Shannon divergence and the novel Statistical Complexity quantifiers defined here are in high correlation with gene expression changes of well-established biomarkers associated to cancer progression. In addition, variations of the basic technique (i.e. a modified form of statistical complexity) which allows us to better understand the phenotypic changes observed in these samples which are associated with the progression and the transitions of the gene expression profiles. For instance, in a properly defined Statistical Complexity vs. Entropy plane, on a melanoma dataset first studied in Ref. [110] , samples appear in well differentiated ''clusters''. These clusters correlate well with the phonotypic characteristics of normal skin, nevi, primary and metastatic melanoma. In this ''Complexity vs. Entropy'' plane, primary melanomas samples appear ''bridging'' benign nevi and metastatic melanoma samples. Our results may also suggest that the evolution of metastatic melanoma leads to at least two different subtypes.