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...
| Publicado en: | Scientific World Journal pp. 254279 - 254280 |
|---|---|
| Autores principales: | , , , |
| Formato: | research Journal Article |
| Publicado: |
Wiley-Blackwell
2014
|
| Acceso en línea: | Ver este registro en EBSCOhost |
| fields | @attributes: recordID: 1 pdfLink: plink: https://search.ebscohost.com/login.aspx?direct=true&db=ccm&AN=103831763&site=ehost-live header: @attributes: shortDbName: ccm uiTerm: 103831763 longDbName: CINAHL Complete uiTag: AN controlInfo: bkinfo: dissinfo: jinfo: jid: 1537744X 1BX5 jtl: Scientific World Journal issn: 1537744X maglogo: N pubinfo: dt: 2014 pid: 480 pub: Wiley-Blackwell place: Malden, Massachusetts artinfo: ui: 103831763 103831763 NLM24982934 2012634762 10.1155/2014/254279 NLM24982934 PMC3996867 103831763 ppf: 254279 ppct: 1 formats: tig: atl: The comparison of tree-sibling time consistent phylogenetic networks is graph isomorphism-complete. aug: au: Cardona, Gabriel Llabrés, Mercè Rosselló, Francesc Valiente, Gabriel affil: Department of Mathematics and Computer Science, University of the Balearic Islands, 07122 Palma de Mallorca, Spain. sug: subj: Algorithms Evolution Bioinformatics ab: 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. pubtype: Academic Journal doctype: research Journal Article ougenre: Article language: English refInfo: holdings: @attributes: islocal: N |
|---|