Professor Magnus Bordewich m.j.r.bordewich@durham.ac.uk
Professor
Accuracy Guarantees for Phylogeny Reconstruction Algorithms Based on Balanced Minimum Evolution.
Bordewich, Magnus; Mihaescu, Radu
Authors
Radu Mihaescu
Contributors
Vincent Moulton
Editor
Mona Singh
Editor
Abstract
Distance based phylogenetic methods attempt to reconstruct an accurate phylogenetic tree relating a given set of taxa from an estimated matrix of pair-wise distances between taxa. This paper examines two distance based algorithms (GreedyBME and FastME) which are based on the principle of trying to minimise the balanced minimum evolution (BME) score of the output tree in relation to the given estimated distance matrix. We show firstly that these algorithms will both reconstruct the correct tree if the input data is quartet consistent, and secondly that if the maximum error in any individual distance estimate is ε, then both algorithms will output trees containing all edges of the true tree that have length at least 3ε. That is to say the algorithms have edge safety radius 1/3. In contrast, quartet consistency of the data is not sufficient to guarantee Neighbor Joining (NJ) reconstructs the correct tree, and moreover NJ has edge safety radius of 1/4, which is strictly worse.
Citation
Bordewich, M., & Mihaescu, R. (2010). Accuracy Guarantees for Phylogeny Reconstruction Algorithms Based on Balanced Minimum Evolution. In V. Moulton, & M. Singh (Eds.), Algorithms in Bioinformatics: 10th International Workshop, WABI 2010, Liverpool, UK, September 6-8, 2010. Proceedings (250-261). https://doi.org/10.1007/978-3-642-15294-8_21
Conference Name | 10th Workshop on Algorithms in Bioinformatics (WABI 2010) |
---|---|
Conference Location | Liverpool |
Publication Date | 2010 |
Deposit Date | Aug 2, 2010 |
Publisher | Springer Verlag |
Volume | 6293 |
Pages | 250-261 |
Series Title | Lecture Notes in Computer Science |
Book Title | Algorithms in Bioinformatics: 10th International Workshop, WABI 2010, Liverpool, UK, September 6-8, 2010. Proceedings |
ISBN | 978-3-642-15293-1 |
DOI | https://doi.org/10.1007/978-3-642-15294-8_21 |
Public URL | https://durham-repository.worktribe.com/output/1159173 |
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