New Algorithm Reconstructs Tumor Cell Family Trees Under a Strict Evolutionary Rule

Cancer is not a single disease within a patient but a population of competing cell lineages, each carrying its own collection of mutations. Reconstructing the family tree of these clones from sequencing data is a central challenge in tumor phylogenetics, and the choice of evolutionary model determines which trees are even considered possible. A new study published in Algorithms for Molecular Biology introduces Dolphyin, a combinatorial algorithm designed to infer phylogenies under the 1-Dollo model, in which every single-nucleotide variant may be gained only once but lost at most one time during a tumor’s evolution.

The 1-Dollo, or persistent phylogeny, model has attracted attention precisely because it sits between two extremes. Under the classical perfect phylogeny model, no mutation can ever be lost once gained, an assumption that real tumors routinely violate. Copy-number aberrations, for example, can delete stretches of the genome and erase single-nucleotide variants that were previously acquired. At the other extreme, allowing unlimited losses makes the inference problem computationally intractable in known ways. The 1-Dollo model permits exactly one loss per character, capturing the biological reality that variants are rarely reintroduced but are frequently erased. Despite more than two decades of study, the computational hardness of the general 1-Dollo phylogeny problem has remained an open question.

The new work, by Daniel W. Feng and Mohammed El-Kebir, delivers two kinds of results: theoretical characterizations and a practical algorithm. On the theory side, the authors prove that a restricted version of the problem has a surprisingly clean solution. When the required phylogeny must be linear, meaning that after removing the leaves corresponding to sequenced cells the remaining tree forms a simple chain with no branching, the problem becomes equivalent to checking whether the input binary matrix has the consecutive ones property. That property, which asks whether the rows of a matrix can be permuted so that the 1s in every column appear consecutively, can be verified in O(mn) time using PQ trees, where m is the number of cells and n the number of variants.

This equivalence has immediate consequences. The authors show that natural extensions of the linear problem, such as requiring the phylogeny to be rooted at a specified state vector or to terminate at one, remain solvable in polynomial time through a matrix transformation. But the picture darkens for more practical variants. Determining the minimum number of false negative entries, positions where a mutation present in a cell was recorded as absent, that must be corrected to admit a linear 1-Dollo phylogeny is NP-hard, because the equivalent consecutive ones problem is itself NP-hard. Even allowing two gains and two losses per character in the linear setting is NP-hard. The general 1-Dollo problem, without the linearity constraint, remains open.

The key to handling branching phylogenies is a recursive decomposition. Any 1-Dollo phylogeny can be split at its first branching point, the internal node where cell evolution diverges into multiple non-leaf lineages. The path from the root to that branching point, together with the characters gained and lost along it, forms a linear phylogeny on a subset of taxa and characters. Each of the branching point’s outgoing edges then defines a smaller 1-Dollo phylogeny problem on a submatrix of the data. The authors prove that this decomposition is not just necessary but sufficient: a matrix admits a 1-Dollo phylogeny rooted at a given state if and only if there exists a choice of taxa and gained and lost character sets satisfying an agreement condition, such that the resulting submatrices each admit their own phylogenies.

Dolphyin turns this characterization into an algorithm. It exhaustively searches over possible choices of the taxa set and the gained and lost character sets, checks whether each choice is in agreement with the data, computes a block diagonal decomposition of a transformed complement matrix, and recursively solves the resulting subproblems. A heuristic called FindLinearChains accelerates the search by precomputing linear chains of taxa that are guaranteed to satisfy the 1-Dollo model, restricting the exhaustive enumeration to candidates already known to yield a valid linear phylogeny. The worst-case running time remains super-exponential, O(√2^[m(m−1)+2n(n−1)]·mn), though under an assumption of balanced recursive decompositions the bound improves to an exponential form, O(min(m,n)·4^[m+2n]·mn).

