Counting consistent phylogenetic trees is #P-complete

Type of content
Journal Article
Publisher's DOI/URI
Thesis discipline
Degree name
Publisher
University of Canterbury. Mathematics and Statistics.
Journal Title
Journal ISSN
Volume Title
Language
Date
2004
Authors
Bordewich, M.
Semple, C.
Talbot, J.
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.

Description
Citation
Bordewich, M., Semple, C., Talbot, J. (2004) Counting consistent phylogenetic trees is #P-complete. Advances in Applied Mathematics, 33, pp. 416-430.
Keywords
Ngā upoko tukutuku/Māori subject headings
ANZSRC fields of research
Rights