IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v320y2025i3p777-788.html
   My bibliography  Save this article

Addressing the multiplicity of optimal solutions to the Clonal Deconvolution and Evolution Problem

Author

Listed:
  • Tellaetxe-Abete, Maitena
  • Lawrie, Charles
  • Calvo, Borja

Abstract

The Clonal Deconvolution and Evolution Problem consists on unraveling the clonal structure and phylogeny of a tumor using estimated mutation frequency values obtained from multiple biopsies containing mixtures of tumor clones. In this article, we tackle the problem from an optimization perspective and we explore the number of optimal solutions for a given instance. Even in ideal scenarios without noise, we demonstrate that the Clonal Deconvolution and Evolution Problem is highly under-determined, leading to multiple solutions. Through a comprehensive analysis, we examine the factors contributing to the multiplicity of solutions. We find that as the number of samples increases, the number of optimal solutions decreases. Additionally, we explore how this phenomenon operates across various tumor topology scenarios. To address the issue of the existence of multiple solutions, we present sufficient conditions under which the problem can have a unique solution, and we propose a linear programming-based algorithm that leverages mutation orderings to generate instances with a single solution for a given topology. This algorithm encounters numerical challenges when applied to large instance sizes so, to overcome this, we propose a heuristic adaptation that enables the algorithm’s use for instances of any size.

