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

ABSTRACT: The last decade of phylogenetics has seen the development of many methods that leverage constraints plus dynamic programming. The goal of this algorithmic technique is to produce a phylogeny that is optimal with respect to some objective function and that lies within a constrained version of tree space. The popular species tree estimation method ASTRAL, for example, returns a tree that (1) maximizes the quartet score computed with respect to the input gene trees and that (2) draws its branches (bipartitions) from the input constraint set. This technique has yet to be used for parsimony problems where the input are binary characters, sometimes with missing values. Here, we introduce the clade-constrained character parsimony problem and present an algorithm that solves this problem for the D

SUBMITTER: Dai J 

PROVIDER: S-EPMC10775561 | biostudies-literature | 2024 Jan

REPOSITORIES: biostudies-literature