Abstract
A conjecture of Bandelt and Dress states that the maximum quartet distance between any two phylogenetic trees on n leaves is at most ( 2/3 +o(1))(n 4). Using the machinery of flag algebras, we improve the currently known bounds regarding this conjecture; in particular, we show that the maximum is at most (0.69 + o(1)) (n 4). We also give further evidence that the conjecture is true by proving that the maximum distance between caterpillar trees is at most ( 2/3 + o(1)) (n 4).
| Original language | English (US) |
|---|---|
| Pages (from-to) | 718-735 |
| Number of pages | 18 |
| Journal | SIAM Journal on Discrete Mathematics |
| Volume | 30 |
| Issue number | 2 |
| DOIs | |
| State | Published - 2016 |
Bibliographical note
Publisher Copyright:© 2016 Society for Industrial and Applied Mathematics.
Keywords
- Flag algebras
- Phylogenetic trees
- Quartet distance