Sapling: Inferring and Summarizing Tumor Phylogenies from Bulk Data using Backbone Trees
Qi, Y.; El-Kebir, M.
Show abstract
Cancer phylogenies are key to understanding tumor evolution. There exists many important downstream analyses that takes as input a single or 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 expanded into full trees.
Matching journals
The top 4 journals account for 50% of the predicted probability mass.
Similar papers in this journal
- Large-scale Inference of Cell Lineage Trees and Genotype Calling from Noisy Single-Cell Data Using Efficient Local Search 98%
- Haplotype-aware sequence alignment to pangenome graphs 97%
- Sequence aligners can guarantee accuracy in almost O(m log n) time: a rigorous average-case analysis of the seed-chain-extend heuristic 96%
Similar papers in this journal
Similar papers in this journal
- EssentCell: Discovering Essential Evolutionary Relations in Noisy Single-Cell Data 93%
- Detecting boolean asymmetric relationships with a loop counting technique and its implications for analyzing heterogeneity within gene expression datasets 92%
- Simple k-RF Metrics for Comparison of Labeled DAGs 92%
"Similar papers" are the closest papers from that journal in the model's embedding space. They show what the match is built on, but the ranking comes mostly from a classifier over the whole training set, not from these examples alone.