Sequenz-Alignment-Algorithmen

Sequenz-Alignment-Algorithmen messen und zeigen die Ähnlichkeit zwischen zwei Zeichenketten, indem sie den kostengünstigsten Weg finden, eine in die andere umzuwandeln, unter Verwendung dynamischer Programmierung über Einfügungen, Löschungen und Substitutionen.

Definition

Sequenz-Alignment ist die Anordnung von zwei (oder mehr) Zeichenketten, um ihre Korrespondenz durch Einfügen von Lücken und Abgleichen, Nicht-Abgleichen oder Ersetzen von Zeichen zu maximieren; ein Alignment-Algorithmus berechnet ein optimales Alignment und dessen Score unter einem gegebenen Kosten- oder Bewertungsmodell, typischerweise mittels dynamischer Programmierung.

Scope

Dieses Thema behandelt die Algorithmen der dynamischen Programmierung zum Vergleich von Zeichenketten: Editier-(Levenshtein-)Distanz und die längste gemeinsame Teilsequenz, globales Alignment (Needleman-Wunsch), lokales Alignment (Smith-Waterman) und die Bewertungsmodelle (Gap-Penalties, Substitutionsmatrizen), die biologische Alignments prägen. Es behandelt die zugrunde liegende Rekursion und ihre quadratische Zeit- und Raumkomplexität sowie platzsparende Verfeinerungen. Indexbasierte und exakte Matching-Methoden werden in verwandten Themen behandelt.

Core questions

• Wie wird die Ähnlichkeit zwischen zwei Zeichenketten als Editierdistanz oder Alignment-Score quantifiziert?
• Wie berechnet eine dynamische Programmierungs-Tabelle ein optimales Alignment?
• Was unterscheidet globales Alignment von lokalem Alignment, und wann ist jedes davon angemessen?
• Wie beeinflussen Gap-Penalties und Substitutionsmatrizen das resultierende Alignment?
• Wie kann der quadratische Speicherbedarf für lange Sequenzen reduziert werden?

Key concepts

• Editier-(Levenshtein-)Distanz
• längste gemeinsame Teilsequenz
• globales Alignment
• lokales Alignment
• Needleman-Wunsch-Algorithmus
• Smith-Waterman-Algorithmus
• Gap-Penalties
• Substitutionsmatrizen

Key theories

Globales Alignment durch dynamische Programmierung

Der Needleman-Wunsch-Algorithmus füllt eine dynamische Programmierungs-Tabelle, deren Einträge den besten Alignment-Score von Zeichenkettenpräfixen angeben, was ein optimales End-to-End (globales) Alignment von zwei Sequenzen in einer Zeit liefert, die proportional zum Produkt ihrer Längen ist.

Lokales Alignment für gemeinsame Teilsequenzen

Der Smith-Waterman-Algorithmus modifiziert die Rekursion, um Alignments zu ermöglichen, die überall beginnen und enden können, und findet die am höchsten bewertete übereinstimmende Region (lokales Alignment), was entscheidend ist, um konservierte Fragmente innerhalb ansonsten unähnlicher Sequenzen zu erkennen.

Clinical relevance

Sequenz-Alignment ist ein Eckpfeiler der Bioinformatik und wird zum Vergleich von DNA-, RNA- und Proteinsequenzen hinsichtlich Homologie, evolutionärer Rückschlüsse und Datenbanksuche verwendet (der heuristische BLAST baut auf lokalem Alignment auf). Außerhalb der Biologie treibt dieselbe Editierdistanz-Maschinerie die Rechtschreibprüfung, das Fuzzy-Text-Matching, Versionskontroll-Diffe und den Vergleich von Sprache und Handschrift an.

History

Levenshtein führte die Editierdistanz 1965 ein. Needleman und Wunsch präsentierten 1970 den ersten dynamischen Programmierungsalgorithmus für das globale Alignment von Proteinen, und Smith und Waterman führten 1981 das lokale Alignment ein. Hirschbergs Linearspeichertechnik (1975) und spätere Heuristiken wie BLAST erweiterten das Alignment für den großtechnischen praktischen Einsatz.

Key figures

• Saul Needleman
• Christian Wunsch
• Temple Smith
• Michael Waterman
• Vladimir Levenshtein

Seminal works

• needleman1970
• smith1981
• gusfield1997

Frequently asked questions

Was ist der Unterschied zwischen globalem und lokalem Alignment?

Globales Alignment (Needleman-Wunsch) gleicht zwei Sequenzen von Ende zu Ende ab und ist angemessen, wenn sie ähnliche Längen haben und voraussichtlich durchgehend verwandt sind. Lokales Alignment (Smith-Waterman) findet die am besten passende Unterregion und ist angemessen, wenn nur Teile der Sequenzen ähnlich sind, wie z. B. eine konservierte Domäne innerhalb größerer Sequenzen.

Ist Sequenz-Alignment dasselbe wie die längste gemeinsame Teilsequenz?

Sie sind eng verwandt. Die längste gemeinsame Teilsequenz ist ein Sonderfall des Alignments mit einer bestimmten Bewertung (Übereinstimmungen werden belohnt, Lücken sind kostenlos, Nicht-Übereinstimmungen sind nicht erlaubt). Das allgemeine Alignment verwendet eine reichere Bewertung mit Substitutionskosten und Gap-Penalties, aber beide werden durch dieselbe Art von dynamischer Programmierungs-Rekursion gelöst.