Professor Magnus Bordewich m.j.r.bordewich@durham.ac.uk
Professor
Defining a Phylogenetic Tree with the Minimum Number of r-State Characters
Bordewich, M.; Semple, C.
Authors
C. Semple
Abstract
Semple and Steel (2002) showed that if T is a phylogenetic X-tree and C is a collection of r-state characters that defines T , then |C| ≥ (n − 3)/(r − 1), where n = |X|. In this paper, we show that, provided n is sufficiently large, this lower bound is sharp. Furthermore, we show that, for all n ≥ 13, there exists a collection of 4-state characters of size (n − 3)/3 that defines T , but there is a phylogenetic X-tree with n = 12 which is not defined by any set of 3 characters.
Citation
Bordewich, M., & Semple, C. (2015). Defining a Phylogenetic Tree with the Minimum Number of r-State Characters. SIAM Journal on Discrete Mathematics, 29(2), 835-853. https://doi.org/10.1137/130924469
Journal Article Type | Article |
---|---|
Acceptance Date | Jan 28, 2015 |
Publication Date | Apr 21, 2015 |
Deposit Date | Apr 28, 2015 |
Publicly Available Date | Mar 28, 2024 |
Journal | SIAM Journal on Discrete Mathematics |
Print ISSN | 0895-4801 |
Electronic ISSN | 1095-7146 |
Publisher | Society for Industrial and Applied Mathematics |
Peer Reviewed | Peer Reviewed |
Volume | 29 |
Issue | 2 |
Pages | 835-853 |
DOI | https://doi.org/10.1137/130924469 |
Keywords | Phylogenetic tree, r-State character, Chordal graph. |
Files
Published Journal Article
(362 Kb)
PDF
Copyright Statement
Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.
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