Finding common patterns, or motifs, in the promoter regions of co-expressed genes is an important problem in bioinformatics. Despite years of efforts in solving this problem, less than 30% of the known motifs in TRASNSFAC can be found computationally.
Motifs can be represented by strings or probability matrix. In this talk, we shall present approaches and formulations of this problem based on these two common motif representations.
The planted (l,d)-motif problem (PMP) is formulated for string representation, where l is the length of the motif and d is the maximum Hamming Distance between the similar patterns. We shall introduce new algorithms to solve this motif problem and its variations.
Finding motifs based on matrix representation is very difficult. Even for a motif length 6 or 7, there is no algorithm that can guarantee finding the exact optimal matrix from an infinite number of possible matrices. New advances in finding the optimal matrix will be discussed in this talk.
Finally, some new motif discovering algorithms, which assume extra biological knowledge and other types of representations to greatly improve performance, will be highlighted.
Professor Chin received the B.A.Sc. degree from the University of Toronto, Canada, in 1972, and the M.S., M.A. and Ph.D. degrees from Princeton University, in 1974, 1975, and 1976, respectively. Since 1975, he has taught at the University of Maryland, Baltimore County, University of California, San Diego, University of Alberta, Chinese University of Hong Kong, and University of Texas at Dallas. He joined the University of Hong Kong (HKU) in 1985, where he is the Chair of the Department of Computer Science and was the founding Head of the department from its establishment until December 31, 1999. Between 1992-1996, he served as the Associated Dean of Graduate School. In 1996, Prof. Chin was elected to the grade of IEEE Fellow. Professor Chin is currently serving as Manager Editor of the International Journal of Foundations of Computer Science and is also on the editorial boards of several journals. He has served on the program committees and as conference chairman of numerous international workshops and conferences. Professor Chin's research interests include design and analysis of algorithms, on-line algorithms, and bioinformatics.