Ranking Genes from DNA Microarray Data of Cervical Cancer by a local Tree Comparison

Authors: Frank Emmert-Streib, Matthias Dehmer, Jing Liu, Max Muhlhauser

Abstract:

The major objective of this paper is to introduce a new method to select genes from DNA microarray data. As criterion to select genes we suggest to measure the local changes in the correlation graph of each gene and to select those genes whose local changes are largest. More precisely, we calculate the correlation networks from DNA microarray data of cervical cancer whereas each network represents a tissue of a certain tumor stage and each node in the network represents a gene. From these networks we extract one tree for each gene by a local decomposition of the correlation network. The interpretation of a tree is that it represents the n-nearest neighbor genes on the n-th level of a tree, measured by the Dijkstra distance, and, hence, gives the local embedding of a gene within the correlation network. For the obtained trees we measure the pairwise similarity between trees rooted by the same gene from normal to cancerous tissues. This evaluates the modification of the tree topology due to tumor progression. Finally, we rank the obtained similarity values from all tissue comparisons and select the top ranked genes. For these genes the local neighborhood in the correlation networks changes most between normal and cancerous tissues. As a result we find that the top ranked genes are candidates suspected to be involved in tumor growth. This indicates that our method captures essential information from the underlying DNA microarray data of cervical cancer.

Keywords: Graph similarity, generalized trees, graph alignment, DNA microarray data, cervical cancer.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1060016

References:

[1] R. Bellman, Dynamic Programming. Princeton University Press, 1957.
[2] M. Dehmer, Strukturelle Analyse web-basierter Dokumente, Ph.D Thesis, Department of Computer Science, Technische Universit¨at Darmstadt, 2005.
[3] E. W. Dijkstra, A note on two problems in connection with graphs. Numerische Math., Vol. 1, 1959, 269-271.
[4] F. Emmert-Streib., M. Dehmer, J. Kilian: Classification of large Graphs by a local Tree decomposition, Proceedings of the 2005 International Conference on Data Mining (DMIN-05), Editors: H.R. Arabnia, A. Scime (2005) 200-207.
[5] T. R. Golub et.al., Molecular Classification of Cancer: Class Discovery and Class Prediction by Gene Expression Monitoring, Science, Vol. 286, 1999, 531-537.
[6] F. Kaden, Graphmetriken und Distanzgraphen. ZKI-Informationen, Akad. Wiss. DDR, Vol. 2 (82), 1982, 1-63.
[7] F. Kaden, Graph metrics and distance-graphs. In: Graphs and other Combinatorial Topics, ed. M. Fiedler, Teubner Texte zur Math., Leipzig, Vol. 59, 1983, 145-158.
[8] P. J. Kraulis, Molscript: A Program to Produce Both detailed and schematic plots of protein structures. Journal of Applied Crystallography, Vol. 24, 1991, 946-950.
[9] K.Mori et al., Highly specific marker genes for detecting minimal gastric cancer cells in cytology negative peritoneal washings, Biochem. Biophys. Res. Commun. 23;313(4):931-937 (2004).
[10] V. Batagelj and A. Mrvar, Pajek - Program for Large Network Analysis, Connections 21:47-57 (1998).
[11] R. C. Read and D. G. Corneil, The graph isomorphism disease. Journal of Graph Theory, Vol. 1, 1977, 339-363.
[12] J. Rougemont and P. Hingamp, DNA microarray data and contextual analysis of correlation graphs. BMC Bioinformatics, Vol. 4, 2003, 4-15.
[13] F. Sobik, Graphmetriken und Klassifikation strukturierter Objekte. ZKIInformationen, Akad. Wiss. DDR, Vol. 2 (82), 1982, 63-122.
[14] F. Sobik, Graphmetriken und Charakterisierung von Graphklassen. 27. Internat. Wiss. Koll., TH-Ilmenau, Vol. 2 (82), 1982, 63-122.
[15] J. R. Ullman, An algorithm for subgraph isomorphism. J. ACM, Vol. 23 (1), 1976, 31-42.
[16] Y. Wang et al., Gene expression profiles and molecular markers to predict recurrence of Dukes-B colon cancer, J. Clin. Oncol. 1;22(9):1564- 1571 (2004).
[17] Y. F. Wong et.al. Expression Genomics of Cervical Cancer: Molecular Classification and Prediction of Radiotherapy Response by DNA Microarray. Clinical Cancer Research, Vol. 9, 2003, 5486-5492.
[18] B. Zelinka, On a certain distance between isomorphism classes of graphs. ˇ Casopis pro ˇpest. Mathematiky, Vol. 100, 1975, 371-373.