Assembling the Tree of Life (ATOL) program funded by the US NSF fund aims at reconstruction the evolutionary history of several millions of species. This goal cannot be achieved by contemporary ordinary phylogenetic reconstruction methods. This calls for a supertree approach – an approach for combining small trees over partial, overlapping, sets of species, into a big tree over the complete species set.
Quartet trees – trees over four species, are the most basic informative phylogenetic unit as it can define uniquely any tree. Therefore, quartet amalgamation – joining quartets into a single tree lies at the heart of almost any phylogenetic task. Quartet supertree arises in many instances, even when the history is not tree-like, with event like horizontal gene transfer or incomplete lineage sorting. Nevertheless, it is among the hardest computationally and basic questions are open for decades.
During the years, we have developed a novel graph-based, divide and conquer technique relaying on semi-definite programming (SDP) approach. The approach, denoted Quartet MaxCut, constructs the Quartet Graph based on the input quartets, and then applies a MaxCut to this graph. We have devised a super fast implementation to this approach that is the fastest and most accurate for this task. Our software was used by many users in many applications ranging from cancer detection and even up to computer graphics and music classification.
In parallel, in a series of theoretical works, we could show that the MaxCut approach yields the first theoretical approximation guarantee, of 0.425, improving over the naïve 1/3 obtained trivially by a random tree.
