Super Seeds for Fast and Sensitive Homology Search

Speaker:	Prof. Ming Li
 		Canada Research Chair in Bioinformatics
 		School of Computer Science
 		University of Waterloo and City Univ. of HK

Topic:		"Super Seeds for Fast and Sensitive Homology Search"

Date:		Friday, 26 November 2004

Time:		2:00 pm - 3:00 pm

Venue:		Lecture Theatre E
 		(Cheung On Tak Lecture Theatre,
		Chia-Wei Woo Academic Concourse)
 		HKUST

Abstract:

Homology search, finding similar parts between two sequences, is the most
basic and popular task in bioinformatics. A large fraction of the world's
supercomputing time is consumed by homology search. We introduce the
fundamental ideas and the mathematical theory of optimized spaced seeds.
Based on such ideas, our software PatternHunter is significantly faster
than current homology search tools such as BLAST, at higher sensitivity,
or Smith-Waterman dynamic programming, at its full sensitivity. The
optimal spaced seeds are directly benefiting thousands of researchers in
the world, daily.


(Joint work with Bin Ma and John Tromp)



**********************
Biography:

Ming Li is a CRC Chair Professor in Bioinformatics, of Computer Science at
the University of Waterloo. He is a recipient of Canada's E.W.R. Steacie
Fellowship Award in 1996, and the 2001 Killam Fellowship. Together with
Paul Vitanyi they pioneered applications of Kolmogorov complexity and
co-authored the book "An Introduction to Kolmogorov Complexity and Its
Applications" (Springer-Verlag, 1993, 2nd Edition, 1997). He is a
co-managing editor of Journal of Bioinformatics and Computational
Biology. He currently also serves on the editorial boards of Journal of
Computer and System Sciences, Information and Computation, SIAM Journal on
Computing, Journal of Combinatorial Optimization, Journal of Software, and
Journal of Computer Science and Technology.