On a Mirkin-Muchnik-Smith Conjecture for Comparing Molecular Phylogenies
Author:
- 1 January 1997
- journal article
- editorial
- Published by SAGE Publications in Journal of Computational Biology
- Vol. 4 (2) , 177-187
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 14 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
- On Finding Lowest Common Ancestors: Simplification and ParallelizationSIAM Journal on Computing, 1988
- 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