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