Sapling: Inferring and Summarizing Tumor Phylogenies from Bulk Data Using Backbone Trees

Yuanyuan Qi, Mohammed El-Kebir

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Cancer phylogenies are key to understanding tumor evolution. There exist many important downstream analyses that take as input a single or a small number of trees. However, due to uncertainty, one typically infers many, equally-plausible phylogenies from bulk DNA sequencing data of tumors. We introduce Sapling, a heuristic method to solve the Backbone Tree Inference from Reads problem, which seeks a small set of backbone trees on a smaller subset of mutations that collectively summarize the entire solution space. Sapling also includes a greedy algorithm to solve the Backbone Tree Expansion from Reads problem, which aims to expand an inferred backbone tree into a full tree. We prove that both problems are NP-hard. On simulated and real data, we demonstrate that Sapling is capable of inferring high-quality backbone trees that adequately summarize the solution space and that can be expanded into full trees.

Original languageEnglish (US)
Title of host publication24th International Workshop on Algorithms in Bioinformatics, WABI 2024
EditorsSolon P. Pissis, Wing-Kin Sung
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959773409
DOIs
StatePublished - Aug 2024
Event24th International Workshop on Algorithms in Bioinformatics, WABI 2024 - London, United Kingdom
Duration: Sep 2 2024Sep 4 2024

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume312
ISSN (Print)1868-8969

Conference

Conference24th International Workshop on Algorithms in Bioinformatics, WABI 2024
Country/TerritoryUnited Kingdom
CityLondon
Period9/2/249/4/24

Keywords

  • Cancer
  • consensus
  • intra-tumor heterogeneity
  • maximum agreement

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Sapling: Inferring and Summarizing Tumor Phylogenies from Bulk Data Using Backbone Trees'. Together they form a unique fingerprint.

Cite this