Skip to main content

Thank you for visiting nature.com. You are using a browser version with limited support for CSS. To obtain the best experience, we recommend you use a more up to date browser (or turn off compatibility mode in Internet Explorer). In the meantime, to ensure continued support, we are displaying the site without styles and JavaScript.

  • Analysis
  • Published:

Inferring parsimonious migration histories for metastatic cancers

Nature Genetics volume 50, pages 718–726 (2018)Cite this article

Subjects

Abstract

Metastasis is the migration of cancerous cells from a primary tumor to other anatomical sites. Although metastasis was long thought to result from monoclonal seeding, or single cellular migrations, recent phylogenetic analyses of metastatic cancers have reported complex patterns of cellular migrations between sites, including polyclonal migrations and reseeding. However, accurate determination of migration patterns from somatic mutation data is complicated by intratumor heterogeneity and discordance between clonal lineage and cellular migration. We introduce MACHINA, a multi-objective optimization algorithm that jointly infers clonal lineages and parsimonious migration histories of metastatic cancers from DNA sequencing data. MACHINA analysis of data from multiple cancers shows that migration patterns are often not uniquely determined from sequencing data alone and that complicated migration patterns among primary tumors and metastases may be less prevalent than previously reported. MACHINA’s rigorous analysis of migration histories will aid in studies of the drivers of metastasis.

This is a preview of subscription content, access via your institution

Access options

Buy this article

  • Purchase on Springer Link
  • Instant access to full article PDF
Buy now

Prices may be subject to local taxes which are calculated during checkout

Fig. 1: Phylogenetic analysis of metastatic tumors.
Fig. 2: The migration number µ does not determine the migration pattern.
Fig. 3: Migration history analysis requires evaluation of tradeoffs between migration pattern, migration number and comigration number.
Fig. 4: The MACHINA algorithm for joint clone tree inference and migration history analysis.
Fig. 5: MACHINA accurately infers clone trees and migration histories on simulated data.
Fig. 6: Joint analysis of migrations and comigrations leads to more parsimonious migration histories in metastatic ovarian cancer.
Fig. 7: Joint analysis of mutations and migrations shows a monoclonal single-source migration history for a patient with metastatic breast cancer.

Similar content being viewed by others

