dc.contributor.author | Cardona, Gabriel | |
dc.contributor.author | Llabres, Merce | |
dc.contributor.author | Rossello, Francesc | |
dc.contributor.author | Valiente, Gabriel | |
dc.date.accessioned | 2024-07-03T11:01:11Z | |
dc.date.available | 2024-07-03T11:01:11Z | |
dc.date.issued | 2014 | |
dc.identifier.citation | Cardona G, Llabres Segura M, Rossello F, Valiente G. The Comparison of Tree-Sibling Time Consistent Phylogenetic Networks Is Graph Isomorphism-Complete. Sci World J. 2014;:254279. Epub 2014 Apr 2. | en |
dc.identifier.issn | 1537-744X | |
dc.identifier.other | http://hdl.handle.net/20.500.13003/11385 | |
dc.identifier.uri | http://hdl.handle.net/20.500.12105/19941 | |
dc.description.abstract | 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. | en |
dc.description.sponsorship | The authors would like to thank Antoni Lozano for his comments on an early version of this paper. The research reported in this paper has been partially supported by the Spanish government and the UE FEDER Program, through Project no. MTM2009-07165. | es_ES |
dc.language.iso | eng | en |
dc.publisher | Hindawi | en |
dc.rights.uri | https://creativecommons.org/licenses/by/3.0/ | * |
dc.subject.mesh | Phylogeny | * |
dc.subject.mesh | Computational Biology | * |
dc.subject.mesh | Humans | * |
dc.subject.mesh | Algorithms | * |
dc.title | The Comparison of Tree-Sibling Time Consistent Phylogenetic Networks Is Graph Isomorphism-Complete | en |
dc.type | research article | en |
dc.rights.license | Attribution 3.0 Unported | * |
dc.identifier.pubmedID | 24982934 | es_ES |
dc.format.page | 254279 | es_ES |
dc.identifier.doi | 10.1155/2014/254279 | |
dc.relation.publisherversion | https://dx.doi.org/10.1155/2014/254279 | en |
dc.identifier.journal | Scientific World Journal | es_ES |
dc.rights.accessRights | open access | en |
dc.subject.decs | Filogenia | * |
dc.subject.decs | Humanos | * |
dc.subject.decs | Algoritmos | * |
dc.subject.decs | Biología Computacional | * |
dc.identifier.scopus | 2-s2.0-84899408710 | |
dc.identifier.wos | 334201300001 | |
dc.identifier.pui | L372953415 | |