Pattern Matching
Unter Pattern Matching versteht man mathematisch-informatische Ansätze, folgende Fragestellungen zu beantworten:
- Wie ähnlich sind zwei oder mehrere Zeichenketten (z.B. zwei DNA-Stränge) zueinander?
- Wie müssen die Zeichenketten zueinander ausgerichtet werden?
- Wann sind zwei Zeichenketten ähnlich genug, um als gleich gewertet zu werden?
Beinahe jedes Textverarbeitungsprogramm besitzt zum Beispiel eine Suchfunktion, mit der in einem Text alle Vorkommnisse eines bestimmten Begriffs gefunden werden können.
Es wird prinzipiell zwischen "harten" und "weichen" Matchingverfahren unterschieden.
"Harte" Verfahren
Es muss jedes Zeichen eines Teils übereinstimmen.
Beispiele für Erfolg:
Sequenz 1 = ACGTGC, Sequenz 2 = ACGTGC (Vollkommene Übereinstimmung)
Sequenz 1 = ACGTCGCTTC, Sequenz 2 = GTCGC (Ein Teil der Zeichenkette (Substring) wurde gefunden)
Beispiel für Misserfolg:
Sequenz 1 = ACGTGC, Sequenz 2 = ACGGGC (In der ersten Zeichenkette steht an Position 4 ein T, in der zweiten jedoch ein G)
"Weiche" Verfahren
Es wird die Ähnlichkeit zweier Zeichenketten untersucht. Ein Ansatz dazu ist das Sequenzalignment, welches unter anderem in der Bioinformatik seine Anwendung findet.
Beispiel:
Sequenz 1 = ACGTGC, Sequenz 2 = ACGGGC (Es wird keine Aussage darüber getroffen, ob Erfolg oder Misserfolg, es wird lediglich mittels Sequenzalignments ein Richtwert für die Qualität des Vergleichs - der Score - berechnet.)