Counting Consistent Phylogenetic Trees is #P-complete

Bordewich, M.; Semple, C.; Talbot, J.

doi:10.1016/j.aam.2003.08.006

Counting Consistent Phylogenetic Trees is #P-complete

Bordewich, M.; Semple, C.; Talbot, J.

Authors

Professor Magnus Bordewich m.j.r.bordewich@durham.ac.uk
Professor

C. Semple

J. Talbot

Abstract

Reconstructing phylogenetic trees is a fundamental task in evolutionary biology. Various algorithms exist for this purpose, many of which come under the heading of `supertree methods'. These methods amalgamate a collection Ρ of phylogenetic trees into a single parent tree. In this paper, we show that, in both the rooted and unrooted settings, counting the number of parent trees that preserve all of the ancestral relationships displayed by the phylogenetic trees in Ρ is #P-complete.

Citation

Bordewich, M., Semple, C., & Talbot, J. (2004). Counting Consistent Phylogenetic Trees is #P-complete. Advances in Mathematics, 33(2), 416-430. https://doi.org/10.1016/j.aam.2003.08.006

Journal Article Type	Article
Publication Date	Aug 1, 2004
Deposit Date	Dec 21, 2009
Journal	Advances in Mathematics
Print ISSN	0001-8708
Publisher	Elsevier
Peer Reviewed	Peer Reviewed
Volume	33
Issue	2
Pages	416-430
DOI	https://doi.org/10.1016/j.aam.2003.08.006
Keywords	Phylogenetic tree, Complexity, #P complete.
Publisher URL	http://www.sciencedirect.com/science?_ob=MImg&_imagekey=B6W9D-4C0V4XH-2-2&_cdi=6680&_user=121711&_orig=browse&_coverDate=08%2F31%2F2004&_sk=999669997&view=c&wchp=dGLbVlb-zSkWb&md5=0b0c83ed517623f014720d845ece9d52&ie=/sdarticle.pdf