DROPS

Document

DOI: 10.4230/LIPIcs.WABI.2026.10

Exact and Efficient Inference of Tumor Phylogenies via Novel Pruning Techniques

Authors: Juan Luque, Jacob Gilbert, Arjun Subramanian, Aravind Srinivasan, Salem Malikic, and S. Cenk Sahinalp

Published in: LIPIcs, Volume 390, 26th International Conference on Algorithms for Bioinformatics (WABI 2026)

Abstract

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.

Cite as

Juan Luque, Jacob Gilbert, Arjun Subramanian, Aravind Srinivasan, Salem Malikic, and S. Cenk Sahinalp. Exact and Efficient Inference of Tumor Phylogenies via Novel Pruning Techniques. In 26th International Conference on Algorithms for Bioinformatics (WABI 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 390, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{luque_et_al:LIPIcs.WABI.2026.10,
  author =	{Luque, Juan and Gilbert, Jacob and Subramanian, Arjun and Srinivasan, Aravind and Malikic, Salem and Sahinalp, S. Cenk},
  title =	{{Exact and Efficient Inference of Tumor Phylogenies via Novel Pruning Techniques}},
  booktitle =	{26th International Conference on Algorithms for Bioinformatics (WABI 2026)},
  pages =	{10:1--10:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-446-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{390},
  editor =	{El-Mabrouk, Nadia and Vandin, Fabio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2026.10},
  URN =		{urn:nbn:de:0030-drops-275141},
  doi =		{10.4230/LIPIcs.WABI.2026.10},
  annote =	{Keywords: Branch and Bound, Vertex Cover, Linear Programming, Tumor Evolution, Single-Cell Sequencing}
}

Search Results

Documents authored by Subramanian, Arjun

Exact and Efficient Inference of Tumor Phylogenies via Novel Pruning Techniques

Abstract

Cite as

Thanks for your feedback!

Could not send message