Abstract
Tumors exhibit extensive intra-tumor heterogeneity, the presence of groups of cellular populations with distinct sets of somatic mutations. This heterogeneity is the result of an evolutionary process, described by a phylogenetic tree. The problem of reconstructing a phylogenetic tree T given bulk sequencing data from a tumor is more complicated than the classic phylogeny inference problem. Rather than observing the leaves of T directly, we are given mutation frequencies that are the result of mixtures of the leaves of T. The majority of current tumor phylogeny inference methods employ the perfect phylogeny evolutionary model. In this work, we show that the underlying Perfect Phylogeny Mixture combinatorial problem typically has multiple solutions. We provide a polynomial-time computable upper bound on the number of solutions. We use simulations to identify factors that contribute to and counteract non-uniqueness of solutions. In addition, we study the sampling performance of current methods, identifying significant biases.
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
Notes
- 1.
We expect the counting problem #PPM to be #P-complete, as to date no NP-complete problem has been found whose counting version is not NP-complete [14]. To prove that #PPM is #P-complete, we need to give a parsimonious reduction from a known #P-complete problem to #PPM.
References
Deshwar, A.G., et al.: Abstract B2–59: PhyloSpan: Using multi-mutation reads to resolve subclonal architectures from heterogeneous tumor samples. Cancer Res. 75(22 Suppl. 2), B2-59–B2-59 (2015)
Deshwar, A.G., et al.: PhyloWGS: reconstructing subclonal composition and evolution from whole-genome sequencing of tumors. Genome Biol. 16(1), 35 (2015)
El-Kebir, M., Oesper, L., Acheson-Field, H., Raphael, B.J.: Reconstruction of clonal trees and tumor composition from multi-sample sequencing data. Bioinformatics 31(12), i62–i70 (2015)
El-Kebir, M., Satas, G., Oesper, L., Raphael, B.J.: Inferring the mutational history of a tumor using multi-state perfect phylogeny mixtures. Cell Syst. 3(1), 43–53 (2016)
El-Kebir, M., Satas, G., Raphael, B.J.: Inferring parsimonious migration histories for metastatic cancers. Nature Genetics 50(5), 718–726 (2018)
Fisher, R., Pusztai, L., Swanton, C.: Cancer heterogeneity: implications for targeted therapeutics. Br. J. Cancer 108(3), 479–485 (2013)
Gabow, H.N., Myers, E.W.: Finding all spanning trees of directed and undirected graphs. SIAM J. Comput. 7(3), 280–287 (1978)
Gerstung, M., et al.: PCAWG Evolution, Heterogeneity Working Group, and PCAWG network. The evolutionary history of 2,658 cancers. bioRxiv, p. 161562, July 2017
Jamal-Hanjani, M., et al.: Trackingthe evolution of non-small-cell lung cancer. New Engl. J. Med. 376(22), 2109–2121 (2017)
Jiang, Y., Qiu, Y., Minn, A.J., Zhang, N.R.: Assessing intratumor heterogeneity and tracking longitudinal and spatial clonal evolutionary history by next-generation sequencing. Proc. National Acad. Sci. United States Am. 113(37), E5528–37 (2016)
Jiao, W., Vembu, S., Deshwar, A.G., Stein, L., Morris, Q.: Inferring clonal evolution of tumors from single nucleotide somatic mutations. BMC Bioinform. 15, 35 (2014)
Kandoth, C., et al.: Mutational landscape and significance across 12 major cancer types. Nature 502(7471), 333–339 (2013)
Kirchhoff, G.: Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird. Annalen der Physik 148, 497–508 (1847)
Livne, N.: A note on #P-completeness of NP-witnessing relations. Inf. Process. Lett. 109(5), 259–261 (2009)
Łuksza, M., et al.: A neoantigen fitness model predicts tumour response to checkpoint blockade immunotherapy. Nature 551(7681), 517 (2017)
Malikic, S., Jahn, K., Kuipers, J., Sahinalp, C., Beerenwinkel, N.: Integrative inference of subclonal tumour evolution from single-cell and bulk sequencing data. bioRxiv, p. 234914, December 2017
Malikic, S., McPherson, A.W., Donmez, N., Sahinalp, C.S.: Clonality inference in multiple tumor samples using phylogeny. Bioinformatics 31(9), 1349–1356 (2015)
McGranahan, N., et al.: Clonal status of actionable driver events and the timing of mutational processes in cancer evolution. Sci. Trans. Med. 7(283), 283ra54 (2015)
Nowell, P.C.: The clonal evolution of tumor cell populations. Science 194(4260), 23–8 (1976)
Popic, V., Salari, R., Hajirasouliha, I., Kashef-Haghighi, D., West, R.B., Batzoglou, S.: Fast and scalable inference of multi-sample cancer lineages. Genome Biol. 16(1), 91 (2015)
Propp, J.G., Wilson, D.B., James Gary Propp and David Bruce Wilson: How to get a perfectly random sample from a generic Markov chain and generate a random spanning tree of a directed graph. J. Algorithms 27(2), 170–217 (1998)
Schwartz, R., Schäffer, A.A., Russell Schwartz and Alejandro: The evolution of tumour phylogenetics: principles and practice. Nature Rev. Genet. 18(4), 213–229 (2017)
Strino, F., Parisi, F., Micsinai, M., Kluger, Y.: Trap: a tree approach for fingerprinting subclonal tumor composition. Nucleic Acids Res. 41(17), e165 (2013)
Tabassum, D.P., Polyak, K.: Tumorigenesis: it takes a village. Nature Rev. Cancer 15(8), 473–483 (2015)
Turajlic, S., et al.: Tracking cancer evolution reveals constrained routes to metastases: TRACERx Renal. Cell 173(3), 581–594 (2018)
Turajlic, S., et al.: Deterministic evolutionary trajectories influence primary tumor growth: TRACERx renal. Cell 173(3), 581–594 (2018)
Tutte, W.T.: The dissection of equilateral triangles into equilateral triangles. Math. Proc. Camb. Philos. Soc. 44(4), 463–482 (1948)
Venkatesan, S., Swanton, C.: Tumor evolutionary principles: how intratumor heterogeneity influences cancer treatment and outcome. Am. Soc. Clin. Oncol. Educ. Book. 35, e141–9 (2016). American Society of Clinical Oncology. Meeting
Yuan, K., Sakoparnig, T., Markowetz, F., Beerenwinkel, N.: BitPhylogeny: a probabilistic framework for reconstructing intra-tumor phylogenies. Genome Biol. 16(1), 1 (2015)
Zhang, A.W., et al.: Interfaces of malignant and immunologic clonal dynamics in ovarian cancer. Cell 173(7), 1755–1769.e22 (2018)
Acknowledgements
This research is part of the Blue Waters sustained-petascale computing project, which is supported by the National Science Foundation (awards OCI-0725070 and ACI-1238993) and the state of Illinois. Blue Waters is a joint effort of the University of Illinois at Urbana-Champaign and its National Center for Supercomputing Applications. The authors thank the anonymous referees for insightful comments that have improved the manuscript.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Pradhan, D., El-Kebir, M. (2018). On the Non-uniqueness of Solutions to the Perfect Phylogeny Mixture Problem. In: Blanchette, M., Ouangraoua, A. (eds) Comparative Genomics. RECOMB-CG 2018. Lecture Notes in Computer Science(), vol 11183. Springer, Cham. https://doi.org/10.1007/978-3-030-00834-5_16
Download citation
DOI: https://doi.org/10.1007/978-3-030-00834-5_16
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-00833-8
Online ISBN: 978-3-030-00834-5
eBook Packages: Computer ScienceComputer Science (R0)