Ming Li - Whole genome phylogeny

We are witnessing a revolution in molecular biology and medicine: complete genomes for dozens of species are already available; genomes for many other species, including the H. sapiens, will be completed very soon.

Analyzing such information becomes one of the most interesting questions in bioinformatics research. In this talk, we will present a theory based on Kolmogorov complexity, and an actual program implementing this theory, for measuring the distance between two genomes. Using these, we are able to construct evolutionary trees (consistent with known trees) from complete genomes. Our new algorithm does not need multiple sequence alignment, does not suffer from the problem of getting different trees for different genes, and uses the complete information of a genome. The program depends on efficient compression of DNA sequences. We will also present a compression program with best compression ratios (on all benchmark sequences) for DNA sequences.