The Library
Unique perfect phylogeny is intractable
Tools
Habib, Michel and Stacho, Juraj (2013) Unique perfect phylogeny is intractable. Theoretical Computer Science, Volume 476 . pp. 47-66. doi:10.1016/j.tcs.2012.12.048 ISSN 0304-3975.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1016/j.tcs.2012.12.048
Abstract
A phylogeny is a tree capturing evolution and ancestral relationships of a set of taxa (e.g., species). Reconstructing phylogenies from molecular data plays an important role in many areas of contemporary biological research. A phylogeny is perfect if (in rough terms) it correctly captures all input data. Determining if a perfect phylogeny exists was shown to be intractable in 1992 by Mike Steel (Steel, 1992) [32] and independently by Bodlaender et al. (Bodlaender et al., 1992) [4]. In light of this, a related problem was proposed by Steel (1992) [32]: given a perfect phylogeny, determine if it is the unique perfect phylogeny for the given dataset, where the dataset is provided as a set of quartet (4-leaf) trees. It was suggested that this problem may be more tractable (Steel, 1992) [32], and determining its complexity became known as the Quartet Challenge (Steel, 2012) [33].
In this paper, we resolve this question by showing that the problem is CoNP-complete. We prove this by relating perfect phylogenies to satisfying assignments of Boolean formulae. To this end, we cast the question as a chordal sandwich problem. As a particular consequence of our method, we show that the unique minimal chordal sandwich problem is CoNP-complete, and counting minimal chordal sandwiches is #P-complete.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Journal or Publication Title: | Theoretical Computer Science | ||||
Publisher: | Elsevier Science BV | ||||
ISSN: | 0304-3975 | ||||
Official Date: | 11 March 2013 | ||||
Dates: |
|
||||
Volume: | Volume 476 | ||||
Page Range: | pp. 47-66 | ||||
DOI: | 10.1016/j.tcs.2012.12.048 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |