2026-08-27T21:20:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27514 2026-08-27T06:04:07Z ddc:004 open_access

Exact and Efficient Inference of Tumor Phylogenies via Novel Pruning Techniques Luque, Juan Gilbert, Jacob Subramanian, Arjun Srinivasan, Aravind Malikic, Salem Sahinalp, S. Cenk Branch and Bound Vertex Cover Linear Programming Tumor Evolution Single-Cell Sequencing Reconstructing the evolutionary history of tumors using single-cell sequencing (SCS) data presents significant computational challenges. Existing approaches are either computationally intractable for emerging large-scale datasets or rely on heuristics that lack optimality guarantees. In this work, we propose a novel, time-efficient algorithm that constructs the phylogenetic tree of tumor evolution with a provable guarantee of optimality. Our main result is a branch-and-bound algorithm that reconstructs the most likely tumor evolutionary history up to two orders of magnitude faster than the previous best algorithm. To achieve this, we use efficient and well-known 2-approximation algorithms for the Vertex Cover problem to prune the branch-and-bound tree effectively. Unlike previous works' polynomial-time branch-and-bound bounding strategies, our bounding algorithm provides strong worst-case theoretical guarantees, leading to faster reconstruction of the tumor evolution. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Juan Luque and Jacob Gilbert and Arjun Subramanian and Aravind Srinivasan and Salem Malikic and S. Cenk Sahinalp 2026 Is Part Of LIPIcs, Volume 390, 26th International Conference on Algorithms for Bioinformatics (WABI 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WABI.2026.10 urn:nbn:de:0030-drops-275141 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2026.10 eng https://creativecommons.org/licenses/by/4.0/legalcode