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...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2014-01-01
|
| Series: | The Scientific World Journal |
| Online Access: | http://dx.doi.org/10.1155/2014/254279 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832551880658518016 |
|---|---|
| author | Gabriel Cardona Mercè Llabrés Francesc Rosselló Gabriel Valiente |
| author_facet | Gabriel Cardona Mercè Llabrés Francesc Rosselló Gabriel Valiente |
| author_sort | Gabriel Cardona |
| collection | DOAJ |
| 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 | Article |
| id | doaj-art-6aba4fb91b37427691d8fad5740c1640 |
| institution | Kabale University |
| issn | 2356-6140 1537-744X |
| language | English |
| publishDate | 2014-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | The Scientific World Journal |
| spelling | doaj-art-6aba4fb91b37427691d8fad5740c16402025-02-03T06:00:07ZengWileyThe Scientific World Journal2356-61401537-744X2014-01-01201410.1155/2014/254279254279The Comparison of Tree-Sibling Time Consistent Phylogenetic Networks Is Graph Isomorphism-CompleteGabriel Cardona0Mercè Llabrés1Francesc Rosselló2Gabriel Valiente3Department of Mathematics and Computer Science, University of the Balearic Islands, 07122 Palma de Mallorca, SpainDepartment of Mathematics and Computer Science, University of the Balearic Islands, 07122 Palma de Mallorca, SpainDepartment of Mathematics and Computer Science, University of the Balearic Islands, 07122 Palma de Mallorca, SpainAlgorithms, Bioinformatics, Complexity and Formal Methods Research Group, Technical University of Catalonia, 08034 Barcelona, SpainSeveral 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.http://dx.doi.org/10.1155/2014/254279 |
| spellingShingle | Gabriel Cardona Mercè Llabrés Francesc Rosselló Gabriel Valiente The Comparison of Tree-Sibling Time Consistent Phylogenetic Networks Is Graph Isomorphism-Complete The Scientific World Journal |
| 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 |
| url | http://dx.doi.org/10.1155/2014/254279 |
| work_keys_str_mv | AT gabrielcardona thecomparisonoftreesiblingtimeconsistentphylogeneticnetworksisgraphisomorphismcomplete AT mercellabres thecomparisonoftreesiblingtimeconsistentphylogeneticnetworksisgraphisomorphismcomplete AT francescrossello thecomparisonoftreesiblingtimeconsistentphylogeneticnetworksisgraphisomorphismcomplete AT gabrielvaliente thecomparisonoftreesiblingtimeconsistentphylogeneticnetworksisgraphisomorphismcomplete AT gabrielcardona comparisonoftreesiblingtimeconsistentphylogeneticnetworksisgraphisomorphismcomplete AT mercellabres comparisonoftreesiblingtimeconsistentphylogeneticnetworksisgraphisomorphismcomplete AT francescrossello comparisonoftreesiblingtimeconsistentphylogeneticnetworksisgraphisomorphismcomplete AT gabrielvaliente comparisonoftreesiblingtimeconsistentphylogeneticnetworksisgraphisomorphismcomplete |