Journal
JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC
Volume 38, Issue 1, Pages 237-259Publisher
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1006/jagm.2000.1133
Keywords
quartets; phylogenetic trees; algorithms; consensus; networks
Ask authors/readers for more resources
We present fast new algorithms for constructing, phylogenetic trees from quartets (resolved trees on Four leaves). The problem is central to divide-and-conquer approaches to phylogenetic analysis and has been receiving considerable attention from the computational biology community. Most formulations of the problem are NP-hard. Here we consider a number of constrained versions that have polynomial time solutions. The main result is an algorithm for determining bounded degree trees with optimal quartet weight, subject to the constraint that the splits in the tree come from a given collection, For example, the splits in the aligned sequence data. The algorithm can search an exponentially large number of phylogenetic trees in polynomial time. We present applications of this algorithm to a number of problems in phylogenetics, including sequence analysis, construction of trees from phylogenetic networks, and consensus methods, (C) 2001 Academic Press.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available