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,
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