References

  1. Gupta, G. P. & Massagué, J. Cancer metastasis: building a framework. Cell 127, 679–695 (2006).

    Article  CAS  PubMed  Google Scholar 

  2. Comen, E., Norton, L. & Massagué, J. Clinical implications of cancer self-seeding. Nat. Rev. Clin. Oncol. 8, 369–377 (2011).

    Article  PubMed  Google Scholar 

  3. Faries, M. B., Steen, S., Ye, X., Sim, M. & Morton, D. L. Late recurrence in melanoma: clinical implications of lost dormancy. J. Am. Coll. Surg. 217, 27–34 (2013).

    Article  PubMed  PubMed Central  Google Scholar 

  4. Sanborn, J. Z. et al. Phylogenetic analyses of melanoma reveal complex patterns of metastatic dissemination. Proc. Natl. Acad. Sci. USA 112, 10995–11000 (2015).

    Article  CAS  PubMed  PubMed Central  Google Scholar 

  5. Tabassum, D. P. & Polyak, K. Tumorigenesis: it takes a village. Nat. Rev. Cancer 15, 473–483 (2015).

    Article  CAS  PubMed  Google Scholar 

  6. Macintyre, G. et al. How subclonal modeling is changing the metastatic paradigm. Clin. Cancer Res. 23, 630–635 (2017).

    Article  CAS  PubMed  Google Scholar 

  7. Naxerova, K. & Jain, R. K. Using tumor phylogenetics to identify the roots of metastasis in humans. Nat. Rev. Clin. Oncol. 12, 258–272 (2015).

    Article  CAS  PubMed  Google Scholar 

  8. Turajlic, S. & Swanton, C. Metastasis as an evolutionary process. Science 352, 169–175 (2016).

    Article  CAS  PubMed  Google Scholar 

  9. Choi, Y. J. et al. Intra-individual genomic heterogeneity of high-grade serous carcinoma of the ovary and clinical utility of ascitic cancer cells for mutation profiling. J. Pathol. 241, 57–66 (2017).

    Article  CAS  PubMed  Google Scholar 

  10. Hoadley, K. A. et al. Tumor evolution in two patients with basal-like breast cancer: a retrospective genomics study of multiple metastases. PLoS Med. 13, e1002174 (2016).

    Article  PubMed  PubMed Central  Google Scholar 

  11. Gundem, G. et al. The evolutionary history of lethal metastatic prostate cancer. Nature 520, 353–357 (2015).

    Article  CAS  PubMed  PubMed Central  Google Scholar 

  12. McPherson, A. et al. Divergent modes of clonal spread and intraperitoneal mixing in high-grade serous ovarian cancer. Nat. Genet. 48, 758–767 (2016).

    Article  CAS  PubMed  Google Scholar 

  13. Brown, D. et al. Phylogenetic analysis of metastatic progression in breast cancer using somatic mutations and copy-number aberrations. Nat. Commun. 8, 14944 (2017).

    Article  CAS  PubMed  PubMed Central  Google Scholar 

  14. Aceto, N. et al. Circulating tumor cell clusters are oligoclonal precursors of breast cancer metastasis. Cell 158, 1110–1122 (2014).

    Article  CAS  PubMed  PubMed Central  Google Scholar 

  15. Marrinucci, D. et al. Fluid biopsy in patients with metastatic prostate, pancreatic and breast cancers. Phys. Biol. 9, 016003 (2012).

    Article  PubMed  PubMed Central  Google Scholar 

  16. Maddipati, R. & Stanger, B. Z. Pancreatic cancer metastases harbor evidence of polyclonality. Cancer Discov. 5, 1086–1097 (2015).

    Article  CAS  PubMed  PubMed Central  Google Scholar 

  17. Yu, M. et al. Circulating breast tumor cells exhibit dynamic changes in epithelial and mesenchymal composition. Science 339, 580–584 (2013).

    Article  CAS  PubMed  PubMed Central  Google Scholar 

  18. Cheung, K. J. et al. Polyclonal breast cancer metastases arise from collective dissemination of keratin-14-expressing tumor cell clusters. Proc. Natl. Acad. Sci. USA 113, E854–E863 (2016).

    Article  CAS  PubMed  PubMed Central  Google Scholar 

  19. Dadiani, M. et al. Real-time imaging of lymphogenic metastasis in orthotopic human breast cancer. Cancer Res. 66, 8037–8041 (2006).

    Article  CAS  PubMed  Google Scholar 

  20. Cheung, K. J. & Ewald, A. J. A collective route to metastasis: seeding by tumor cell clusters. Science 352, 167–169 (2016).

    Article  CAS  PubMed  Google Scholar 

  21. Gerlinger, M. et al. Intratumor heterogeneity and branched evolution revealed by multi-region sequencing. N. Engl. J. Med. 366, 883–892 (2012).

    Article  CAS  PubMed  PubMed Central  Google Scholar 

  22. Gerlinger, M. et al. Genomic architecture and evolution of clear-cell renal cell carcinomas defined by multi-region sequencing. Nat. Genet. 46, 225–233 (2014).

    Article  CAS  PubMed  PubMed Central  Google Scholar 

  23. Kim, T.-M. et al. Subclonal genomic architectures of primary and metastatic colorectal cancer based on intratumoral genetic heterogeneity. Clin. Cancer Res. 21, 4461–4472 (2015).

    Article  CAS  PubMed  Google Scholar 

  24. Zhao, Z.-M. et al. Early and multiple origins of metastatic lineages within primary tumors. Proc. Natl. Acad. Sci. USA 113, 2140–2145 (2016).

    Article  CAS  PubMed  PubMed Central  Google Scholar 

  25. McCreery, M. Q. et al. Evolution of metastasis revealed by mutational landscapes of chemically induced skin cancers. Nat. Med. 21, 1514–1520 (2015).

    Article  CAS  PubMed  PubMed Central  Google Scholar 

  26. Liu, B. et al. Spatiotemporal genomic heterogeneity, phylogeny and metastatic evolution in salivary adenoid cystic carcinoma. J. Natl. Cancer Inst. 109, 109 (2017).

    Google Scholar 

  27. Zhai, W. et al. The spatial organization of intratumor heterogeneity and evolutionary trajectories of metastases in hepatocellular carcinoma. Nat. Commun. 8, 4565 (2017).

    Article  CAS  PubMed  PubMed Central  Google Scholar 

  28. Gibson, W. J. et al. The genomic landscape and evolution of endometrial carcinoma progression and abdominopelvic metastasis. Nat. Genet. 48, 848–855 (2016).

    Article  CAS  PubMed  PubMed Central  Google Scholar 

  29. Lote, H. et al. Carbon dating cancer: defining the chronology of metastatic progression in colorectal cancer. Ann. Oncol. 28, 1243–1249 (2017).

    Article  CAS  PubMed  PubMed Central  Google Scholar 

  30. Thomsen, M. B. H. et al. Spatial and temporal clonal evolution during development of metastatic urothelial carcinoma. Mol. Oncol. 10, 1450–1460 (2016).

    Article  PubMed  PubMed Central  Google Scholar 

  31. Tan, Q. et al. Genomic alteration during metastasis of lung adenocarcinoma. Cell. Physiol. Biochem. 38, 469–486 (2016).

    Article  CAS  PubMed  Google Scholar 

  32. Hosseini, H. et al. Early dissemination seeds metastasis in breast cancer. Nature 540, 552–558 (2016).

    Article  CAS  Google Scholar 

  33. Xue, R. et al. Variable intratumor genomic heterogeneity of multiple lesions in patients with hepatocellular carcinoma. Gastroenterology 150, 998–1008 (2016).

    Article  PubMed  Google Scholar 

  34. Campbell, P. J. et al. The patterns and dynamics of genomic instability in metastatic pancreatic cancer. Nature 467, 1109–1113 (2010).

    Article  CAS  PubMed  PubMed Central  Google Scholar 

  35. Schwarz, R. F. et al. Spatial and temporal heterogeneity in high-grade serous ovarian cancer: a phylogenetic analysis. PLoS Med. 12, e1001789 (2015).

    Article  PubMed  PubMed Central  Google Scholar 

  36. Beltran, H. et al. Divergent clonal evolution of castration-resistant neuroendocrine prostate cancer. Nat. Med. 22, 298–305 (2016).

    Article  CAS  PubMed  PubMed Central  Google Scholar 

  37. De Mattos-Arruda, L. et al. Establishing the origin of metastatic deposits in the setting of multiple primary malignancies: the role of massively parallel sequencing. Mol. Oncol. 8, 150–158 (2014).

    Article  PubMed  Google Scholar 

  38. Naxerova, K. et al. Origins of lymphatic and distant metastases in human colorectal cancer. Science 357, 55–60 (2017).

    Article  CAS  PubMed  PubMed Central  Google Scholar 

  39. Nik-Zainal, S. et al. The life history of 21 breast cancers. Cell 149, 994–1007 (2012).

    Article  CAS  PubMed  PubMed Central  Google Scholar 

  40. Burrell, R. A., McGranahan, N., Bartek, J. & Swanton, C. The causes and consequences of genetic heterogeneity in cancer evolution. Nature 501, 338–345 (2013).

    Article  CAS  PubMed  Google Scholar 

  41. Alves, J. M., Prieto, T. & Posada, D. Multiregional tumor trees are not phylogenies. Trends Cancer 3, 546–550 (2017).

    Article  PubMed  PubMed Central  Google Scholar 

  42. Miller, C. A. et al. SciClone: inferring clonal architecture and tracking the spatial and temporal patterns of tumor evolution. PLoS Comput. Biol. 10, e1003665 (2014).

    Article  PubMed  PubMed Central  Google Scholar 

  43. Roth, A. et al. PyClone: statistical inference of clonal population structure in cancer. Nat. Methods 11, 396–398 (2014).

    Article  CAS  PubMed  PubMed Central  Google Scholar 

  44. Deshwar, A. G. et al. PhyloWGS: reconstructing subclonal composition and evolution from whole-genome sequencing of tumors. Genome Biol. 16, 35 (2015).

    Article  PubMed  PubMed Central  Google Scholar 

  45. Malikic, S., McPherson, A. W., Donmez, N. & Sahinalp, C. S. Clonality inference in multiple tumor samples using phylogeny. Bioinformatics 31, 1349–1356 (2015).

    Article  CAS  PubMed  Google Scholar 

  46. Popic, V. et al. Fast and scalable inference of multi-sample cancer lineages. Genome Biol. 16, 91 (2015).

    Article  PubMed  PubMed Central  Google Scholar 

  47. 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, i62–i70 (2015).

    Article  CAS  PubMed  PubMed Central  Google Scholar 

  48. Yuan, K., Sakoparnig, T., Markowetz, F. & Beerenwinkel, N. BitPhylogeny: a probabilistic framework for reconstructing intratumor phylogenies. Genome Biol. 16, 36 (2015).

    Article  PubMed  PubMed Central  Google Scholar 

  49. El-Kebir, M., Satas, G., Oesper, L. & Raphael, B. J. Inferring the mutational history of a tumor using multistate perfect phylogeny mixtures. Cell Syst. 3, 43–53 (2016).

    Article  CAS  PubMed  Google Scholar 

  50. Dang, H. X. et al. ClonEvol: clonal ordering and visualization in cancer sequencing. Ann. Oncol. 28, 3076–3082 (2017).

    Article  CAS  PubMed  Google Scholar 

  51. Reiter, J. G. et al. Reconstructing metastatic seeding patterns of human cancers. Nat. Commun. 8, 14114 (2017).

    Article  CAS  PubMed  PubMed Central  Google Scholar 

  52. Vakiani, E. et al. Local recurrences at the anastomotic area are clonally related to the primary tumor in sporadic colorectal carcinoma. Oncotarget 8, 42487–42494 (2017).

    Article  PubMed  PubMed Central  Google Scholar 

  53. Makohon-Moore, A. P. et al. Limited heterogeneity of known driver gene mutations among the metastases of individual patients with pancreatic cancer. Nat. Genet. 49, 358–366 (2017).

    Article  CAS  PubMed  PubMed Central  Google Scholar 

  54. Hong, W. S., Shpak, M. & Townsend, J. P. Inferring the origin of metastases from cancer phylogenies. Cancer Res. 75, 4021–4025 (2015).

    Article  CAS  PubMed  PubMed Central  Google Scholar 

  55. Sankoff, D. Minimal mutation trees of sequences. SIAM J. Appl. Math. 28, 35–42 (1975).

    Article  Google Scholar 

  56. Slatkin, M. & Maddison, W. P. A cladistic measure of gene flow inferred from the phylogenies of alleles. Genetics 123, 603–613 (1989).

    CAS  PubMed  PubMed Central  Google Scholar 

  57. Qiu, M., Hu, J., Yang, D., Cosgrove, D. P. & Xu, R. Pattern of distant metastases in colorectal cancer: a SEER-based study. Oncotarget 6, 38658–38666 (2015).

    PubMed  PubMed Central  Google Scholar 

  58. Pickrell, J. K. & Pritchard, J. K. Inference of population splits and mixtures from genome-wide allele frequency data. PLoS Genet. 8, e1002967 (2012).

    Article  CAS  PubMed  PubMed Central  Google Scholar 

  59. Nelson, M. I., Simonsen, L., Viboud, C., Miller, M. A. & Holmes, E. C. Phylogenetic analysis reveals the global migration of seasonal influenza A viruses. PLoS Pathog. 3, 1220–1228 (2007).

    Article  CAS  PubMed  Google Scholar 

  60. Sottoriva, A. et al. A Big Bang model of human colorectal tumor growth. Nat. Genet. 47, 209–216 (2015).

    Article  CAS  PubMed  PubMed Central  Google Scholar 

  61. Saitou, N. & Nei, M. The neighbor-joining method: a new method for reconstructing phylogenetic trees. Mol. Biol. Evol. 4, 406–425 (1987).

    CAS  PubMed  Google Scholar 

  62. Ross, E. M. & Markowetz, F. OncoNEM: inferring tumor evolution from single-cell sequencing data. Genome Biol. 17, 69 (2016).

    Article  CAS  PubMed  PubMed Central  Google Scholar 

  63. Jahn, K., Kuipers, J. & Beerenwinkel, N. Tree inference for single-cell data. Genome Biol. 17, 86 (2016).

    Article  PubMed  PubMed Central  Google Scholar 

  64. Zafar, H., Tzen, A., Navin, N., Chen, K. & Nakhleh, L. SiFit: inferring tumor trees from single-cell sequencing data under finite-sites models. Genome Biol. 18, 178 (2017).

    Article  PubMed  PubMed Central  Google Scholar 

  65. Leung, M. L. et al. Single-cell DNA sequencing reveals a late-dissemination model in metastatic colorectal cancer. Genome Res. 27, 1287–1299 (2017).

    Article  CAS  PubMed  PubMed Central  Google Scholar 

  66. Maddison, W. Reconstructing character evolution on polytomous cladograms. Cladistics 5, 365–377 (1989).

    Article  Google Scholar 

  67. Fitch, W. M. Toward defining the course of evolution: minimum change for a specific tree topology. Syst. Biol. 20, 406–416 (1971).

    Article  Google Scholar 

  68. Felsenstein, J. Evolutionary trees from DNA sequences: a maximum-likelihood approach. J. Mol. Evol. 17, 368–376 (1981).

    Article  CAS  PubMed  Google Scholar 

  69. Strino, F., Parisi, F., Micsinai, M. & Kluger, Y. TrAp: a tree approach for fingerprinting subclonal tumor composition. Nucleic Acids Res. 41, e165 (2013).

    Article  CAS  PubMed  PubMed Central  Google Scholar 

  70. Jiao, W., Vembu, S., Deshwar, A. G., Stein, L. & Morris, Q. Inferring clonal evolution of tumors from single-nucleotide somatic mutations. BMC Bioinformatics 15, 35 (2014).

    Article  PubMed  PubMed Central  Google Scholar 

  71. Satas, G. & Raphael, B. J. Tumor phylogeny inference using tree-constrained importance sampling. Bioinformatics 33, i152–i160 (2017).

    Article  PubMed  PubMed Central  Google Scholar 

  72. Zare, H. et al. Inferring clonal composition from multiple sections of a breast cancer. PLoS Comput. Biol. 10, e1003703 (2014).

    Article  PubMed  PubMed Central  Google Scholar 

  73. Salehi, S. et al. ddClone: joint statistical inference of clonal populations from single-cell and bulk-tumor sequencing data. Genome Biol. 18, 44 (2017).

    Article  PubMed  PubMed Central  Google Scholar 

  74. Reiter, J.G., Bozic, I., Chatterjee, K. & Nowak, M.A. in Computer-Aided Verification (eds. Sharygina, N. and Veith, H.) 101–106 (Springer, Berlin and Heidelberg, Germany, 2013).

  75. Hajirasouliha, I. & Raphael, B.J. in Algorithms in Bioinformatics (eds. Brown, D. and Morgenstern, B.) 354–367 (Springer-Verlag, Berlin and Heidelberg, Germany, 2014).

  76. Robinson, D. F. & Foulds, L. R. Comparison of phylogenetic trees. Math. Biosci. 53, 131–147 (1981).

    Article  Google Scholar 

