TY - GEN

T1 - On the compatibility of quartet trees

AU - Alon, Noga

AU - Snir, Sagi

AU - Yuster, Raphael

PY - 2014

Y1 - 2014

N2 - Phylogenetic tree reconstruction is a fundamental biological problem. Quartet trees, trees over four species, are the minimal informational unit for phylogenetic classification. While every phylogenetic tree over n species defines (n4) quartets, not every set of quartets is compatible with some phylogenetic tree. Here we focus on the compatibility of quartet sets. We provide several results addressing the question of what can be inferred about the compatibility of a set from its subsets. Most of our results use probabilistic arguments to prove the sought characteristics. In particular we show that there are quartet sets Q of size m = cn log n in which every subset of cardinality c'n/ log n is compatible, and yet no fraction of more than 1/3 + ε of Q is compatible. On the other hand, in contrast to the classical result stating when Q is the densest, i.e. m = (n4) the consistency of any set of 3 quartets implies full consistency, we show that even for m = Θ((n4)) there are (very) inconsistent sets for which every subset of large constant cardinality is consistent. Our final result, relates to the conjecture of Bandelt and Dress regarding the maximum quartet distance between trees. We provide asymptotic upper and lower bounds for this value.

AB - Phylogenetic tree reconstruction is a fundamental biological problem. Quartet trees, trees over four species, are the minimal informational unit for phylogenetic classification. While every phylogenetic tree over n species defines (n4) quartets, not every set of quartets is compatible with some phylogenetic tree. Here we focus on the compatibility of quartet sets. We provide several results addressing the question of what can be inferred about the compatibility of a set from its subsets. Most of our results use probabilistic arguments to prove the sought characteristics. In particular we show that there are quartet sets Q of size m = cn log n in which every subset of cardinality c'n/ log n is compatible, and yet no fraction of more than 1/3 + ε of Q is compatible. On the other hand, in contrast to the classical result stating when Q is the densest, i.e. m = (n4) the consistency of any set of 3 quartets implies full consistency, we show that even for m = Θ((n4)) there are (very) inconsistent sets for which every subset of large constant cardinality is consistent. Our final result, relates to the conjecture of Bandelt and Dress regarding the maximum quartet distance between trees. We provide asymptotic upper and lower bounds for this value.

UR - http://www.scopus.com/inward/record.url?scp=84902096374&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84902096374&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973402.40

DO - 10.1137/1.9781611973402.40

M3 - Conference contribution

AN - SCOPUS:84902096374

SN - 9781611973389

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

SP - 535

EP - 545

BT - Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014

PB - Association for Computing Machinery

T2 - 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014

Y2 - 5 January 2014 through 7 January 2014

ER -