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

Maitena Tellaetxe-Abete, Charles Lawrie and Borja Calvo

European Journal of Operational Research, 2025, vol. 320, issue 3, 777-788

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.

Keywords: Bioinformatics; Clonal deconvolution and evolution problem; Tumor phylogenetics; Combinatorial algorithm; Linear programming (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221724007094
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:320:y:2025:i:3:p:777-788

DOI: 10.1016/j.ejor.2024.09.006

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().