Hypothesis Testing in Perfect Phylogeny for a Bounded Number of Characters
Lists
Only you see this
Abstract
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 2 r 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 3 r 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) [10]. We also consider several variations of HTP which we either show to be solvable in polynomial time or NP-complete.
BibTeX
@inproceedings{lagergren1996hypothesis,
author = {Jens Lagergren},
title = {{Hypothesis Testing in Perfect Phylogeny for a Bounded Number of Characters}},
booktitle = {STACS},
year = {1996},
doi = {10.1007/3-540-60922-9\_49},
}Loading related content...