On a Mirkin-Muchnik-Smith Conjecture for Comparing Molecular Phylogenies

Louxin Zhang (lxzhang@iss.nus.sg)

BioInformatics Center Institute of Systems Science
Heng Mui Keng Terrace Singapore 119597

A conjecture of Mirkin, Muchnik and Smith is answered affirmatively which connects the inconsistency function, a biologically meaningful dissimilarity measure for a gene and species tree, to the mutation cost function, a combinatorial measure based on mapping of trees. A linear-time algorithm for computing the inconsistency function is also derived from the conjecture.