On the maximum quartet distance between phylogenetic trees

Noga Alon, Humberto Naves, Benny Sudakov

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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(l))(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(l)) (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 +0(1))(n/4).

Original languageEnglish (US)
Title of host publication27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
EditorsRobert Krauthgamer
PublisherAssociation for Computing Machinery
Pages2095-2106
Number of pages12
ISBN (Electronic)9781510819672
DOIs
StatePublished - 2016
Externally publishedYes
Event27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 - Arlington, United States
Duration: Jan 10 2016Jan 12 2016

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume3

Other

Other27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
CountryUnited States
CityArlington
Period1/10/161/12/16

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'On the maximum quartet distance between phylogenetic trees'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., Naves, H., & Sudakov, B. (2016). On the maximum quartet distance between phylogenetic trees. In R. Krauthgamer (Ed.), 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 (pp. 2095-2106). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 3). Association for Computing Machinery. https://doi.org/10.1137/1.9781611974331.ch146