Professor Magnus Bordewich m.j.r.bordewich@durham.ac.uk
Professor
Computing the minimum number of hybridisation events for a consistent evolutionary history
Bordewich, M.; Semple, C.
Authors
C. Semple
Abstract
It is now well-documented that the structure of evolutionary relationships between a set of present-day species is not necessarily tree-like. The reason for this is that reticulation events such as hybridizations mean that species are a mixture of genes from different ancestors. Since such events are relatively rare, a fundamental problem for biologists is to determine the smallest number of hybridization events required to explain a given (input) set of data in a single (hybrid) phylogeny. The main results of this paper show that computing this smallest number is APX-hard, and thus NP-hard, in the case the input is a collection of phylogenetic trees on sets of present-day species. This answers a problem which was raised at a recent conference (Phylogenetic Combinatorics and Applications, Uppsala University, 2004). As a consequence of these results, we also correct a previously published NP-hardness proof in the case the input is a collection of binary sequences, where each sequence represents the attributes of a particular present-day species. The APX-hardness of these problems means that it is unlikely that there is an efficient algorithm for either computing the result exactly or approximating it to any arbitrary degree of accuracy.
Citation
Bordewich, M., & Semple, C. (2007). Computing the minimum number of hybridisation events for a consistent evolutionary history. Discrete Applied Mathematics, 155(8), 914-928. https://doi.org/10.1016/j.dam.2006.08.008
Journal Article Type | Article |
---|---|
Publication Date | Apr 15, 2007 |
Deposit Date | Dec 21, 2009 |
Journal | Discrete Applied Mathematics |
Print ISSN | 0166-218X |
Publisher | Elsevier |
Peer Reviewed | Peer Reviewed |
Volume | 155 |
Issue | 8 |
Pages | 914-928 |
DOI | https://doi.org/10.1016/j.dam.2006.08.008 |
Keywords | Rooted phylogenetic tree, Reticulate evolution, Hybrid phylogeny, Phylogenetic network, Agreement forest, Rooted subtree prune and regraft. |
You might also like
Evaluating Gaussian Grasp Maps for Generative Grasping Models
(2022)
Conference Proceeding
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
Autoencoders Without Reconstruction for Textural Anomaly Detection
(2021)
Conference Proceeding
Improving Robotic Grasping on Monocular Images Via Multi-Task Learning and Positional Loss
(2021)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
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 © 2024
Advanced Search