Dollo-CDP: a polynomial-time algorithm for the clade-constrained large Dollo parsimony problem.

Area of Science:

• Phylogenetics and computational biology
• Algorithm development for evolutionary analysis
• Molecular evolution and bioinformatics

Background:

• Phylogenetic methods increasingly use constraints and dynamic programming for optimal tree construction.
• The species tree method ASTRAL exemplifies this by maximizing quartet scores and using input gene tree bipartitions.
• Parsimony problems with binary characters and missing data have not yet fully adopted these constraint-based techniques.

Purpose of the Study:

• Introduce the clade-constrained character parsimony problem for binary characters.
• Present an efficient algorithm to solve the Dollo parsimony problem with clade constraints.
• Implement and evaluate the algorithm in a software package (Dollo-CDP) for practical phylogenetic analysis.

Main Methods:

• Developed a novel algorithm for clade-constrained Dollo parsimony with a time complexity of O(nk|C|).
• Implemented the algorithm in the Dollo-CDP software package.
• Evaluated performance on retroelement insertion data for bats, birds, toothed whales, and simulated datasets.

Main Results:

• Dollo-CDP improves upon heuristic search by often finding better scoring trees.
• The software scales to larger datasets than branch-and-bound methods while retaining an optimality guarantee.
• The algorithm is adaptable to Camin-Sokal parsimony but not Fitch parsimony.

Conclusions:

• Clade-constrained parsimony offers a powerful approach for phylogenetic inference.
• Dollo-CDP provides an efficient and scalable solution for Dollo parsimony with constraints.
• The developed method has implications for tumor phylogenetics and species evolution studies, particularly with low-homoplasy data.