To access the full text documents, please follow this link:

Comparison of Tree-Child Phylogenetic Networks
Cardona, Gabriel; Rosselló, Francesc; Valiente Feruglio, Gabriel Alejandro
Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics; Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals
Phylogenetic networks are a generalization of phylogenetic trees that allow for the representation of nontreelike evolutionary events, like recombination, hybridization, or lateral gene transfer. While much progress has been made to find practical algorithms for reconstructing a phylogenetic network from a set of sequences, all attempts to endorse a class of phylogenetic networks (strictly extending the class of phylogenetic trees) with a well-founded distance measure have, to the best of our knowledge and with the only exception of the bipartition distance on regular networks, failed so far. In this paper, we present and study a new meaningful class of phylogenetic networks, called tree-child phylogenetic networks, and we provide an injective representation of these networks as multisets of vectors of natural numbers, their path multiplicity vectors. We then use this representation to define a distance on this class that extends the well-known Robinson-Foulds distance for phylogenetic trees and to give an alignment method for pairs of networks in this class. 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. They have been implemented as a Perl package and a Java applet, which can be found at
Peer Reviewed
Àrees temàtiques de la UPC::Informàtica::Aplicacions de la informàtica::Bioinformàtica
Trees (Graph theory)
Genetic vectors
Biologia computacional
Arbres (Grafs, Teoria de)
Vectors genètics

Show full item record

Related documents

Other documents of the same author

Cardona, Gabriel; Llabrés, Mercè; Rosselló, Francesc; Valiente Feruglio, Gabriel Alejandro
Arenas, Miguel; Patricio, Mateus; Posada, David; Valiente Feruglio, Gabriel Alejandro
Santamaria, Monica; Fosso, Bruno; Consiglio, Arianna; De Caro, Giorigio; Grillo, Giorgio; Licciulli, Flavio; Liuni, Sabino; Marzano, Marinella; Alonso-Alemany, Daniel; Valiente Feruglio, Gabriel Alejandro; Pesole, Graziano
Alonso-Alemany, Daniel; Clemente, José C.; Jansson, Jesper; Valiente Feruglio, Gabriel Alejandro