February 7, 2008 - Ming Li

Title: Modern Homology Search

Abstract:
Homology search, finding similar parts between two sequences, is the most fundamental and popular task in bioinformatics. Traditional homology search technology is either too slow or too insensitive. When it does return something, the results are simply some non-specific fragments of alignments. We introduce new ideas, including a new mathematical theory of optimized spaced seeds, that allow modern homology search to achieve high sensitivity, high specificity, and high speed simultaneously. The spaced seed methodology is implemented in our PatternHunter software, as well as most other modern homology search software, serving thousands of queries daily. We also introduce ZOOM that maps short reads of 5x coverage of a human genome in a CPU-day.

Joint work with Bin Ma, John Tromp, X.F. Cui, B. Brejova, T. Vinar, D. Shasha