On the maximum quartet distance between phylogenetic trees

Noga Alon; Humberto Naves; Benny Sudakov

doi:10.1137/1.9781611974331.ch146

On the maximum quartet distance between phylogenetic trees

Noga Alon
, Humberto Naves
, Benny Sudakov

Institute for Mathematics and its Applications

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
Editors	Robert Krauthgamer
Publisher	Association for Computing Machinery
Pages	2095-2106
Number of pages	12
ISBN (Electronic)	9781510819672
DOIs	https://doi.org/10.1137/1.9781611974331.ch146
State	Published - 2016
Event	27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 - Arlington, United States Duration: Jan 10 2016 → Jan 12 2016

Publication series

Name	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume	3

Other

Other	27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
Country/Territory	United States
City	Arlington
Period	1/10/16 → 1/12/16

Bibliographical note

Publisher Copyright:
© Copyright (2016) by SIAM: Society for Industrial and Applied Mathematics.

Publisher link

10.1137/1.9781611974331.ch146

Find It

Find It at U of M Libraries

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

On the maximum quartet distance between phylogenetic trees. / Alon, Noga; Naves, Humberto; Sudakov, Benny.
27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016. ed. / Robert Krauthgamer. Association for Computing Machinery, 2016. p. 2095-2106 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 3).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, vol. 3, Association for Computing Machinery, pp. 2095-2106, 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, United States, 1/10/16. https://doi.org/10.1137/1.9781611974331.ch146

@inproceedings{eab26ade72934dc3901977e12592f242,

title = "On the maximum quartet distance between phylogenetic trees",

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).",

author = "Noga Alon and Humberto Naves and Benny Sudakov",

note = "Publisher Copyright: {\textcopyright} Copyright (2016) by SIAM: Society for Industrial and Applied Mathematics.; 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 ; Conference date: 10-01-2016 Through 12-01-2016",

year = "2016",

doi = "10.1137/1.9781611974331.ch146",

language = "English (US)",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Association for Computing Machinery",

pages = "2095--2106",

editor = "Robert Krauthgamer",

booktitle = "27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016",

}

TY - GEN

T1 - On the maximum quartet distance between phylogenetic trees

AU - Alon, Noga

AU - Naves, Humberto

AU - Sudakov, Benny

PY - 2016

Y1 - 2016

N2 - 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).

AB - 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).

UR - https://www.scopus.com/pages/publications/84963540126

UR - https://www.scopus.com/pages/publications/84963540126#tab=citedBy

U2 - 10.1137/1.9781611974331.ch146

DO - 10.1137/1.9781611974331.ch146

M3 - Conference contribution

AN - SCOPUS:84963540126

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 2095

EP - 2106

BT - 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016

A2 - Krauthgamer, Robert

PB - Association for Computing Machinery

T2 - 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016

Y2 - 10 January 2016 through 12 January 2016

ER -

On the maximum quartet distance between phylogenetic trees

Abstract

Publication series

Other

Bibliographical note

Publisher link

Find It

Other files and links

Fingerprint

Cite this