Strings 2008 2 2: Difference between revisions
ThomasHuber (talk | contribs) No edit summary |
ThomasHuber (talk | contribs) No edit summary |
||
| (7 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
== Pattern search == | == 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 is contained in a larger string, and if so at which location. | 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. | Despite the simplicity of the problem, it is frequently used in bioinformatics. | ||
| Line 9: | Line 9: | ||
* Search for [http://en.wikipedia.org/wiki/PCR PCR] primer matches | * Search for [http://en.wikipedia.org/wiki/PCR PCR] primer matches | ||
The following | |||
=== Formalisation of the problem === | |||
''Given a pattern p and a string s, find the first location where the pattern matches identically the string. Report the negative outcome if the pattern is not contained in the string. | |||
'' | |||
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. For further reading, the Wikipedia also has a good article on [http://en.wikipedia.org/wiki/Text_searching Text searching] | |||
[[Strings_2008_2_3 | goto Brute force search]] | |||
--[[User:ThomasHuber|ThomasHuber]] 12:28, 10 January 2008 (EST) | |||
Latest revision as of 02:41, 10 January 2008
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. Report the negative outcome if the pattern is not contained in the string.
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. For further reading, the Wikipedia also has a good article on Text searching
--ThomasHuber 12:28, 10 January 2008 (EST)
