The Comparison of Tree-Sibling Time Consistent Phylogenetic Networks Is Graph Isomorphism-CompleteReport as inadecuate

The Comparison of Tree-Sibling Time Consistent Phylogenetic Networks Is Graph Isomorphism-Complete - Download this document for free, or read online. Document in PDF available to download.

The Scientific World Journal - Volume 2014 2014, Article ID 254279, 6 pages -

Research Article

Department of Mathematics and Computer Science, University of the Balearic Islands, 07122 Palma de Mallorca, Spain

Algorithms, Bioinformatics, Complexity and Formal Methods Research Group, Technical University of Catalonia, 08034 Barcelona, Spain

Received 27 November 2013; Accepted 21 January 2014; Published 2 April 2014

Academic Editors: J.-H. Hung and L. Zhang

Copyright © 2014 Gabriel Cardona et al. 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.


Several polynomial time computable metrics on the class of semibinary tree-siblingtime consistent phylogenetic networks are available in the literature; in particular,the problem of deciding if two networks of this kind are isomorphic is inP. In this paper, we show that if we remove the semibinarity condition, then theproblem becomes much harder. More precisely, we prove that the isomorphismproblem for generic tree-sibling time consistent phylogenetic networks is polynomiallyequivalent to the graph isomorphism problem. Since the latter is believed notto belong to P, the chances are that it is impossible to define a metric on the classof all tree-sibling time consistent phylogenetic networks that can be computed inpolynomial time.

Author: Gabriel Cardona, Mercè Llabrés, Francesc Rosselló, and Gabriel Valiente



Related documents