The genomic era has reached the point where tasks that seemed imaginary only a decade ago are now within reach. One such task, that is among the most fundamentals in biology, is the inference of the evolutionary history for tens of thousands of species, sometimes of very close origin. Such a history is depicted in a tree structure and is called a phylogeny or a phylogenetic tree. In prokaryotes however, the validity of such a tree has been questioned significantly. This is primarily due to the phenomenon of horizontal gene transfer (HGT), the transfer of genetic material not through lineal descent. HGT links between distantly related species, obfuscating the vertical signal of evolution.

Quartets, trees over four leaves, are the minimal informational phylogenetic unit and stand at the heart of almost any phylogenetic task, in particular when conflicting signals arise. Besides, and perhaps due to their rudimentary role, quartet-based phylogenetic approaches offer combinatorially/statistically clean problems yet highly relevant to topical questions in evolution. In a series of works we have developed a graph theoretically based approach for the quartets amalgamation task. Our approach is based on a divide and conquer algorithm, where the divide step is based on solving a MaxCut in a special graph we construct. Besides providing a very fast and accurate heuristic for phylogenetics, the cleanliness of this approach has also advanced a more than thirty years open problem of quartets’ compatibility. Additionally, I will survey HGT geared quartets approaches that provide provably guarantees to popular approaches in genomics and metagenomics.  

The talk is self contained and assumes no knowledge in biology.