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

Area of Science:

• Computational Biology
• Cancer Genomics
• Evolutionary Biology

Background:

• Cancer phylogeny inference often uses the k-Dollo model for genetic variants.
• The 1-Dollo model requires variants to be gained once and lost at most once.
• The computational complexity of the 1-Dollo model, especially for linear phylogenies, remained an open question.

Purpose of the Study:

• To determine the computational complexity of the 1-Dollo Linear Phylogeny (1DLP) problem.
• To develop a novel algorithm for inferring 1-Dollo phylogenies.
• To apply the developed algorithm to real-world cancer datasets.

Main Methods:

• Proved the equivalence of 1DLP to the Consecutive Ones Property, solvable in polynomial time.
• Demonstrated NP-hardness for practical extensions like minimizing false negatives.
• Developed Dolphyin, an exponential-time algorithm based on recursive decomposition of 1-Dollo phylogenies.

Main Results:

• The 1DLP problem is solvable in polynomial time.
• Dolphyin is runtime-competitive with existing methods like SPhyR.
• Dolphyin accurately infers 1-Dollo phylogenies with low false negative rates.
• Analysis of acute myeloid leukemia datasets shows many cancers fit 1-Dollo models.

Conclusions:

• A novel combinatorial algorithm, Dolphyin, was developed for practical 1-Dollo phylogeny inference.
• The findings provide a new computational tool for understanding cancer evolution.
• The study validates the utility of the 1-Dollo model in analyzing cancer genomic data.