On the maximum quartet distance between phylogenetic trees

DOI10.1137/1.9781611974331.CH146MaRDI QIDQ4575731zbMATH OpenOpenAlexFDO

Authors Noga Alon, Humberto Naves, Benny Sudakov

Publication date 16 July 2018

Published in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1505.04344

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Problems related to evolution (92D15)

Abstract: A conjecture of Bandelt and Dress states that the maximum quartet distance between any two phylogenetic trees on $n$ leaves is at most $$. 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 $$. We also give further evidence that the conjecture is true by proving that the maximum distance between caterpillar trees is at most $$.

Recommendations

• On the maximum quartet distance between phylogenetic trees
• Quartet distance between general trees
• On the quartet distance given partial information
• The maximum agreement subtree problem
• On the compatibility of quartet trees

Cited in

(6)

• Computing the quartet distance between evolutionary trees in time \(O(n\,\log n)\)
• On the maximum quartet distance between phylogenetic trees
• On the quartet distance given partial information
• Inferring metric trees from weighted quartets via an intertaxon distance
• Necessary and sufficient conditions for the existence of certain quadratic invariants under a phylogenetic tree
• Using the tangle: A consistent construction of phylogenetic distance matrices for quartets

This page was built for publication: On the maximum quartet distance between phylogenetic trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575731)