Dan Gusfield

DIMACS Center - Rutgers University
Piscataway, New Jersey

Topic of Discussion

Discrete algorithms that operate on strings provide the closest intersection between classical theoretical computer science and modern molecular biology. These well known algorithms, or close relatives, are at the heart of systems that search sequence databases (DNA or protein), and use of these databases has become essential in a many subfields of modern biology. It is natural then that string algorithms have attracted the attention of many computer scientists entering the field of computational biology. However, strings provide only a partial reflection of molecular biology and discrete string algorithms are somewhat restricted in the kinds of biological questions they can address. While there are many valid applications for discrete string algorithms in molecular biology, it is important to understand the limitations as well as the opportunities. In this lecture I will review some history, successes, failures, pitfalls and potentials of using string algorithms in molecular biology. I will pay particular attention to problems of multiple string comparisons.


Document last modified on October 31, 1994