Cancer is not a single disease unfolding inside a single tumor. As cells divide, somatic mutations accumulate in different lineages, producing a population of genetically distinct clones within the same mass of tissue. Researchers represent this history with a phylogeny, a rooted tree whose nodes correspond to clones, and they rely on such trees for downstream analyses ranging from immunotherapy and cancer vaccine design to the study of metastasis and evolutionary trajectories. The trouble is that bulk DNA sequencing, the workhorse technology that reads mixed subpopulations of cells, rarely delivers one unambiguous tree. Instead, deconvolving bulk measurements can yield a large solution space of equally plausible phylogenies, and downstream methods that expect a single tree, or just a handful, are left without a usable answer.
A new open-access study published in the journal Algorithms for Molecular Biology on 18 February 2026 tackles this mismatch head-on. Yuanyuan Qi, Henri Schmidt and Mohammed El-Kebir introduce Sapling, a computational method that takes read count data from bulk DNA sequencing and returns a small set of backbone trees on a subset of mutations that collectively summarize the space of plausible cancer phylogenies. The work frames this summarization as two formal optimization problems, proves that both are computationally intractable in a precise mathematical sense, and then develops heuristic algorithms that, in simulations, mostly find optimal solutions and, on real lung cancer data, condense sprawling solution spaces into a few interpretable trees.
The core idea is the backbone tree. Given a candidate phylogeny on a full set of mutations, a backbone tree retains only a chosen subset of mutations while preserving their ancestral relationships: one mutation appears on the path from the root to another in the backbone exactly when it does in the full tree. Mathematically, the full tree is a subdivision or expansion of the backbone, obtained by contracting the nodes corresponding to mutations outside the subset. The authors note that this concept resembles the maximum-agreement subtree used in species phylogenetics, with a key distinction: tumor phylogenies are node-labeled trees, whereas species trees are leaf-labeled. A backbone tree set then consists of all backbone trees of all trees in the solution space, and because multiple full trees can project onto the same backbone, this set is never larger than the original solution space.
Choosing the mutation subset involves a genuine tradeoff. Including every mutation reproduces the entire solution space and summarizes nothing; including none or one yields a single trivial backbone tree that carries no information specific to the data. The authors formalize the two extremes as two problems. Minimum Cardinality Backbone Trees asks, for a fixed number of mutations, for the subset whose backbone tree set is as small as possible. Maximum Mutation Backbone Trees asks, for a fixed upper bound on the number of backbone trees, for the largest mutation subset that stays within that bound. In practice, the solution space of trees is not given in advance, so the authors reformulate both problems to work directly from variant and total read count matrices for mutations across samples, which may come from different regions or time points of the same tumor.
The statistical machinery behind this read-based formulation is a binomial model of variant read counts. The observed number of reads supporting a mutation in a sample depends on the total read depth and on the latent frequency of that mutation, which lies between zero and one because each bulk sample is a mixture of clones that either carry or lack the mutation. A tree constrains these frequencies through the sum condition, which requires that a parent mutation’s frequency be at least the sum of its children’s frequencies. The method approximates the probability of the read counts given a tree by finding the frequency matrix that maximizes the binomial likelihood subject to this condition, a convex optimization problem solvable in polynomial time with interior point methods. Trees whose likelihood falls within a user-specified factor of the maximum define the solution space to be summarized.
On the computational complexity side, the authors prove that both read-based backbone problems are NP-hard, even with just two samples. The proof reduces from the Perfect Phylogeny Mixture Deconvolution problem, which asks whether any tree satisfies the sum condition for a given frequency matrix and was previously shown NP-complete for two or more samples. Because exact solutions are out of reach, Sapling employs heuristics. A naive iterative expansion, which adds each new mutation at every possible location in every partial tree, fails for two reasons: the order in which mutations are considered changes the number of resulting backbones, and expanding a single node can generate an exponential number of candidate trees. Sapling’s practical version sorts mutations by their observed variant allele frequencies, so that mutations closest to the root are added first, and restricts each expansion to only a linear number of possibilities: placing the new mutation as the new root, as a new leaf, or splitting an existing edge. The authors supply a theoretical justification for the leaf-placement rule in the limit of infinite sequencing depth, showing that a mutation with a higher summed observed frequency cannot be a descendant of one with a lower summed frequency.
The evaluation begins with small, exactly solvable simulations. The authors generated 20 instances with eight mutations and two samples, and exhaustively enumerated all 2,097,152 possible rooted trees to construct the full solution space of trees within a factor of 0.9 of the maximum likelihood. These spaces ranged from 3 to 861 trees, with a median of 62.5. Sapling achieved perfect recall, meaning its backbone trees exactly matched the sets obtained by projecting the ground-truth full trees down to the same mutation subsets. Its median approximation ratio was 1, indicating optimal solutions in most cases, with a worst case of 7, where the method returned 14 backbone trees where 2 were optimal for a five-mutation subset. When constrained by a maximum number of backbone trees, the median ratio was again 1, with a minimum of 0.25 in the strictest setting of a single allowed backbone tree, where Sapling found one mutation when four were possible.
Larger simulations tested scalability. Across 60 instances with ten samples and 20, 50 or 100 mutations, Sapling’s backbone inference ran quickly on a laptop with 16 gigabytes of memory, and swapping the convex solver cvxopt for a faster alternative sped up likelihood computations by several orders of magnitude. For full-tree inference, the authors added a beam-search variant that retains only the top trees by likelihood at each iteration, and compared it against the state-of-the-art methods Orchard and fastBE. Sapling achieved higher binomial log-likelihoods than Orchard at matching beam widths, and strikingly, Sapling with a beam width of just 1 outperformed Orchard with a beam width of 100 for 50 and 100 mutations, while taking a fraction of the time, with median running times of 27.91 seconds versus 641.12 seconds. Sapling with width 1 also beat fastBE with width 100 in likelihood across all mutation regimes, which the authors attribute to fastBE approximating the likelihood with an L1 loss rather than a binomial one. Against ground truth, Sapling’s trees matched better than Orchard’s and were of similar quality to fastBE’s; at a beam width of 50 and 20 mutations, median parent-child, ancestor-descendant, CASet and DISC distances were 0.54, 0.25, 0.17 and 0.33 for Sapling versus 0.69, 0.32, 0.20 and 0.39 for Orchard.
Finally, the authors applied Sapling to the TRACERx cohort of 100 non-small-cell lung cancer patients, using the published mutation clusters, which numbered between 2 and 15 per patient, with between 1 and 7 sequencing samples. When asked to enumerate the complete solution space, Sapling found at least two trees for 26 patients under a permissive likelihood threshold and 14 patients under a stricter one. When restricted to a single backbone tree, the method still covered a median fraction of 0.75 and 0.81 of mutation clusters under the two thresholds. For patient CRUK0013, with nine mutation clusters, the single backbone tree spanned seven clusters and formed a proper subtree of the consensus tree reported by an earlier method; for patient CRUK0037, allowing two backbone trees instead of one covered an additional mutation cluster, and the resulting trees were again proper subtrees of the previously reported consensus trees. The authors caution that performance drops in the strict single-backbone case and list relaxing the infinite sites assumption, which currently excludes mutation loss, as future work. Sapling is available under an open-source license, with data and results also publicly released.
Subject of Research: Computational methods for inferring and summarizing tumor phylogenies from bulk DNA sequencing data
Article Title: Inferring and summarizing tumor phylogenies from bulk DNA data
Article References: Qi, Y., Schmidt, H., & El-Kebir, M. (2026). Inferring and summarizing tumor phylogenies from bulk DNA data. Algorithms for Molecular Biology, 21(1), Article 5. https://doi.org/10.1186/s13015-025-00295-5
Image Credits: AI Generated
DOI: 10.1186/s13015-025-00295-5
Keywords: tumor phylogenetics, cancer evolution, bulk DNA sequencing, intra-tumor heterogeneity, backbone trees, computational complexity, NP-hardness, convex optimization, simulation study, TRACERx, non-small-cell lung cancer, Sapling
News Source: Nathaniel Bowman. (October 29, 2026). New Tool Distills Tumor Family Trees Into a Few Reliable Branches. Scienmag.
