dc.contributor.author |
Bonet, ML |
en |
dc.contributor.author |
Linz, Simone |
en |
dc.contributor.author |
St. John, K |
en |
dc.date.accessioned |
2015-02-02T20:52:08Z |
en |
dc.date.issued |
2012-01 |
en |
dc.identifier.citation |
IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2012, 9 (1), pp. 273 - 285 |
en |
dc.identifier.issn |
1545-5963 |
en |
dc.identifier.uri |
http://hdl.handle.net/2292/24371 |
en |
dc.description.abstract |
We show that two important problems that have applications in computational biology are ASP-complete, which implies that, given a solution to a problem, it is NP-complete to decide if another solution exists. We show first that a variation of BETWEENNESS, which is the underlying problem of questions related to radiation hybrid mapping, is ASP-complete. Subsequently, we use that result to show that QUARTET COMPATIBILITY, a fundamental problem in phylogenetics that asks whether a set of quartets can be represented by a parent tree, is also ASP-complete. The latter result shows that Steel's QUARTET CHALLENGE, which asks whether a solution to QUARTET COMPATIBILITY is unique, is coNP-complete. |
en |
dc.language |
aa |
en |
dc.relation.ispartofseries |
IEEE/ACM Transactions on Computational Biology and Bioinformatics |
en |
dc.rights |
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher. Details obtained from http://www.ieee.org/publications_standards/publications/rights/rights_policies.html
http://www.sherpa.ac.uk/romeo/issn/1545-5963/ |
en |
dc.rights.uri |
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm |
en |
dc.title |
The Complexity of Finding Multiple Solutions to Betweenness and Quartet Compatibility |
en |
dc.type |
Journal Article |
en |
dc.identifier.doi |
10.1109/TCBB.2011.108 |
en |
pubs.issue |
1 |
en |
pubs.begin-page |
273 |
en |
pubs.volume |
9 |
en |
dc.description.version |
AM - Accepted Manuscript |
en |
dc.identifier.pmid |
21788676 |
en |
pubs.end-page |
285 |
en |
dc.rights.accessrights |
http://purl.org/eprint/accessRights/OpenAccess |
en |
pubs.subtype |
Article |
en |
pubs.elements-id |
460389 |
en |
pubs.org-id |
Science |
en |
pubs.org-id |
School of Computer Science |
en |
pubs.record-created-at-source-date |
2015-02-03 |
en |
pubs.online-publication-date |
2011-07-29 |
en |
pubs.dimensions-id |
21788676 |
en |