String Searching

The string searching problem is to find a string or pattern such as the polyadenylation concensus signal "AATAAA" in a body of text such as a gene.

String matching can be used to find: Start and stop codons Polyadenylation consensus signals Consensus transcription factor binding sites (see the TRANSFAC database)
In our introduction to string matching, we will illustrate issues of algorithm design and analysis from the perspective of computer science and mathematics.
Those interested in further information are referred to the following book:: Dan Gusfield, Algorithms on Strings, Trees and Sequences, Cambridge University Press, 1997. This is a very readable book about algorithms in computational biology. Of particular interest to this lecture are Chapters 1 and 2.