![](/images/graphics-bg.png)
The Comparison of Tree-Sibling Time Consistent Phylogenetic Networks Is Graph Isomorphism-Complete
Joint Authors
Cardona, Gabriel
Llabrés, Mercè
Rosselló, Francesc
Valiente, Gabriel
Source
Issue
Vol. 2014, Issue 2014 (31 Dec. 2014), pp.1-6, 6 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2014-04-02
Country of Publication
Egypt
No. of Pages
6
Main Subjects
Medicine
Information Technology and Computer Science
Abstract EN
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.
American Psychological Association (APA)
Cardona, Gabriel& Llabrés, Mercè& Rosselló, Francesc& Valiente, Gabriel. 2014. The Comparison of Tree-Sibling Time Consistent Phylogenetic Networks Is Graph Isomorphism-Complete. The Scientific World Journal،Vol. 2014, no. 2014, pp.1-6.
https://search.emarefa.net/detail/BIM-1048920
Modern Language Association (MLA)
Cardona, Gabriel…[et al.]. The Comparison of Tree-Sibling Time Consistent Phylogenetic Networks Is Graph Isomorphism-Complete. The Scientific World Journal No. 2014 (2014), pp.1-6.
https://search.emarefa.net/detail/BIM-1048920
American Medical Association (AMA)
Cardona, Gabriel& Llabrés, Mercè& Rosselló, Francesc& Valiente, Gabriel. The Comparison of Tree-Sibling Time Consistent Phylogenetic Networks Is Graph Isomorphism-Complete. The Scientific World Journal. 2014. Vol. 2014, no. 2014, pp.1-6.
https://search.emarefa.net/detail/BIM-1048920
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1048920