On a Mirkin-Muchnik-Smith Conjecture for Comparing Molecular Phylogenies
- 1 January 1997
- journal article
- editorial
- Published by Mary Ann Liebert Inc in Journal of Computational Biology
- Vol. 4 (2) , 177-187
- https://doi.org/10.1089/cmb.1997.4.177
Abstract
A conjecture of Mirkin, Muchnik, and Smith is answered affirmatively which connects the inconsistency function, a biologically meaningful similarity/dissimilarity measure for a gene tree and a species tree, to the mutation cost function, a combinatorial measure based on the mapping of trees. A linear-time algorithm for computing the mutation cost function is also derived from the conjecture.Keywords
This publication has 15 references indexed in Scilit:
- Reconstruction of Ancient Molecular PhylogenyMolecular Phylogenetics and Evolution, 1996
- A Biologically Consistent Model for Comparing Molecular PhylogeniesJournal of Computational Biology, 1995
- N-trees as nestings: Complexity, similarity, and consensusJournal of Classification, 1986
- On the use of ordered sets in problems of comparison and consensus of classificationsJournal of Classification, 1986
- Comparing Trees with Pendant Vertices LabelledSIAM Journal on Applied Mathematics, 1984
- Fast Algorithms for Finding Nearest Common AncestorsSIAM Journal on Computing, 1984
- Consensus-treesBulletin of Mathematical Biology, 1981
- On the similarity of dendrogramsJournal of Theoretical Biology, 1978
- Comparison of labeled trees with valency threeJournal of Combinatorial Theory, Series B, 1971