Cargando…

The Comparison of Tree-Sibling Time Consistent Phylogenetic Networks Is Graph Isomorphism-Complete

Several polynomial time computable metrics on the class of semibinary tree-sibling time consistent phylogenetic networks are available in the literature; in particular, the problem of deciding if two networks of this kind are isomorphic is in P. In this paper, we show that if we remove the semibinar...

Descripción completa

Detalles Bibliográficos
Autores principales: Cardona, Gabriel, Llabrés, Mercè, Rosselló, Francesc, Valiente, Gabriel
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Hindawi Publishing Corporation 2014
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3996867/
https://www.ncbi.nlm.nih.gov/pubmed/24982934
http://dx.doi.org/10.1155/2014/254279
_version_ 1782313108662910976
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 Several polynomial time computable metrics on the class of semibinary tree-sibling time consistent phylogenetic networks are available in the literature; in particular, the problem of deciding if two networks of this kind are isomorphic is in P. In this paper, we show that if we remove the semibinarity condition, then the problem becomes much harder. More precisely, we prove that the isomorphism problem for generic tree-sibling time consistent phylogenetic networks is polynomially equivalent to the graph isomorphism problem. Since the latter is believed not to belong to P, the chances are that it is impossible to define a metric on the class of all tree-sibling time consistent phylogenetic networks that can be computed in polynomial time.
format Online
Article
Text
id pubmed-3996867
institution National Center for Biotechnology Information
language English
publishDate 2014
publisher Hindawi Publishing Corporation
record_format MEDLINE/PubMed
spelling pubmed-39968672014-06-30 The Comparison of Tree-Sibling Time Consistent Phylogenetic Networks Is Graph Isomorphism-Complete Cardona, Gabriel Llabrés, Mercè Rosselló, Francesc Valiente, Gabriel ScientificWorldJournal Research Article Several polynomial time computable metrics on the class of semibinary tree-sibling time consistent phylogenetic networks are available in the literature; in particular, the problem of deciding if two networks of this kind are isomorphic is in P. In this paper, we show that if we remove the semibinarity condition, then the problem becomes much harder. More precisely, we prove that the isomorphism problem for generic tree-sibling time consistent phylogenetic networks is polynomially equivalent to the graph isomorphism problem. Since the latter is believed not to belong to P, the chances are that it is impossible to define a metric on the class of all tree-sibling time consistent phylogenetic networks that can be computed in polynomial time. Hindawi Publishing Corporation 2014 2014-04-02 /pmc/articles/PMC3996867/ /pubmed/24982934 http://dx.doi.org/10.1155/2014/254279 Text en Copyright © 2014 Gabriel Cardona et al. https://creativecommons.org/licenses/by/3.0/ This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
spellingShingle Research Article
Cardona, Gabriel
Llabrés, Mercè
Rosselló, Francesc
Valiente, Gabriel
The Comparison of Tree-Sibling Time Consistent Phylogenetic Networks Is Graph Isomorphism-Complete
title The Comparison of Tree-Sibling Time Consistent Phylogenetic Networks Is Graph Isomorphism-Complete
title_full The Comparison of Tree-Sibling Time Consistent Phylogenetic Networks Is Graph Isomorphism-Complete
title_fullStr The Comparison of Tree-Sibling Time Consistent Phylogenetic Networks Is Graph Isomorphism-Complete
title_full_unstemmed The Comparison of Tree-Sibling Time Consistent Phylogenetic Networks Is Graph Isomorphism-Complete
title_short The Comparison of Tree-Sibling Time Consistent Phylogenetic Networks Is Graph Isomorphism-Complete
title_sort comparison of tree-sibling time consistent phylogenetic networks is graph isomorphism-complete
topic Research Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3996867/
https://www.ncbi.nlm.nih.gov/pubmed/24982934
http://dx.doi.org/10.1155/2014/254279
work_keys_str_mv AT cardonagabriel thecomparisonoftreesiblingtimeconsistentphylogeneticnetworksisgraphisomorphismcomplete
AT llabresmerce thecomparisonoftreesiblingtimeconsistentphylogeneticnetworksisgraphisomorphismcomplete
AT rossellofrancesc thecomparisonoftreesiblingtimeconsistentphylogeneticnetworksisgraphisomorphismcomplete
AT valientegabriel thecomparisonoftreesiblingtimeconsistentphylogeneticnetworksisgraphisomorphismcomplete
AT cardonagabriel comparisonoftreesiblingtimeconsistentphylogeneticnetworksisgraphisomorphismcomplete
AT llabresmerce comparisonoftreesiblingtimeconsistentphylogeneticnetworksisgraphisomorphismcomplete
AT rossellofrancesc comparisonoftreesiblingtimeconsistentphylogeneticnetworksisgraphisomorphismcomplete
AT valientegabriel comparisonoftreesiblingtimeconsistentphylogeneticnetworksisgraphisomorphismcomplete