A quartet tree (or simply a quartet) is a tree over four taxa (species) that is the most basic phylogenetic building block - A tree can be decomposed into its defining quartets that uniquely define it. It is this fundamentality that confers the quartets their power. The converse however, is not true - it is rare that an arbitrary quartet set agrees on some tree. Hence, given a set of quartets, it is a common practice to look for a tree agreeing with the most of them. This seemingly simple and “clean” question lies at the heart of almost any specific, more complicated question in phylogenetics. Due to its centrality and importance, it has gained a lot of attention, from both theoreticians and practitioners. Notwithstanding, very little has been achieved since it was first introduced, more than two decades ago [1] - the best rigorous approximation to it, is obtained naively by a random tree, satisfying a third of the quartet set [2], and practical software use crude heuristics and are either slow or inaccurate.

During the years, our lab has dealt with many aspects of the supertree task, for the centrality and challenge of the associated tasks. Starting from my postdoc at Berkeley, we have developed a novel approach that embed the data in a graph and applies a MaxCut algorithm to the graph in order to classify the species according to the quartet information. The MaxCut, a very hard computational problem, is “solved” using a randomized semi-definite programming (SDP) approach that yields a very fast implementation. The general approach, quartet MaxCut has provided both theoretical and practical improvements in this well studied field that have been published in top conferences and journals in and bioinformatics [3,4,5] and computer science [6,7,8]. The approach (and software) is generic and was found useful in other applications such as classifying shapes in computer graphics [9], music performance analysis [10]. We were awarded the Israeli Science Foundation grant for this research direction. It is a nice example to the interrelationships between theory and practice in the field.