December 30, Wednesday 14:15, Room 303, Jacobs Building

Phylogenetic Tree Reconstruction with Insertions and Deletions

Lecturer :
Avinatan Hassidim

Lecturer homepage : http://www2.lns.mit.edu/~avinatan/

Affiliation : Microsoft Research, Boston MA


Phylogenetic trees represent evolutionary history, by showing the course of evolution from some
extinct common ancestor to today's species. These trees can reveal connections between different
species, teach us about extinct species, and help us understand the development of viruses, and
other organisms with high mutation rate.

The most common way of reconstructing phylogenetic trees is based on sequencing DNA from
different species, and using similarities between sequences to infer the tree. This requires some
model of how DNA evolves between an ancestor species and its descendants. The simplest model
assumes that there are i.i.d mutations, and that each mutation is a substitution, and under this model,
there are provably good reconstruction algorithm. However, recent studies show that insertions and
deletions mutations are a serious cause of reconstruction errors, and can not be ignored.

We present the first efficient algorithm for tree reconstruction when the mutations can be
substitutions, insertions and deletions. The algorithm uses a clustering based approach, which
builds small parts of the tree, and glues them together. In addition, the algorithm outputs a global
alignment of the DNA sequences, which respects the evolutionary history.

Based on joint works with Alex Andoni, Mark Braverman, Costis Daskalakis and Sebasiten Roch