×

Efficient algorithms for inferring evolutionary trees. (English) Zbl 0719.92015

Given an \(n\times m\) 0-1 matrix representing n objects in terms of m characters, a phylogenetic tree is a rooted tree, where each object is attached to exactly one leaf, where each of the m characters is associated with exactly one edge and where the characters on the path from root to a leaf exactly specify the character vector at the leaf. The author describes an algorithm for the construction of the phylogenetic tree working in time O(nm).
Reviewer: P.Kůrka (Praha)

MSC:

92D15 Problems related to evolution
68R10 Graph theory (including graph drawing) in computer science
05C90 Applications of graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] , and , The Design and Analysis of Computer Algorithms, Addison-Wesley(1974).
[2] Booth, J. Comput. Syst. Sci. 13 pp 335– (1976) · Zbl 0367.68034 · doi:10.1016/S0022-0000(76)80045-1
[3] Camin, Evolution 19 pp 311– (1965)
[4] Estabrook, J. Math. Biosci. 4 pp 195– (1977) · Zbl 0355.92005 · doi:10.1007/BF00275985
[5] Estabrook, J. Math. Biosci. 10 pp 367– (1980)
[6] Estabrook, Math. Biosci. 23 pp 263– (1975)
[7] Estabrook, Math. Biosci. 29 pp 000– (1976)
[8] Estabrook, Discrete Math. 16 pp 141– (1976)
[9] Farris, Systematic Zool. 28 pp 000– (1967)
[10] Felsenstein, Q. Rev. Biol. 57 pp 000– (1982)
[11] Fitch, Science 155 pp 000– (1967)
[12] The Steiner Tree Problem in Phylogeny, Technical Report 332, Department of Computer Science, Yale University, September (1984).
[13] Clustering Algorithms. Wiley, New York (1975). · Zbl 0372.62040
[14] , and (Eds.) Mathematics in the Archeological and Historical Sciences. University Press, Edinburgh (1970).
[15] McMorris, Bull. Math. Biol. 39 pp 133– (1977) · Zbl 0356.92003 · doi:10.1007/BF02462853
[16] Theoretical and Computational Considerations of the Compatiability of Qualitative Taxonomic Characters, Nato ASI Series Vol. G1 on Numerical Taxonomy, Springer-Verlag (1983).
[17] Najok, Comput. Humanities 14 pp 000– (1980)
[18] Establishing the linkage of different variants of a romanian chronical. Mathematics in archeological and Historical Science, University Press, Edinburgh ( and , Eds.) (1970).
[19] Phylogenetics: The Theory and Practice of Phylogenetic Systematics. Wiley-Interscience, New York (1981).
[20] Wilson, Systematic Zool. 14 pp 214– (1900)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.