Daniel W. Feng, Mohammed El-Kebir
BACKGROUND: Several recent cancer phylogeny inference methods have used the k-Dollo evolutionary model for single-nucleotide variants, which requires a phylogeny T on binary sequencing data matrix B such that each variant is gained once and lost at most k times. The 1-Dollo variant has been studied extensively but its hardness remains open. RESULTS: We prove that the 1-DOLLO LINEAR PHYLOGENY (1DLP) problem, where we additionally require the resulting 1-Dollo phylogeny T to be linear, is equivalent to verifying whether matrix B has the Consecutive Ones Property, which can be determined in polynomial time. We also show that some practical extensions of 1DLP, such as the minimization of false negatives, are NP-hard. We then show how to recursively decompose any 1-Dollo phylogeny T, not necessarily linear, into several 1-Dollo linear phylogenies and extend this characterization to all matrices B that admit 1-Dollo phylogenies. We use this characterization to develop Dolphyin, a new exponential-time algorithm for inferring 1-Dollo phylogenies. Dolphyin is runtime-competitive with integer linear programming-based algorithm SPhyR (El-Kebir 2018) on simulated datasets and infers 1-Dollo phylogenies with false negative sequencing error rates at or below simulated ground truth rates. We apply Dolphyin to acute myeloid leukemia datasets and find that the majority of the cancers can be explained by 1-Dollo phylogenies with error rates in line with the used sequencing technology. CONCLUSION: Our work develops a novel, combinatorial algorithm for practical inference of 1-Dollo phylogenies.