Suggested Citation

  • Tellaetxe-Abete, Maitena & Lawrie, Charles & Calvo, Borja, 2025. "Addressing the multiplicity of optimal solutions to the Clonal Deconvolution and Evolution Problem," European Journal of Operational Research, Elsevier, vol. 320(3), pages 777-788.
  • Handle: RePEc:eee:ejores:v:320:y:2025:i:3:p:777-788
    DOI: 10.1016/j.ejor.2024.09.006
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221724007094
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.ejor.2024.09.006?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Shinichi Yachida & Siân Jones & Ivana Bozic & Tibor Antal & Rebecca Leary & Baojin Fu & Mihoko Kamiyama & Ralph H. Hruban & James R. Eshleman & Martin A. Nowak & Victor E. Velculescu & Kenneth W. Kinz, 2010. "Distant metastasis occurs late during the genetic evolution of pancreatic cancer," Nature, Nature, vol. 467(7319), pages 1114-1117, October.
    2. Mel Greaves & Carlo C. Maley, 2012. "Clonal evolution in cancer," Nature, Nature, vol. 481(7381), pages 306-313, January.
    3. Andrew C. Trapp & Renata A. Konrad, 2015. "Finding diverse optima and near-optima to binary integer programs," IISE Transactions, Taylor & Francis Journals, vol. 47(11), pages 1300-1312, November.
    4. Yoshitaka Sakamoto & Shuhei Miyake & Miho Oka & Akinori Kanai & Yosuke Kawai & Satoi Nagasawa & Yuichi Shiraishi & Katsushi Tokunaga & Takashi Kohno & Masahide Seki & Yutaka Suzuki & Ayako Suzuki, 2022. "Phasing analysis of lung cancer genomes using a long read sequencer," Nature Communications, Nature, vol. 13(1), pages 1-17, December.
    5. Juhee Lee & Peter Müller & Subhajit Sengupta & Kamalakar Gulukota & Yuan Ji, 2016. "Bayesian inference for intratumour heterogeneity in mutations and copy number variation," Journal of the Royal Statistical Society Series C, Royal Statistical Society, vol. 65(4), pages 547-563, August.
    6. Oyetunji E Ogundijo & Kaiyi Zhu & Xiaodong Wang & Dimitris Anastassiou, 2019. "A sequential Monte Carlo algorithm for inference of subclonal structure in cancer," PLOS ONE, Public Library of Science, vol. 14(1), pages 1-21, January.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Song Li & Wenbin Yu & Fei Xie & Haitao Luo & Zhimin Liu & Weiwei Lv & Duanbo Shi & Dexin Yu & Peng Gao & Cheng Chen & Meng Wei & Wenhao Zhou & Jiaqian Wang & Zhikun Zhao & Xin Dai & Qian Xu & Xue Zhan, 2023. "Neoadjuvant therapy with immune checkpoint blockade, antiangiogenesis, and chemotherapy for locally advanced gastric cancer," Nature Communications, Nature, vol. 14(1), pages 1-16, December.
    2. Yasuhiko Haga & Yoshitaka Sakamoto & Keiko Kajiya & Hitomi Kawai & Miho Oka & Noriko Motoi & Masayuki Shirasawa & Masaya Yotsukura & Shun-Ichi Watanabe & Miyuki Arai & Junko Zenkoh & Kouya Shiraishi &, 2023. "Whole-genome sequencing reveals the molecular implications of the stepwise progression of lung adenocarcinoma," Nature Communications, Nature, vol. 14(1), pages 1-19, December.
    3. Lichun Ma & Sophia Heinrich & Limin Wang & Friederike L. Keggenhoff & Subreen Khatib & Marshonna Forgues & Michael Kelly & Stephen M. Hewitt & Areeba Saif & Jonathan M. Hernandez & Donna Mabry & Roman, 2022. "Multiregional single-cell dissection of tumor and immune cells reveals stable lock-and-key features in liver cancer," Nature Communications, Nature, vol. 13(1), pages 1-17, December.
    4. Jesse Kreger & Jazlyn A. Mooney & Darryl Shibata & Adam L. MacLean, 2024. "Developmental hematopoietic stem cell variation explains clonal hematopoiesis later in life," Nature Communications, Nature, vol. 15(1), pages 1-12, December.
    5. Adam C. Weiner & Marc J. Williams & Hongyu Shi & Ignacio Vázquez-García & Sohrab Salehi & Nicole Rusk & Samuel Aparicio & Sohrab P. Shah & Andrew McPherson, 2024. "Inferring replication timing and proliferation dynamics from single-cell DNA sequencing data," Nature Communications, Nature, vol. 15(1), pages 1-19, December.
    6. Marco, Nicholas & Şentürk, Damla & Jeste, Shafali & DiStefano, Charlotte C. & Dickinson, Abigail & Telesca, Donatello, 2024. "Flexible regularized estimation in high-dimensional mixed membership models," Computational Statistics & Data Analysis, Elsevier, vol. 194(C).
    7. Julio Diaz Caballero & Rachel M. Wheatley & Natalia Kapel & Carla López-Causapé & Thomas Van der Schalk & Angus Quinn & Liam P. Shaw & Lois Ogunlana & Claudia Recanatini & Basil Britto Xavier & Leen T, 2023. "Mixed strain pathogen populations accelerate the evolution of antibiotic resistance in patients," Nature Communications, Nature, vol. 14(1), pages 1-12, December.
    8. Noushin Niknafs & Violeta Beleva-Guthrie & Daniel Q Naiman & Rachel Karchin, 2015. "SubClonal Hierarchy Inference from Somatic Mutations: Automatic Reconstruction of Cancer Evolutionary Trees from Multi-region Next Generation Sequencing," PLOS Computational Biology, Public Library of Science, vol. 11(10), pages 1-26, October.
    9. Chengdi Wang & Jingwei Li & Jingyao Chen & Zhoufeng Wang & Guonian Zhu & Lujia Song & Jiayang Wu & Changshu Li & Rong Qiu & Xuelan Chen & Li Zhang & Weimin Li, 2025. "Multi-omics analyses reveal biological and clinical insights in recurrent stage I non-small cell lung cancer," Nature Communications, Nature, vol. 16(1), pages 1-19, December.
    10. Albert H Gough & Ning Chen & Tong Ying Shun & Timothy R Lezon & Robert C Boltz & Celeste E Reese & Jacob Wagner & Lawrence A Vernetti & Jennifer R Grandis & Adrian V Lee & Andrew M Stern & Mark E Schu, 2014. "Identifying and Quantifying Heterogeneity in High Content Analysis: Application of Heterogeneity Indices to Drug Discovery," PLOS ONE, Public Library of Science, vol. 9(7), pages 1-16, July.
    11. Saakian, David B. & Vardanyan, Edgar & Yakushkina, Tatiana, 2020. "Evolutionary model with recombination and randomly changing fitness landscape," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 541(C).
    12. Joseph G. Kern & Andrew M. Tilston-Lunel & Anthony Federico & Boting Ning & Amy Mueller & Grace B. Peppler & Eleni Stampouloglou & Nan Cheng & Randy L. Johnson & Marc E. Lenburg & Jennifer E. Beane & , 2022. "Inactivation of LATS1/2 drives luminal-basal plasticity to initiate basal-like mammary carcinomas," Nature Communications, Nature, vol. 13(1), pages 1-13, December.
    13. Erfan Mehmanchi & Andrés Gómez & Oleg A. Prokopyev, 2019. "Fractional 0–1 programs: links between mixed-integer linear and conic quadratic formulations," Journal of Global Optimization, Springer, vol. 75(2), pages 273-339, October.
    14. Sheli L Ostrow & Ruth Barshir & James DeGregori & Esti Yeger-Lotem & Ruth Hershberg, 2014. "Cancer Evolution Is Associated with Pervasive Positive Selection on Globally Expressed Genes," PLOS Genetics, Public Library of Science, vol. 10(3), pages 1-11, March.
    15. Christopher R S Banerji & Simone Severini & Carlos Caldas & Andrew E Teschendorff, 2015. "Intra-Tumour Signalling Entropy Determines Clinical Outcome in Breast and Lung Cancer," PLOS Computational Biology, Public Library of Science, vol. 11(3), pages 1-23, March.
    16. Seth Haney & Jessica Konen & Adam I Marcus & Maxim Bazhenov, 2018. "The complex ecosystem in non small cell lung cancer invasion," PLOS Computational Biology, Public Library of Science, vol. 14(5), pages 1-21, May.
    17. Yukinari Haraoka & Yuki Akieda & Yuri Nagai & Chihiro Mogi & Tohru Ishitani, 2022. "Zebrafish imaging reveals TP53 mutation switching oncogene-induced senescence from suppressor to driver in primary tumorigenesis," Nature Communications, Nature, vol. 13(1), pages 1-15, December.
    18. Anna A Schönherz & Julie Støve Bødker & Alexander Schmitz & Rasmus Froberg Brøndum & Lasse Hjort Jakobsen & Anne Stidsholt Roug & Marianne T Severinsen & Tarec C El-Galaly & Paw Jensen & Hans Erik Joh, 2020. "Normal myeloid progenitor cell subset-associated gene signatures for acute myeloid leukaemia subtyping with prognostic impact," PLOS ONE, Public Library of Science, vol. 15(4), pages 1-21, April.
    19. Nedim Durmus & Yongzhao Shao & Alan A. Arslan & Yian Zhang & Sultan Pehlivan & Maria-Elena Fernandez-Beros & Lisette Umana & Rachel Corona & Sheila Smyth-Giambanco & Sharon A. Abbott & Joan Reibman, 2020. "Characteristics of Cancer Patients in the World Trade Center Environmental Health Center," IJERPH, MDPI, vol. 17(19), pages 1-15, October.
    20. Peng V. Wu & Matt Fish & Florette K. Hazard & Chunfang Zhu & Sujay Vennam & Hannah Walton & Dhananjay Wagh & John Coller & Joanna Przybyl & Maurizio Morri & Norma Neff & Robert B. West & Roel Nusse, 2024. "A developmental biliary lineage program cooperates with Wnt activation to promote cell proliferation in hepatoblastoma," Nature Communications, Nature, vol. 15(1), pages 1-19, December.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:320:y:2025:i:3:p:777-788. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.