Title :
Refining Phylogenetic Trees Given Additional Data: An Algorithm Based on Parsimony
Author :
Wu, Taoyang ; Moulton, Vincent ; Steel, Mike
Author_Institution :
Dept. of Comput. Sci. & Sch. of Math. Sci., Univ. of London, London
Abstract :
Given a set X of taxa, a phylogenetic X-tree T that is only partially resolved, and a collection of characters on X, we consider the problem of finding a resolution (refinement) of T that minimizes the parsimony score of the given characters. Previous work has shown that this problem has a polynomial time solution provided certain strong constraints are imposed on the input. In this paper we provide a new algorithm for this problem, and show that it is fixed parameter tractable under more general conditions.
Keywords :
biology computing; trees (mathematics); parsimony score; phylogenetic X-tree; phylogenetic trees; polynomial time solution; Combinatorial algorithms; Life and Medical Sciences; Algorithms; Computational Biology; Evolution; Models, Genetic; Phylogeny;
Journal_Title :
Computational Biology and Bioinformatics, IEEE/ACM Transactions on
DOI :
10.1109/TCBB.2008.100
