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. 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.
    2. 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.
    3. 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.
    4. Mel Greaves & Carlo C. Maley, 2012. "Clonal evolution in cancer," Nature, Nature, vol. 481(7381), pages 306-313, January.
    5. 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.
    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. 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.
    2. 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).
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. Shravana kumar chinnikatti, 2017. "Cancer and its Genomics in Transformation Era," Cancer Therapy & Oncology International Journal, Juniper Publishers Inc., vol. 7(2), pages 25-26, September.
    10. Duy Pham & Xiao Tan & Brad Balderson & Jun Xu & Laura F. Grice & Sohye Yoon & Emily F. Willis & Minh Tran & Pui Yeng Lam & Arti Raghubar & Priyakshi Kalita-de Croft & Sunil Lakhani & Jana Vukovic & Ma, 2023. "Robust mapping of spatiotemporal trajectories and cell–cell interactions in healthy and diseased tissues," Nature Communications, Nature, vol. 14(1), pages 1-25, December.
    11. Xiaodong Liu & Ke Zhang & Neslihan A. Kaya & Zhe Jia & Dafei Wu & Tingting Chen & Zhiyuan Liu & Sinan Zhu & Axel M. Hillmer & Torsten Wuestefeld & Jin Liu & Yun Shen Chan & Zheng Hu & Liang Ma & Li Ji, 2024. "Tumor phylogeography reveals block-shaped spatial heterogeneity and the mode of evolution in Hepatocellular Carcinoma," Nature Communications, Nature, vol. 15(1), pages 1-14, December.
    12. Juan S. Borrero & Colin Gillen & Oleg A. Prokopyev, 2017. "Fractional 0–1 programming: applications and algorithms," Journal of Global Optimization, Springer, vol. 69(1), pages 255-282, September.
    13. Caravagna Giulio, 2020. "Measuring evolutionary cancer dynamics from genome sequencing, one patient at a time," Statistical Applications in Genetics and Molecular Biology, De Gruyter, vol. 19(4-6), pages 1-12, December.
    14. Patrick Nathan Lawlor & Tomer Kalisky & Robert Rosner & Marsha Rich Rosner & Konrad Paul Kording, 2014. "Conceptualizing Cancer Drugs as Classifiers," PLOS ONE, Public Library of Science, vol. 9(9), pages 1-10, September.
    15. Jolanda Sarno & Pablo Domizi & Yuxuan Liu & Milton Merchant & Christina Bligaard Pedersen & Dorra Jedoui & Astraea Jager & Garry P. Nolan & Giuseppe Gaipa & Sean C. Bendall & Felice-Alessio Bava & Kar, 2023. "Dasatinib overcomes glucocorticoid resistance in B-cell acute lymphoblastic leukemia," Nature Communications, Nature, vol. 14(1), pages 1-15, December.
    16. Richard L Church & Carlos A Baez, 2020. "Generating optimal and near-optimal solutions to facility location problems," Environment and Planning B, , vol. 47(6), pages 1014-1030, July.
    17. Yuxuan Liu & Zhimin Gu & Hui Cao & Pranita Kaphle & Junhua Lyu & Yuannyu Zhang & Wenhuo Hu & Stephen S. Chung & Kathryn E. Dickerson & Jian Xu, 2021. "Convergence of oncogenic cooperation at single-cell and single-gene levels drives leukemic transformation," Nature Communications, Nature, vol. 12(1), pages 1-17, December.
    18. 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.
    19. 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.
    20. 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.

    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.