On the maximum quartet distance between phylogenetic trees
Preprint
Abstract
A conjecture of Bandelt and Dress states that the maximum quartet distance between any two phylogenetic trees on $n$ leaves is at most $(\frac 23 +o(1))\binom{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))\binom{n}{4}$. We also give further evidence that the conjecture is true by proving that the maximum distance between caterpillar trees is at most $(\frac 23 +o(1))\binom{n}{4}$.
Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Minimum Number ofk-Cliques in Graphs with Bounded Independence NumberCombinatorics, Probability and Computing, 2013
- On the number of pentagons in triangle-free graphsJournal of Combinatorial Theory, Series A, 2013
- On 3-Hypergraphs with Forbidden 4-Vertex ConfigurationsSIAM Journal on Discrete Mathematics, 2010
- Quartets MaxCut: A Divide and Conquer Quartets AlgorithmIEEE/ACM Transactions on Computational Biology and Bioinformatics, 2008
- On the Minimal Density of Triangles in GraphsCombinatorics, Probability and Computing, 2008
- Inferring evolutionary trees with strong combinatorial evidenceTheoretical Computer Science, 2000
- Quartet Puzzling: A Quartet Maximum-Likelihood Method for Reconstructing Tree TopologiesMolecular Biology and Evolution, 1996
- The complexity of reconstructing trees from qualitative characters and subtreesJournal of Classification, 1992
- Reconstructing the shape of a tree from observed dissimilarity dataAdvances in Applied Mathematics, 1986
- Tree structures for proximity dataBritish Journal of Mathematical and Statistical Psychology, 1981