skip to main content
10.1145/3307339.3342178acmconferencesArticle/Chapter ViewAbstractPublication PagesbcbConference Proceedingsconference-collections
short-paper
Public Access

Reconstructing Intra-Tumor Heterogeneity via Convex Optimization and Branch-and-Bound Search

Published: 04 September 2019 Publication History

Abstract

Studies of intra-tumor heterogeneity using high-throughput sequencing data, i.e., assembly of tumor populations and inference of their relative frequencies, may provide highly valuable information about molecular signatures of cancer and point towards specific therapeutic treatments. Reconstructing heterogeneous tumor populations, however, is a challenging task rendered difficult by complex mutations and further exacerbated by the fact that high-throughput sequencing reads are short relative to genomic regions experiencing structural mutations. In this paper, we present a novel algorithmic framework for computationally efficient and accurate analysis of tumor clonal populations. Given locations of copy number aberrations, the proposed method quantifies gains and losses of the affected regions, and determines relative frequencies of the populations in a clonal mixture. This is achieved by formulating the reconstruction as a mixed-integer optimization problem and solved via a combination of convex optimization and branch-and-bound search. The developed algorithm was tested on realistic synthetic as well as experimental data and shown to outperform state-of-the art competing methods in a variety of scenarios.

References

[1]
Ludmil B. Alexandrov, Serena Nik-Zainal, David C. Wedge, Samuel A. J. R. Aparicio, Sam Behjati, Andrew V. Biankin, Graham R. Bignell, Niccolò Bolli, Ake Borg, Anne-Lise Børresen-Dale, Sandrine Boyault, Birgit Burkhardt, Adam P. Butler, Carlos Caldas, Helen R. Davies, Christine Desmedt, Roland Eils, Jórunn Erla Eyfjörd, John A. Foekens, Mel Greaves, Fumie Hosoda, Barbara Hutter, Tomislav Ilicic, Sandrine Imbeaud, Marcin Imielinski, Natalie Jäger, David T. W. Jones, David Jones, Stian Knappskog, Marcel Kool, Sunil R. Lakhani, Carlos López-Otín, Sancha Martin, Nikhil C. Munshi, Hiromi Nakamura, Paul A. Northcott, Marina Pajic, Elli Papaemmanuil, Angelo Paradiso, John V. Pearson, Xose S. Puente, Keiran Raine, Manasa Ramakrishna, Andrea L. Richardson, Julia Richter, Philip Rosenstiel, Matthias Schlesner, Ton N. Schumacher, Paul N. Span, Jon W. Teague, Yasushi Totoki, Andrew N. J. Tutt, Rafael Valdés-Mas, Marit M. van Buuren, Laura van 't Veer, Anne Vincent-Salomon, NicolaWaddell, Lucy R. Yates, Australian Pancreatic Cancer Genome Initiative, ICGC Breast Cancer Consortium, ICGC MMMLSeq Consortium, ICGC PedBrain, Jessica Zucman-Rossi, P. Andrew Futreal, Ultan McDermott, Peter Lichter, Matthew Meyerson, Sean M. Grimmond, Reiner Siebert, Elías Campo, Tatsuhiro Shibata, Stefan M. Pfister, Peter J. Campbell, and Michael R. Stratton. 2013. Signatures of mutational processes in human cancer. Nature 500 (14 08 2013), 415 EP --.
[2]
J. Kenneth Baillie, Mark W. Barnett, Kyle R. Upton, Daniel J. Gerhardt, Todd A. Richmond, Fioravante De Sapio, Paul M. Brennan, Patrizia Rizzu, Sarah Smith, Mark Fell, Richard T. Talbot, Stefano Gustincich, Thomas C. Freeman, John S. Mattick, David A. Hume, Peter Heutink, Piero Carninci, Jeffrey A. Jeddeloh, and Geoffrey J. Faulkner. 2011. Somatic retrotransposition alters the genetic landscape of the human brain. Nature 479 (30 10 2011), 534 EP --.
[3]
Niko Beerenwinkel, Roland F. Schwarz, Moritz Gerstung, and Florian Markowetz. 2015. Cancer Evolution: Mathematical Models and Computational Inference. Systematic Biology 64, 1 (2015), e1--e25.
[4]
George B Dantzig. 1957. Discrete-variable extremum problems. Operations research 5, 2 (1957), 266--288 0030--364X.
[5]
Jin-Tang Dong. 2001. Chromosomal Deletions and Tumor Suppressor Genes in Prostate Cancer. Cancer and Metastasis Reviews 20, 3 (2001), 173--193.
[6]
Mohammed El-Kebir, Layla Oesper, Hannah Acheson-Field, and Benjamin J. Raphael. 2015. Reconstruction of clonal trees and tumor composition from multi-sample sequencing data. Bioinformatics 31, 12 (2015), i62--i70.
[7]
Edward D Esplin, Ling Oei, and Michael P Snyder. 2014. Personalized sequencing and the future of medicine: discovery, diagnosis and defeat of disease. Pharmacogenomics 15, 14 (2014), 1771--1790. arXiv:https://doi.org/10.2217/pgs.14.117 25493570.
[8]
Manuel L Gonzalez-Garay. 2014. The road from next-generation sequencing to personalized medicine. Personalized Medicine 11, 5 (2014), 523--544. arXiv:https://doi.org/10.2217/pme.14.34 26000024.
[9]
Ravi G Gupta and Robert A Somer. 2017. Intra-tumor Heterogeneity: Novel Approaches for Resolving Genomic Architecture and Clonal Evolution. Molecular Cancer Research (2017). MCR-17-0070 arXiv:http://mcr.aacrjournals.org/content/early/2017/06/08/1541- 7786.MCR-17-0070.full.pdf
[10]
Wei Jiao, Shankar Vembu, Amit G. Deshwar, Lincoln Stein, and Quaid Morris. 2014. Inferring clonal evolution of tumors from single nucleotide somatic mutations. BMC Bioinformatics 15, 1 (2014), 35.
[11]
Pamela S Larson, Benjamin L Schlechter, Antonio de las Morenas, Judy E Garber, L Adrienne Cupples, and Carol L Rosenberg. 2005. Allele imbalance, or loss of heterozygosity, in normal breast epithelium of sporadic breast cancer cases and BRCA1 gene mutation carriers is increased compared with reduction mammoplasty tissues. Journal of clinical oncology 23, 34 (2005), 8613--8619.
[12]
Michael S. Lawrence, Petar Stojanov, Paz Polak, Gregory V. Kryukov, Kristian Cibulskis, Andrey Sivachenko, Scott L. Carter, Chip Stewart, Craig H. Mermel, Steven A. Roberts, Adam Kiezun, Peter S. Hammerman, Aaron McKenna, Yotam Drier, Lihua Zou, Alex H. Ramos, Trevor J. Pugh, Nicolas Stransky, Elena Helman, Jaegil Kim, Carrie Sougnez, Lauren Ambrogio, Elizabeth Nickerson, Erica Shefler, Maria L. Cortés, Daniel Auclair, Gordon Saksena, Douglas Voet, Michael Noble, Daniel DiCara, Pei Lin, Lee Lichtenstein, David I. Heiman, Timothy Fennell, Marcin Imielinski, Bryan Hernandez, Eran Hodis, Sylvan Baca, Austin M. Dulak, Jens Lohr, Dan-Avi Landau, Catherine J. Wu, Jorge Melendez-Zajgla, Alfredo Hidalgo-Miranda, Amnon Koren, Steven A. McCarroll, Jaume Mora, Ryan S. Lee, Brian Crompton, Robert Onofrio, Melissa Parkin,Wendy Winckler, Kristin Ardlie, Stacey B. Gabriel, Charles W. M. Roberts, Jaclyn A. Biegel, Kimberly Stegmaier, Adam J. Bass, Levi A. Garraway, Matthew Meyerson, Todd R. Golub, Dmitry A. Gordenin, Shamil Sunyaev, Eric S. Lander, and Gad Getz. 2013. Mutational heterogeneity in cancer and the search for new cancer-associated genes. Nature 499 (16 06 2013), 214 EP --.
[13]
Yi Li and Xiaohui Xie. 2015. Mixclone: a mixture model for inferring tumor subclonal populations. In BMC genomics, Vol. 16. BioMed Central, S1.
[14]
W W Lockwood, R Chari, B P Coe, L Girard, C MacAulay, S Lam, A F Gazdar, J D Minna, and W L Lam. 2008. DNA amplification is a ubiquitous mechanism of oncogene activation in lung and other cancers. Oncogene 27 (07 04 2008), 4615 EP --.
[15]
Salem Malikic, Andrew W. McPherson, Nilgun Donmez, and Cenk S. Sahinalp. 2015. Clonality inference in multiple tumor samples using phylogeny. Bioinformatics 31, 9 (2015), 1349--1356.
[16]
Iñigo Martincorena and Peter J. Campbell. 2015. Somatic mutation in cancer and normal cells. Science 349, 6255 (2015), 1483--1489.
[17]
Iñigo Martincorena, Amit Roshan, Moritz Gerstung, Peter Ellis, Peter Van Loo, Stuart McLaren, David C Wedge, Anthony Fullam, Ludmil B Alexandrov, and Jose M Tubio. 2015. High burden and pervasive positive selection of somatic mutations in normal human skin. Science 348, 6237 (2015), 880--886 0036--8075.
[18]
Serena Nik-Zainal, Peter Van Loo, David CWedge, Ludmil B Alexandrov, Christopher D Greenman, King Wai Lau, Keiran Raine, David Jones, John Marshall, and Manasa Ramakrishna. 2012. The life history of 21 breast cancers. Cell 149, 5 (2012), 994--1007 0092--8674.
[19]
Layla Oesper, Ahmad Mahmoody, and Benjamin J. Raphael. 2013. THetA: inferring intra-tumor heterogeneity from high-throughput DNA sequencing data. Genome Biology 14, 7 (2013), R80.
[20]
Layla Oesper, Anna Ritz, Sarah J Aerni, Ryan Drebin, and Benjamin J Raphael. 2012. Reconstructing cancer genomes from paired-end sequencing data. BMC Bioinformatics 13, Suppl 6 (2012), S10--S10.
[21]
Bradley A. Perkins, C. Thomas Caskey, Pamila Brar, Eric Dec, David S. Karow, Andrew M. Kahn, Ying-Chen Claire Hou, Naisha Shah, Debbie Boeldt, Erin Coughlin, Gabby Hands, Victor Lavrenko, James Yu, Andrea Procko, Julia Appis, Anders M. Dale, Lining Guo, Thomas J. Jönsson, Bryan M. Wittmann, Istvan Bartha, Smriti Ramakrishnan, Axel Bernal, James B. Brewer, Suzanne Brewerton, William H. Biggs, Yaron Turpaz, and J. Craig Venter. 2018. Precision medicine screening using whole-genome sequencing and advanced imaging to identify disease risk in adults. Proceedings of the National Academy of Sciences 115, 14 (2018), 3686--3691.
[22]
Victoria Popic, Raheleh Salari, Iman Hajirasouliha, Dorna Kashef-Haghighi, Robert B West, and Serafim Batzoglou. 2015. Fast and scalable inference of multi-sample cancer lineages. Genome Biology 16, 1 (2015), 91.
[23]
Maochun Qin, Biao Liu, Jeffrey M Conroy, Carl D Morrison, Qiang Hu, Yubo Cheng, Mitsuko Murakami, Adekunle O Odunsi, Candace S Johnson, Lei Wei, et al. 2015. SCNVSim: somatic copy number variation and structure variation simulator. BMC bioinformatics 16, 1 (2015), 66.
[24]
Benjamin J. Raphael, Jason R. Dobson, Layla Oesper, and Fabio Vandin. 2014. Identifying driver mutations in sequenced cancer genomes: computational approaches to enable precision medicine. Genome Medicine 6, 1 (2014), 5.
[25]
Claus-Peter Schnorr and Martin Euchner. 1994. Lattice basis reduction: Improved practical algorithms and solving subset sum problems. Mathematical programming 66, 1--3 (1994), 181--199.
[26]
Ronglai Shen and Venkatraman E. Seshan. 2016. FACETS: allele-specific copy number and clonal heterogeneity analysis tool for high-throughput DNA sequencing. Nucleic Acids Research 44, 16 (2016), e131.
[27]
Giorgio Stanta and Serena Bonin. 2018. Overview on Clinical Relevance of Intra- Tumor Heterogeneity. Frontiers in Medicine 5 (2018), 85.
[28]
Philip J. Stephens, David J. McBride, Meng-Lay Lin, Ignacio Varela, Erin D. Pleasance, Jared T. Simpson, Lucy A. Stebbings, Catherine Leroy, Sarah Edkins, Laura J. Mudie, Chris D. Greenman, Mingming Jia, Calli Latimer, JonW. Teague, KingWai Lau, John Burton, Michael A. Quail, Harold Swerdlow, Carol Churcher, Rachael Natrajan, Anieta M. Sieuwerts, John W. M. Martens, Daniel P. Silver, Anita Langerød, Hege E. G. Russnes, John A. Foekens, Jorge S. Reis-Filho, Laura van 't Veer, Andrea L. Richardson, Anne-Lise Børresen-Dale, Peter J. Campbell, P. Andrew Futreal, and Michael R. Stratton. 2009. Complex landscapes of somatic rearrangement in human breast cancer genomes. Nature 462 (24 12 2009), 1005 EP --.
[29]
Xiao-xiao Sun and Qiang Yu. 2015. Intra-tumor heterogeneity of cancer cells and its implications for cancer treatment. Acta Pharmacologica Sinica 36, 10 (10 2015), 1219--1227.
[30]
Bert Vogelstein, Nickolas Papadopoulos, Victor E Velculescu, Shibin Zhou, Luis A Diaz, and KennethWKinzler. 2013. Cancer genome landscapes. Science 339, 6127 (2013), 1546--1558 0036--8075.
[31]
Weiran Wang and Miguel A Carreira-Perpinán. 2013. Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application. arXiv preprint arXiv:1309.1541 (2013).
[32]
Amy H Yang, Dhruv Kaushal, Stevens K Rehen, Kristin Kriedt, Marcy A Kingsbury, Michael J McConnell, and Jerold Chun. 2003. Chromosome segregation defects contribute to aneuploidy in normal neural progenitor cells. Journal of Neuroscience 23, 32 (2003), 10454--10462.
  1. Reconstructing Intra-Tumor Heterogeneity via Convex Optimization and Branch-and-Bound Search

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    BCB '19: Proceedings of the 10th ACM International Conference on Bioinformatics, Computational Biology and Health Informatics
    September 2019
    716 pages
    ISBN:9781450366663
    DOI:10.1145/3307339
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 04 September 2019

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. branch-and-bound search
    2. convex optimization
    3. high-throughput sequencing
    4. tumor heterogeneity

    Qualifiers

    • Short-paper

    Funding Sources

    Conference

    BCB '19
    Sponsor:

    Acceptance Rates

    BCB '19 Paper Acceptance Rate 42 of 157 submissions, 27%;
    Overall Acceptance Rate 254 of 885 submissions, 29%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • 0
      Total Citations
    • 285
      Total Downloads
    • Downloads (Last 12 months)79
    • Downloads (Last 6 weeks)17
    Reflects downloads up to 26 Jan 2025

    Other Metrics

    Citations

    View Options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Login options

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media