On the maximum quartet distance between phylogenetic trees

Noga Alon, Humberto Naves, Benny Sudakov

Research output: Contribution to journalArticle

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 - Jan 1 2016
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

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