Strings 2008 2 2

Pattern search

Text searching is an example of a simple problem with different algorithmic approaches. In practice most commonly one needs to check if a pattern (a short string) is contained in a larger string, and if so at which location.

Despite the simplicity of the problem, it is frequently used in bioinformatics. Examples:

• Find start (ATG) and stop (TAA, TGA and TGG) codons
• Find restriction enzyme cutting sites
• Search for PCR primer matches

Formalisation of the problem

Given a pattern p and a string s, find the first location where the pattern matches identically the string. If the pattern is not contained in the string report the outcome.

The following sections describe basic search algorithms to locate a DNA fragment in a genome. But remember that the same concepts can be applied to any pattern/string pair.

goto Brute force search

--ThomasHuber 12:28, 10 January 2008 (EST)