Hypothesis Testing in Perfect Phylogeny for a Bounded Number of Character

摘要

We introduce the hypothesis testing problem (HTP). In HTP the input is a family of species F and a hypothesis, i.e., a tree where the leaves are labeled with species from some subfamily of F. The problem is to decide whether there is a perfect phylogeny for F which agrees with the hypothesis. We show that HTP can be solved in O(m~2r~m|F|(|F|+mr)) time, where m is the number of characters and r is the maximum number of states on any character. We obtain an O(m~3r~(m+1)+|F|m~2) algorithm for the perfect phylogeny problem (PPP), as well. The fastest previously known algorithm for PPP, with fixed m, has running time O(m~(m+1)R~(m+1)+|F|m~2). We also consider several variations of HTP which we either show to be solvable in polynomial time or NP-complete.