Efficient algorithms for inferring evolutionary trees
Dan Gusfield · Networks · 1991
Abstract In this paper, we examine two related problems of inferring the evolutionary history of n objects, either from present characters of the objects or from several partial estimates of their evolutionary history. The first problem is called the Phylogeny problem, and second is the Tree Compatibility problem. Both of these problems are central in algorithmic approaches to the study of evolution and in other problems of historical reconstruction. In this paper, we show that both of these problems can be solved by graph theoretic methods in linear time, which is time optimal, and which is a significant improvement over existing methods.
Cited by 399 works. doi:10.1002/net.3230210104
Authors
References
- The Design and Analysis of Computer Algorithms
- Construction of Phylogenetic Trees
- A METHOD FOR DEDUCING BRANCHING SEQUENCES IN PHYLOGENY
- Clustering Algorithms.
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Numerical Methods for Inferring Evolutionary Trees
- PHYLOGENETICS: THE THEORY AND PRACTICE OF PHYLOGENETIC SYSTEMATICS
- A Consistency Test for Phylogenies Based on Contemporaneous Species
- An idealized concept of the true cladistic character
- An algebraic analysis of cladistic characters