To test the algorithm, the authors implemented it in C++11 and ran it on 540 simulated errorless single-cell datasets with known 1-Dollo ground truth phylogenies, spanning 25, 50, or 100 cells by 25, 50, or 100 variants, with 60 datasets per size combination. These datasets had previously been used to benchmark SPhyR, an integer linear programming-based solver for the k-Dollo problem. Dolphyin found valid errorless phylogenies on all 540 instances and remained runtime-competitive with SPhyR across input sizes, with identical median running times of 0.019 seconds for both methods. Dolphyin was slightly faster on the smallest instances, 0.008 versus 0.0115 seconds for 25 by 25 matrices, while SPhyR was slightly faster on the largest, 0.0945 versus 0.122 seconds for 100 by 100 matrices.

The authors also probed the algorithm’s behavior on data guaranteed to have no solution. They augmented 60 simulated 50 by 50 datasets with a four-by-four submatrix that is the smallest known matrix admitting no 1-Dollo phylogeny, then ran Dolphyin on truncated versions ranging from 5 by 5 to 30 by 30, for 600 matrices in total. Without explicitly searching for that forbidden pattern, Dolphyin correctly reported that no errorless phylogeny existed for every one of the 600 matrices. Proving infeasibility took longer than finding solutions, with median runtimes rising from 0.013 seconds at size 5 to 0.589 seconds at size 30, and the spread of runtimes widening from a range of 0.010 seconds to 4.007 seconds, roughly exponential growth that the authors note reflects the algorithm’s analytically derived worst-case behavior.

Real sequencing data contains errors, most notably false negatives caused by allelic dropout in single-cell DNA sequencing. The authors adapted Dolphyin with a probabilistic error correction step: in each recursive call it randomly considers pairs of taxa, and if their normalized Hamming distance falls below a threshold e, it alters characters seen in one taxon to be present in both. Starting from e equal to zero, the threshold is increased in steps of 0.2 until a solution is found within a ten second limit. On 180 simulated datasets with false negatives introduced at a ground truth rate of 0.05, chosen to match the estimated median allelic dropout rate of 5.8 percent for the Mission Bio Tapestri platform, Dolphyin in the median case inferred phylogenies with error rates at or below the true rate, and the inferred rate decreased as the number of restarts increased from one to ten.

Finally, the authors applied Dolphyin to 99 real acute myeloid leukemia single-cell sequencing datasets, processed in a previous study, with five restarts per dataset. After removing cells with unsequenced or unknown characters, the datasets averaged 5460 cells and 4.42 variants each. Taking the minimum inferred error rate across restarts, Dolphyin produced 1-Dollo phylogenies for 55 of the 99 datasets, slightly more than half, with an estimated false negative rate at or below 0.06, approximately matching the sequencing technology’s median allelic dropout rate of 5.8 percent. For the remaining datasets, the authors speculate that false positives, a need for more than one loss per character, or insufficient restarts may explain the higher inferred error rates. As a detailed example, on dataset AML 51 with 7163 cells and 6 variants, Dolphyin inferred a near-linear phylogeny with a single internal node of outdegree three furthest from the root, at a false negative error rate of 0.0639. The authors present the work as both a contribution to the theoretical understanding of the persistent phylogeny problem and a practical step toward applying strict evolutionary models to real tumor sequencing data, while acknowledging that better heuristics will be needed to scale to datasets with thousands of cells or characters when the data does not fit the model.

Subject of Research: A combinatorial algorithm and theoretical characterization for inferring 1-Dollo phylogenies from single-cell cancer sequencing data

Article Title: Dolphyin: a combinatorial algorithm for identifying 1-Dollo phylogenies in cancer

Article References: Feng, D. W., & El-Kebir, M. (2026). Dolphyin: a combinatorial algorithm for identifying 1-Dollo phylogenies in cancer. Algorithms for Molecular Biology, 21(1), Article 11. https://doi.org/10.1186/s13015-026-00303-2

Image Credits: AI Generated

DOI: 10.1186/s13015-026-00303-2

Keywords: cancer phylogenetics, 1-Dollo model, persistent phylogeny, single-cell sequencing, consecutive ones property, computational complexity, NP-hard, acute myeloid leukemia, false negative errors, combinatorial algorithm, SPhyR, tumor evolution