HONG KONG BAPTIST UNIVERSITY
FACULTY OF SCIENCE
Department of Computer Science Colloquium
Constrained and Signed Longest Common Subsequences
Dr. Binhai ZHU
Montana State University
Date: June 17, 2007 (Sunday)
Time: 2:00 - 3:00 pm
Venue: SCT909, Cha Chi Ming Science Tower, Ho Sin Hang Campus
Longest Common Subsequence (LCS) is a well-known concept/structure in computer science. Its application in bioinformatics dated back to 1965. It is known that given a set $S$ of $m$ sequences of length $O(n)$, it is NP-complete to compute their LCS and when $m$ is a constant the problem can be solved in $O(n^m)$ time. On the other hand, even for $m=2$ there could be an exponential number of LCS's. In the first part of this talk, I will sketch several applications of LCS in RNA multiple structural alignment; namely, computing a constrained LCS with useful properties. In the genomic distance computation problem, each genome is typically a list of genes (signed integers). So far, almost all the research assumes that each gene appears exactly once in a genome, which is not realistic at all. The corresponding algorithmic problem is to compute the exemplar breakpoint or conserved interval distances between two or more genomes, which are both NP-complete. In the second part of the talk I will present a new version of LCS, Signed LCS, which can naturally handle both distances. Finally I will show several applications of signed LCS in (exact and approximate) exemplar genomic distance computation.
Dr. Binhai Zhu obtained his PhD from McGill University, Canada in 1994. He did his post-doc at Los Alamos National Laboratory, NM, USA between 1994 and 1996. Since 1996 he has taught in Hong Kong, Canada and USA. He is currently an associate professor and PhD program coordinator at Computer Science Department, Montana State University, USA. He has published over 70 papers in international journals and conference proceedings. He was the program committee co-chair for COCOON'2003 and received the Outstanding Research Award in College of Engineering, Montana State University in 2004 and 2005. His current research interests are bioinformatics and geometric computing.
********* ALL INTERESTED ARE WELCOME ***********
(For enquiry, please contact Computer Science Department at 3411 2385)
Department of Computer Science, Hong Kong Baptist University