Reasearch Awards nomination

Email updates

Keep up to date with the latest news and content from Algorithms for Molecular Biology and BioMed Central.

Open Access Research

Incompatible quartets, triplets, and characters

Brad Shutters*, Sudheer Vakati and David Fernández-Baca

Author Affiliations

Department of Computer Science, Iowa State University, Ames, IA 50011, USA

For all author emails, please log on.

Algorithms for Molecular Biology 2013, 8:11  doi:10.1186/1748-7188-8-11

Published: 1 April 2013

Abstract

We study a long standing conjecture on the necessary and sufficient conditions for the compatibility of multi-state characters: There exists a function f(r) such that, for any set C of r-state characters, C is compatible if and only if every subset of f(r) characters of C is compatible. We show that for every r≥2, there exists an incompatible set C of Ω(r2)r-state characters such that every proper subset of C is compatible. This improves the previous lower bound of f(r)≥r given by Meacham (1983), and f(4)≥5 given by Habib and To (2011). For the case when r=3, Lam, Gusfield and Sridhar (2011) recently showed that f(3)=3. We give an independent proof of this result and completely characterize the sets of pairwise compatible 3-state characters by a single forbidden intersection pattern.

Our lower bound on f(r) is proven via a result on quartet compatibility that may be of independent interest: For every n≥4, there exists an incompatible set Q of Ω(n2) quartets over n labels such that every proper subset of Q is compatible. We show that such a set of quartets can have size at most 3 when n=5, and at most O(n3) for arbitrary n. We contrast our results on quartets with the case of rooted triplets: For every n≥3, if R is an incompatible set of more than n−1 triplets over n labels, then some proper subset of R is incompatible. We show this bound is tight by exhibiting, for every n≥3, a set of n−1 triplets over n taxa such that R is incompatible, but every proper subset of R is compatible.

Keywords:
Phylogenetics; Quartet compatibility; Triplet compatibility; Character compatibility; Perfect phylogeny