On the maximum quartet distance between phylogenetic trees

Noga Alon, Humberto Naves, Benny Sudakov

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

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 languageEnglish (US)
Pages (from-to)718-735
Number of pages18
JournalSIAM Journal on Discrete Mathematics
Volume30
Issue number2
DOIs
StatePublished - 2016

Bibliographical note

Funding Information:
Sackler School of Mathematics and Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel, and School of Mathematics, Institute for Advanced Study, Princeton, NJ 08540 (nogaa@tau.ac.il). This author's research was supported in part by a USA-Israeli BSF grant, an ISF grant, the Israeli I-Core program, and the Fund for Mathematics.

Publisher Copyright:
© 2016 Society for Industrial and Applied Mathematics.

Keywords

  • Flag algebras
  • Phylogenetic trees
  • Quartet distance

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

Cite this