Article,
Comparison of Tree-Child Phylogenetic Networks
(August 2007)
Abstract
Phylogenetic networks are a generalization of phylogenetic trees that allow
for the representation of non-treelike evolutionary events, like recombination,
hybridization, or lateral gene transfer. In this paper, we present and study a
new class of phylogenetic networks, called tree-child phylogenetic networks,
where every non-extant species has some descendant through mutation. We provide
an injective representation of these networks as multisets of vectors of
natural numbers, their path multiplicity vectors, and we use this
representation to define a distance on this class and to give an alignment
method for pairs of these networks. To the best of our knowledge, they are
respectively the first true distance and the first alignment method defined on
a meaningful class of phylogenetic networks strictly extending the class of
phylogenetic trees. Simple, polynomial algorithms for reconstructing a
tree-child phylogenetic network from its path multiplicity vectors, for
computing the distance between two tree-child phylogenetic networks, and for
aligning a pair of tree-child phylogenetic networks, are provided, and they
have been implemented as a Perl package and a Java applet, and they are
available at <a href="http://bioinfo.uib.es/\~recerca/phylonetworks/mudistance">this http URL</a>
