Colloque

An information-based sequence distance and its applications to whole genome phylogeny

Ming Li

Membre a labase

Ming Li

Résumé du colloque

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 (algorithmic information theory), and an actual program implementing this theory, for measuring the distance between two genomes. Using these, we are able to construct evolutionary trees from complete mtDNA genomes (and confirming a prior analysis of Hesagawa and his coauthors using different methods). 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. If time permits, we will also present a phylogeny of chain letters, using the same program. 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.