Cargando…

A distance metric for a class of tree-sibling phylogenetic networks

Motivation: The presence of reticulate evolutionary events in phylogenies turn phylogenetic trees into phylogenetic networks. These events imply in particular that there may exist multiple evolutionary paths from a non-extant species to an extant one, and this multiplicity makes the comparison of ph...

Descripción completa

Detalles Bibliográficos
Autores principales: Cardona, Gabriel, Llabrés, Mercè, Rosselló, Francesc, Valiente, Gabriel
Formato: Texto
Lenguaje:English
Publicado: Oxford University Press 2008
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2718672/
https://www.ncbi.nlm.nih.gov/pubmed/18477576
http://dx.doi.org/10.1093/bioinformatics/btn231
_version_ 1782170013166206976
author Cardona, Gabriel
Llabrés, Mercè
Rosselló, Francesc
Valiente, Gabriel
author_facet Cardona, Gabriel
Llabrés, Mercè
Rosselló, Francesc
Valiente, Gabriel
author_sort Cardona, Gabriel
collection PubMed
description Motivation: The presence of reticulate evolutionary events in phylogenies turn phylogenetic trees into phylogenetic networks. These events imply in particular that there may exist multiple evolutionary paths from a non-extant species to an extant one, and this multiplicity makes the comparison of phylogenetic networks much more difficult than the comparison of phylogenetic trees. In fact, all attempts to define a sound distance measure on the class of all phylogenetic networks have failed so far. Thus, the only practical solutions have been either the use of rough estimates of similarity (based on comparison of the trees embedded in the networks), or narrowing the class of phylogenetic networks to a certain class where such a distance is known and can be efficiently computed. The first approach has the problem that one may identify two networks as equivalent, when they are not; the second one has the drawback that there may not exist algorithms to reconstruct such networks from biological sequences. Results: We present in this article a distance measure on the class of semi-binary tree-sibling time consistent phylogenetic networks, which generalize tree-child time consistent phylogenetic networks, and thus also galled-trees. The practical interest of this distance measure is 2-fold: it can be computed in polynomial time by means of simple algorithms, and there also exist polynomial-time algorithms for reconstructing networks of this class from DNA sequence data. Availability: The Perl package Bio::PhyloNetwork, included in the BioPerl bundle, implements many algorithms on phylogenetic networks, including the computation of the distance presented in this article. Contact: gabriel.cardona@uib.es Supplementary information: Some counterexamples, proofs of the results not included in this article, and some computational experiments are available at Bioinformatics online.
format Text
id pubmed-2718672
institution National Center for Biotechnology Information
language English
publishDate 2008
publisher Oxford University Press
record_format MEDLINE/PubMed
spelling pubmed-27186722009-07-31 A distance metric for a class of tree-sibling phylogenetic networks Cardona, Gabriel Llabrés, Mercè Rosselló, Francesc Valiente, Gabriel Bioinformatics Original Papers Motivation: The presence of reticulate evolutionary events in phylogenies turn phylogenetic trees into phylogenetic networks. These events imply in particular that there may exist multiple evolutionary paths from a non-extant species to an extant one, and this multiplicity makes the comparison of phylogenetic networks much more difficult than the comparison of phylogenetic trees. In fact, all attempts to define a sound distance measure on the class of all phylogenetic networks have failed so far. Thus, the only practical solutions have been either the use of rough estimates of similarity (based on comparison of the trees embedded in the networks), or narrowing the class of phylogenetic networks to a certain class where such a distance is known and can be efficiently computed. The first approach has the problem that one may identify two networks as equivalent, when they are not; the second one has the drawback that there may not exist algorithms to reconstruct such networks from biological sequences. Results: We present in this article a distance measure on the class of semi-binary tree-sibling time consistent phylogenetic networks, which generalize tree-child time consistent phylogenetic networks, and thus also galled-trees. The practical interest of this distance measure is 2-fold: it can be computed in polynomial time by means of simple algorithms, and there also exist polynomial-time algorithms for reconstructing networks of this class from DNA sequence data. Availability: The Perl package Bio::PhyloNetwork, included in the BioPerl bundle, implements many algorithms on phylogenetic networks, including the computation of the distance presented in this article. Contact: gabriel.cardona@uib.es Supplementary information: Some counterexamples, proofs of the results not included in this article, and some computational experiments are available at Bioinformatics online. Oxford University Press 2008-07-01 2008-05-12 /pmc/articles/PMC2718672/ /pubmed/18477576 http://dx.doi.org/10.1093/bioinformatics/btn231 Text en © 2008 The Author(s) http://creativecommons.org/licenses/by-nc/2.0/uk/ This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/2.0/uk/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
spellingShingle Original Papers
Cardona, Gabriel
Llabrés, Mercè
Rosselló, Francesc
Valiente, Gabriel
A distance metric for a class of tree-sibling phylogenetic networks
title A distance metric for a class of tree-sibling phylogenetic networks
title_full A distance metric for a class of tree-sibling phylogenetic networks
title_fullStr A distance metric for a class of tree-sibling phylogenetic networks
title_full_unstemmed A distance metric for a class of tree-sibling phylogenetic networks
title_short A distance metric for a class of tree-sibling phylogenetic networks
title_sort distance metric for a class of tree-sibling phylogenetic networks
topic Original Papers
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2718672/
https://www.ncbi.nlm.nih.gov/pubmed/18477576
http://dx.doi.org/10.1093/bioinformatics/btn231
work_keys_str_mv AT cardonagabriel adistancemetricforaclassoftreesiblingphylogeneticnetworks
AT llabresmerce adistancemetricforaclassoftreesiblingphylogeneticnetworks
AT rossellofrancesc adistancemetricforaclassoftreesiblingphylogeneticnetworks
AT valientegabriel adistancemetricforaclassoftreesiblingphylogeneticnetworks
AT cardonagabriel distancemetricforaclassoftreesiblingphylogeneticnetworks
AT llabresmerce distancemetricforaclassoftreesiblingphylogeneticnetworks
AT rossellofrancesc distancemetricforaclassoftreesiblingphylogeneticnetworks
AT valientegabriel distancemetricforaclassoftreesiblingphylogeneticnetworks