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.