Abstract
Evolution of cancer cells are characterized by large scale and rapid changes in the chromosomal landscape. The fluorescence in situ hybridization (FISH) technique provides a way to measure the copy numbers of preselected genes in a group of cells and has been found to be a reliable source of data to model the evolution of tumor cells. Chowdhury et al. [1, 2] recently develop a theoreticallly sound and scalable model for tumor progression driven by gains and losses in cell count patterns obtained by FISH probes. Their model aims to find the Rectilinear Steiner Minimum Tree (RSMT) that describes progression of FISH cell count patterns over its branches in a parsimonious manner. This model is found to effectively model tumor evolution and is also useful in tumor classification. However the RSMT problem is NP–complete and efficient heuristics are necessary to obtain useful solutions, especially for large datasets. In this paper we design a new algorithm for the RSMT problem, based on Maximum Parsimony phylogeny inference. Experimental results from both simulated and real tumor data show that our approach outperforms previous heuristics for the RSMT problem, thus obtaining better models for tumor evolution.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Chowdhury, S.A., Shackney, S.E., Heselmeyer-Haddad, K., Ried, T., Schäffer, A.A., Schwartz, R.: Phylogenetic analysis of multiprobe fluorescence in situ hybridization data from tumor cell populations. Bioinformatics 29(13), 189–198 (2013)
Chowdhury, S.A., Shackney, S.E., Heselmeyer-Haddad, K., Ried, T., Schäffer, A.A., Schwartz, R.: Algorithms to model single gene, single chromosome, and whole genome copy number changes jointly in tumor phylogenetics. PLoS Comput. Biol. 10(7), 1003740 (2014)
Weinberg, R.: The Biology of Cancer. Garland Science, New York (2013)
Futreal, P.A., Coin, L., Marshall, M., Down, T., Hubbard, T., Wooster, R., Rahman, N., Stratton, M.R.: A census of human cancer genes. Nat. Rev. Cancer 4(3), 177–183 (2004)
Swanton, C.: Intratumor heterogeneity: evolution through space and time. Cancer Res. 72(19), 4875–4882 (2012)
Greaves, M., Maley, C.C.: Clonal evolution in cancer. Nature 481(7381), 306–313 (2012)
Yates, L.R., Campbell, P.J.: Evolution of the cancer genome. Nat. Rev. Genet. 13(11), 795–806 (2012)
Attolini, C.S.-O., Michor, F.: Evolutionary theory of cancer. Ann. N. Y. Acad. Sci. 1168(1), 23–51 (2009)
Baudis, M.: Genomic imbalances in 5918 malignant epithelial tumors: an explorative meta-analysis of chromosomal cgh data. BMC Cancer 7(1), 226 (2007)
Pleasance, E.D., Cheetham, R.K., Stephens, P.J., McBride, D.J., Humphray, S.J., Greenman, C.D., Varela, I., Lin, M.-L., Ordóñez, G.R., Bignell, G.R., et al.: A comprehensive catalogue of somatic mutations from a human cancer genome. Nature 463(7278), 191–196 (2009)
Martins, F.C., De, S., Almendro, V., Gönen, M., Park, S.Y., Blum, J.L., Herlihy, W., Ethington, G., Schnitt, S.J., Tung, N., et al.: Evolutionary pathways in brca1-associated breast tumors. Cancer Discov. 2(6), 503–511 (2012)
Navin, N., Krasnitz, A., Rodgers, L., Cook, K., Meth, J., Kendall, J., Riggs, M., Eberling, Y., Troge, J., Grubor, V., et al.: Inferring tumor progression from genomic heterogeneity. Genome Res. 20(1), 68–80 (2010)
Cheng, Y.-K., Beroukhim, R., Levine, R.L., Mellinghoff, I.K., Holland, E.C., Michor, F.: A mathematical methodology for determining the temporal order of pathway alterations arising during gliomagenesis. PLoS Comput. Biol. 8(1), 1002337 (2012)
Shlien, A., Malkin, D.: Copy number variations and cancer. Genome Med 1(6), 62 (2009)
Zack, T.I., Schumacher, S.E., Carter, S.L., Cherniack, A.D., Saksena, G., Tabak, B., Lawrence, M.S., Zhang, C.-Z., Wala, J., Mermel, C.H., et al.: Pan-cancer patterns of somatic copy number alteration. Nat. Genet. 45(10), 1134–1140 (2013)
De Bont, R., Van Larebeke, N.: Endogenous dna damage in humans: a review of quantitative data. Mutagenesis 19(3), 169–185 (2004)
Schärer, O.D.: Dna interstrand crosslinks: natural and drug-induced dna adducts that induce unique cellular responses. ChemBioChem 6(1), 27–32 (2005)
Sung, J.-S., Demple, B.: Roles of base excision repair subpathways in correcting oxidized abasic sites in dna. Febs J. 273(8), 1620–1629 (2006)
Caldecott, K.W.: Single-strand break repair and genetic disease. Nat. Rev. Genet. 9(8), 619–631 (2008)
Cleaver, J.E., Lam, E.T., Revet, I.: Disorders of nucleotide excision repair: the genetic and molecular basis of heterogeneity. Nat. Rev. Genet. 10(11), 756–768 (2009)
Sale, J.E., Lehmann, A.R., Woodgate, R.: Y-family dna polymerases and their role in tolerance of cellular dna damage. Nat. Rev. Mo. Cell Biol. 13(3), 141–152 (2012)
Chapman, J.R., Taylor, M.R., Boulton, S.J.: Playing the end game: Dna double-strand break repair pathway choice. Mo. Cell 47(4), 497–510 (2012)
Wolters, S., Ermolaeva, M.A., Bickel, J.S., Fingerhut, J.M., Khanikar, J., Chan, R.C., Schumacher, B.: Loss of caenorhabditis elegans brca1 promotes genome stability during replication in smc-5 mutants. Genetics 196(4), 985–999 (2014)
Pennington, G., Smith, C.A., Shackney, S., Schwartz, R.: Reconstructing tumor phylogenies from heterogeneous single-cell data. J. Bioinf. Comput. Biol. 5(02a), 407–427 (2007)
Xu, X., Hou, Y., Yin, X., Bao, L., Tang, A., Song, L., Li, F., Tsang, S., Wu, K., Wu, H., et al.: Single-cell exome sequencing reveals single-nucleotide mutation characteristics of a kidney tumor. Cell 148(5), 886–895 (2012)
Von Heydebreck, A., Gunawan, B., Füzesi, L.: Maximum likelihood estimation of oncogenetic tree models. Biostatistics 5(4), 545–556 (2004)
Greenman, C.D., Pleasance, E.D., Newman, S., Yang, F., Fu, B., Nik-Zainal, S., Jones, D., Lau, K.W., Carter, N., Edwards, P.A., et al.: Estimation of rearrangement phylogeny for cancer genomes. Genome Res. 22(2), 346–361 (2012)
Gerstung, M., Baudis, M., Moch, H., Beerenwinkel, N.: Quantifying cancer progression with conjunctive bayesian networks. Bioinformatics 25(21), 2809–2815 (2009)
Langer-Safer, P.R., Levine, M., Ward, D.C.: Immunological method for mapping genes on drosophila polytene chromosomes. Proc. Natl. Acad. Sci. 79(14), 4381–4385 (1982)
Zhou, J., Lin, Y., Hoskins, W., Tang, J.: An iterative approach for phylogenetic analysis of tumor progression using FISH copy number. In: Harrison, R., Li, Y., Mandoiu, I. (eds.) ISBRA 2015. LNCS, vol. 9096, pp. 402–412. Springer, Heidelberg (2015)
Wangsa, D., Heselmeyer-Haddad, K., Ried, P., Eriksson, E., Schäffer, A.A., Morrison,L.E., Luo, J., Auer, G., Munck-Wikland, E., Ried, T., et al.: Fluorescence insitu hybridization markers for prediction of cervical lymph node metastases. Am. J. Pathol. 175(6), 2637–2645 (2009)
Goloboff, P.A., Farris, J.S., Nixon, K.C.: TNT, a free program for phylogenetic analysis. Cladistics 24(5), 774–786 (2008)
Goloboff, P.A., Mattoni, C.I., Quinteros, A.S.: Continuous characters analyzed as such. Cladistics 22(6), 589–601 (2006)
Garey, M.R., Johnson, D.S.: The rectilinear steiner tree problem is np-complete. SIAM J. Appl. Math. 32(4), 826–834 (1977)
Day, W.H.: Computational complexity of inferring phylogenies from dissimilarity matrices. Bull. Math. Biol. 49(4), 461–467 (1987)
Swofford, D.L., Maddison, W.P.: Reconstructing ancestral character states under wagner parsimony. Math. Biosci. 87(2), 199–229 (1987)
Giribet, G.: Efficient tree searches with available algorithms. Evolutionary bioinformaticsonline 3, 341 (2007)
Acknowledgements
We thank Lingxi Zhou, Bin Feng,and Yan Zhang for helpful comments. JZ, WH and, JT were funded by NSF IIS 1161586 and an internal grant from Tianjin University, China. YL was supported by a fellowship of the Swiss National Science Foundation. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Zhou, J., Lin, Y., Rajan, V., Hoskins, W., Tang, J. (2015). Maximum Parsimony Analysis of Gene Copy Number Changes. In: Pop, M., Touzet, H. (eds) Algorithms in Bioinformatics. WABI 2015. Lecture Notes in Computer Science(), vol 9289. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-48221-6_8
Download citation
DOI: https://doi.org/10.1007/978-3-662-48221-6_8
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-48220-9
Online ISBN: 978-3-662-48221-6
eBook Packages: Computer ScienceComputer Science (R0)