Counting consistent phylogenetic trees is #P-complete

Type of content
Discussion / Working Papers
Publisher's DOI/URI
Thesis discipline
Degree name
Publisher
University of Canterbury
Journal Title
Journal ISSN
Volume Title
Language
Date
2003
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 P 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 'P' is #P-complete.

Description
Citation
Keywords
Ngā upoko tukutuku/Māori subject headings
ANZSRC fields of research
Fields of Research::31 - Biological sciences::3104 - Evolutionary biology::310410 - Phylogeny and comparative analysis
Fields of Research::49 - Mathematical sciences::4901 - Applied mathematics::490102 - Biological mathematics
Rights
All Rights Reserved