Rigorous, likelihood-based, analysis of trees and networks as data generative models. Algorithms, algebraic closed-form solutions, and hardness results are shown for the various models - trees and networks, and for the big, the small, and the tiny problem.
The Supertree aims at combining a collection of a small, possibly overlapping, subtrees, into a big tree over the entire species set in a fashion maximizing the subtrees agreement. Quartets - trees over four taxa - are the minimal informational phylogenetic unit. Therefore, quartet supertree is the most fundamental supertree problem and stands at the heart of many other, more complicated, phylogenetic problems. We devised a recursive, semidefinite-programming based approach to quartet amalgamation. The approach, beyond providing a very fast and efficient heuristic to the problem, also gives rise to significant improvement to the long open theoretical question of approximation maximum quartet compatibility, where the only other result is a ratio of 1/3 achieved naively by a random tree.
Genomes of prokaryotes (bacteria and archaea) are characterized by high rates of recombination events, causing continuous change in genome organization. These changes leave an evolutionary footprint that can be exploited for various purposes. We have devised a simple approach, the synteny index, allowing us to infer evolutionary history in a very fine grained resolution of strains of species, as well as the detection of horizontal gene transfer.
A coloring (character) is convex on a tree if it induces no reversals and convergence - homoplasy free. We show hardness results, fixed parameters, and approximation algorithms for several of the variants of the problem.
In this project we adopt the universal pacemaker the we devised to provide a global framework for genome evolution, to model epigenetic aging. Under the model, methylating sites have an intrinsic rate that is universal, however subjected to individual biological (as opposed to chronological) age. This framework, when applied to a cohort, is able to identify an aging trend in a population. Indeed, in a recent study, we were able to show that human epigenetic aging is logarithmic across the entire life span, refuting the common belief of a linear aging during adulthood.
