Professor Magnus Bordewich m.j.r.bordewich@durham.ac.uk
Professor
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.
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. |
Public URL | https://durham-repository.worktribe.com/output/1565693 |
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 |
Quantifying the difference between phylogenetic diversity and diversity indices
(2024)
Journal Article
On the Complexity of Optimising Variants of Phylogenetic Diversity on Phylogenetic Networks
(2022)
Journal Article
On the Maximum Agreement Subtree Conjecture for Balanced Trees
(2022)
Journal Article
A universal tree-based network with the minimum number of reticulations
(2018)
Journal Article
Recovering normal networks from shortest inter-taxa distance information
(2018)
Journal Article
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
Apache License Version 2.0 (http://www.apache.org/licenses/)
Apache License Version 2.0 (http://www.apache.org/licenses/)
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2025
Advanced Search