Download references

Acknowledgements

We thank the authors of the studies by McPherson et al.12, Gundem et al.11, Hoadley et al.10 and Sanborn et al.4 for providing analyzed data in their published manuscripts. This work is supported by US National Institutes of Health (NIH) grants R01HG007069 (B.J.R.), R01CA180776 (B.J.R.) and U24CA211000 (B.J.R.) and US National Science Foundation (NSF) CAREER Award CCF-1053753 (B.J.R.).

Author information

Author notes

  1. Mohammed El-Kebir

    Present address: Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL, USA

Authors and Affiliations

  1. Department of Computer Science, Princeton University, Princeton, NJ, USA

    Mohammed El-Kebir, Gryte Satas & Benjamin J. Raphael

  2. Department of Computer Science, Brown University, Providence, RI, USA

    Gryte Satas

Authors
  1. Mohammed El-Kebir
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Gryte Satas
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Benjamin J. Raphael
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

M.E.-K. and B.J.R. conceived the project; M.E.-K., G.S. and B.J.R. developed the theory and algorithms; M.E.-K. implemented the algorithms; M.E.-K. and G.S. performed simulations and analysis of real data; M.E.-K., G.S. and B.J.R. wrote the manuscript.

Corresponding author

Correspondence to Benjamin J. Raphael.

Ethics declarations

Competing interests

B.J.R. is a cofounder of, and consultant to, Medley Genomics.

Additional information

Publisher’s note: Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Supplementary information

Supplementary Text and Figures

Supplementary Figures 1–24, Supplementary Note and Supplementary Tables 1–9

Reporting Summary

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

El-Kebir, M., Satas, G. & Raphael, B.J. Inferring parsimonious migration histories for metastatic cancers. Nat Genet 50, 718–726 (2018). https://doi.org/10.1038/s41588-018-0106-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1038/s41588-018-0106-z

This article is cited by

Search

Advanced search

Quick links

Nature Briefing: Cancer

Sign up for the Nature Briefing: Cancer newsletter — what matters in cancer research, free to your inbox weekly.

Get what matters in cancer research, free to your inbox weekly. Sign up for Nature Briefing: Cancer