FPT Algorithms for Binary Near-Perfect Phylogenetic Trees

We consider the problem of reconstructing near-perfect phylogenetic trees using binary character states (referred to as BNPP). A perfect phylogeny assumes that every character mutates at most once in the evolutionary tree, yielding an algorithm for binary character states that is computationally efficient but not robust to imperfections in real data. A near-perfect phylogeny relaxes the perfect phylogeny assumption by allowing at most a constant number of additional mutations. In this paper, we present a simple lower bound for the size of an optimal phylogeny, develop two algorithms for constructing optimal phylogenies and show experimental results for one of the variants. The first algorithm is intuitive and reconstructs an optimal near-perfect phylogenetic tree in time (q + κ) O(q) nm + O(nm 2) where κ is the number of characters that share four gametes with some other character. A second, more involved algorithm shows the problem to be fixed parameter tractable in q by solving it in time q O(q) nm + O(nm 2) where n is the number of taxa and m is the number of characters. This is a significant improvement over the previous best result of nm O(q) 2 O(q2 s 2) , where s is the number of states per character (2 for binary). We implement the first algorithm and show that it finds the optimal solution quickly for a selection of population dataset