A new algorithm for the reconstruction of near-perfect binary phylogenetic trees

Abstract: "In this paper, we consider the problem of reconstructing near-perfect phylogenetic trees using binary characters. A perfect phylogeny assumes that every character mutates at most once in the evolutionary tree. The algorithm for reconstructing a perfect phylogeny for binary characters is computationally efficient but impractical in most real settings. A near-perfect phylogeny relaxes this assumption by allowing characters to mutate a constant number of times. We show that if the number of additional mutations required by the near-perfect phylogeny is bounded by q, then we can reconstruct the optimal near-perfect phylogenetic tree in time 2[superscript O](q┬▓)nm┬▓ 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[superscript O(q)]2[superscript O(q┬▓r┬▓)] where r is the number of states per character (2 for binary). This improvement could lead to the first practical phylogenetic tree reconstruction algorithm that is both computationally feasible and biologically meaningful. We finally outline a method to improve the bound to q[superscript O(q)]nm┬▓."