Sequenzalignment

Ein Alignment (englisch: Abgleich, Anordnung, Ausrichtung), im Deutschen oft auch Alinierung genannt, dient dem Vergleich zweier oder mehrerer Strings (technischer Begriff für Zeichenfolge, Sequenz) und wird besonders häufig in der Bioinformatik und der molekularen Phylogenie verwendet, um die funktionelle oder evolutionäre Verwandtschaft (Homologie) von Nukleotidsequenzen- oder Aminosäuresequenzen zu untersuchen. Sequenzalignments sind ein Teilgebiet des Pattern Matchings.

Weiteres empfehlenswertes Fachwissen

Tägliche Sichtkontrolle der Laborwaagen

Wie kann man Pipetten schnell überprüfen?

Sicherer Wägebereich zur Sicherstellung genauer Resultate

Das Prinzip

Es gibt automatisierte Alignmentmethoden, man kann kleinere Datensätze jedoch auch manuell alignen. Die manuelle Methode ermöglicht eine größere Sorgfalt und den Ausschluss von hochvariablen und somit nicht alignbaren Positionen, die spätere Analysen stören würden. Beim Alignment ordnet man die Elemente eines untersuchten Strings denen des/der anderen Strings so zu, dass die Reihenfolge erhalten bleibt und jedes Element einem anderen Element oder einem Gap (Leerstelle, Lücke) in jedem String zugeordnet ist. Eine Fehlpaarung in dem Alignment entspricht einer Mutation. Die Gaps hingegen weisen auf eine Deletion oder eine Insertion hin. Die einander zugeordneten (alignierten) Elemente sollten identisch oder möglichst ähnlich sein, weil viele gleiche oder ähnliche Elemente in gleicher Reihenfolge auf eine evolutionäre oder funktionelle Verwandtschaft hinweisen. Die Ähnlichkeit der Elemente wird meist vorgegeben und hängt von den Eigenschaften der verwendeten Daten oder Scoring Matrizen ab. Damit ein sinnvolles Alignment möglich ist und da die Sequenzen oft unterschiedlich lang sind, dürfen Gaps in die Sequenzen eingefügt werden.

Das Alignment von zwei Sequenzen wird als paarweises Alignment bezeichnet, das von mehreren als multiples Alignment. Beim paarweisen Alignment unterscheidet man weiterhin zwischen globalem, lokalem und semiglobalem Alignment.

Kostenfunktion bei automatisierten Alignment

Um ein Alignment bewerten zu können, gibt es eine Kostenfunktion (alignment score), die meist gleiche und ähnliche alignierte Elemente positiv und sich stärker unterscheidende Kombinationen weniger positiv bis leicht negativ bewertet. Gaps werden ebenfalls negativ bewertet, allerdings gibt es so genannte affine Gap-Scores, die ein langes Gap weniger schlecht bewerten als mehrere kurze.

Beispiel

-AAACGG
AAAACCG

Das oben dargestellte Alignment von zwei kurzen DNA-Sequenzen zeigt an der ersten Position (-A), dass ein Gap eingefügt werden kann, um Längenunterschiede auszugleichen. Das Gap wurde am Anfang der oberen Sequenz eingefügt und nicht in der Mitte, weil es aus der Sicht der Biologie wahrscheinlicher ist, dass eine Sequenz an den Enden mutiert als in der Mitte.

An der vorletzten Stelle wurden C und G aligniert, da in der DNA durchaus Mutationen möglich sind, in denen statt eines C versehentlich ein G eingebaut wird, oder umgekehrt. Es wäre auch möglich gewesen, G und C jeweils mit einem Gap in der anderen Sequenz zu alignieren. Diese Entscheidung hängt von der verwendeten Kostenfunktion ab.

Beim Proteinsequenzalignment entsprechen die Aminosäuresequenzen den Strings. Die Kostenfunktionen für die Ähnlichkeiten der einzelnen Aminosäuren untereinander sind etwas komplexer als bei der DNA.

Paarweises Alignment

Zwei homologe Sequenzen sollen derart untereinander geschrieben werden, dass jeweils homologe Symbole untereinander stehen. Dazu werden gegebenenfalls die oben erwähnten Lückensymbole "-" eingefügt. Ein Alignment zweier Sequenzen S, T wird als (S*, T*) notiert. Dabei ist S* die Verlängerung von S, bei der ausschließlich Lückensymbole eingefügt werden. T* ist eine entsprechende Verlängerung von T. Das Alignment zweier Lückensymbole ist nicht zulässig.

Globales Alignment

Bei einem globalen Alignment zwischen zwei Sequenzen werden alle Symbole berücksichtigt. Globale Alignments werden hauptsächlich verwendet, wenn die zu untersuchenden Sequenzen ähnlich lang sind und starke Sequenzhomologien erwartet werden.

Um ein optimales Alignment zu erkennen wird eine Bewertungsfunktion (engl. score) verwendet. In einfachster Form (sollte aber den Bedürfnissen des Modells angepasst werden):

• match: score +1 (die beiden untereinanderstehenden Buchstaben stimmen überein)
• mismatch: score -1 (keine Übereinstimmung)
• gap: score -2 (gap penalty, "Insert or Deletion")

Allgemein gilt, der Gesamtscore ist die Summe aller match-, mismatch, und gap-scores.

Das Alignment mit dem höchsten Score ist ein optimales Alignment. Dieses zu finden ist ein Optimierungsproblem, welches beim paarweisen Alignment mit der Methode der dynamischen Programmierung (Needleman-Wunsch-Algorithmus) relativ effizient gelöst werden kann.

Beispiel

• Gegeben: Zwei Sequenzen S und T.
• Annahme: S und T haben gemeinsame Vorfahren (sind homolog).
• Frage: Welche Positionen in S und T sind homolog?

Für S = GAC und T = GC sind mögliche Lösungen:

GAC
GC-

GAC--
---GC

GAC
G-C

Lokales Alignment

Methoden zum Finden von lokalen Alignments werden verwendet, wenn zwei Sequenzen auf Homologien untersucht werden sollen, jedoch keine Übereinstimmung auf der gesamten Länge der Sequenz zu erwarten ist. Das heißt ein lokales Alignment ist auf Teilbereiche der Sequenz beschränkt. Beispiele sind hierbei die Suche nach gleichen Sequenzmotiven oder Domänen bei Proteinen. Ein bekannter Algorithmus zur Berechnung von lokalen Alignments ist der Smith-Waterman-Algorithmus. Hierfür wird eine Scorefunktion verwendet. Es geht darum Ähnlichkeiten zu maximieren anstatt Unterschiede zu minimieren.

Semiglobales Alignment

Bei stark unterschiedlich langen Sequenzen sollte nach semiglobalen Alignments gesucht werden. Für die Berechnung des Score berücksichtigt man nur die internen Gaps, nicht die Terminalen.

Multiples Sequenzalignment

Während das optimale Alignment von 2 Sequenzen mit Hilfe eines Computers recht schnell (d.h. in polynomieller Zeit) exakt berechnet werden kann (Laufzeit O(nm), n und m sind die Längen der Sequenzen), ist dies beim multiplen Sequenzalignment (engl. multiple sequence alignment) nicht mehr möglich, da die Laufzeit des Algorithmus zur exakten Berechnung des multiplen Alignment mit der Anzahl der Sequenzen exponentiell wächst (O(2^kn^k), wobei k die Anzahl der Sequenzen und n die längste der zu vergleichenden Sequenzen ist).

Um jedoch ein biologisch bzw. evolutionär sinnvolles Alignment berechnen zu können, aus dem sich tatsächlich Gemeinsamkeiten und Unterschiede in Sequenz, Struktur und Funktion ableiten lassen, braucht man viele lange Sequenzen. Deshalb werden Heuristiken verwendet, beispielsweise sogenannte Progressive Strategien (auch Hierarchische Methoden genannt). Hierbei werden zunächst alle optimalen paarweisen Alignments der zu untersuchenden Sequenzen berechnet und daraus durch Clusteranalyse (zum Beispiel unter Verwendung eines Neighbour-Joining-Algorithmus) ein phylogenetischer Baum abgeleitet (der sogenannte Guide Tree). Entlang dieses Baumes wird schließlich schrittweise (progressiv, nach dem Prinzip eines Greedy-Algorithmus) ein multiples Alignment bestimmt, wobei durch dieses heuristische Vorgehen die optimale Lösung nicht garantiert ist.

Alignment-Algorithmen

• Needleman-Wunsch-Algorithmus (globales Alignment)
• Waterman-Smith-Beyer-Algorithmus (globales Alignment)
• Hirschberg-Algorithmus (globales Alignment auf linearem Speicherplatz)
• Smith-Waterman-Algorithmus (lokales Alignment)
• Gotoh-Algorithmus (globales Alignment bei affinen Gapkosten)

heuristische Algorithmen für paarweises Alignment:

• BLAST
• FASTA

heuristische Algorithmen für multiples Alignment:

• Populäre Fragment-Basierte Methode DIALIGN-T
• Hierarchische Methoden (zum Beispiel Feng-Doolittle)
• PSI-BLAST

Verwandte Themen

• Die Methode Felsenstein 81 korrigiert Distanzdaten von Sequenzalignments.

Software

Häufig genutzte Programme für allgemeine Sequenzalignments sind ClustalW und TCoffee sowie BLAST für die Datenbanksuche.

Eine umfangreiche Liste verfügbarer Software kategorisiert nach Algorithmus und Art der Alignments findet sich hier: en:sequence alignment software.

Online Interface

Das Programm STRAP integriert fast alle frei verfügbaren Programme zur Berechnung von Sequenzalignments. Diese werden automatisch installiert und sind dann mit einer komfortablen graphischen Benutzeroberfläche aufrufbar. Dadurch erspart sich der Nutzer die individuelle Installation und das Erlernen der Kommandozeilensyntax der einzelnen Programme. Da das Berechnen großer Alignments viel Zeit in Anspruch nehmen kann, werden Ergebnisse langwieriger Berechnungen im Cache gespeichert. Wenn für mindestens zwei der Proteine auch 3D-Strukturen vorhanden sind, ist die kombinierte Anwendung von Sequenzalignment und 3D-Strukturüberlagerung zu empfehlen.

Literatur

• Michael S. Waterman: Introduction to Computational Biology: Maps, Sequences and Genomes, 1995 Chapman & Hall, ISBN 0412993910
• Dan Gusfield: Algorithms on Strings, Trees, and Sequences, 1997 Cambridge University Press, ISBN 0521585198
• Andreas D. Baxevanis & B. F. Francis Ouellette (Hrsg.): Bioinformatics : a practical guide to the analysis of genes and proteins, 2001 Wiley-Interscience, ISBN 0471383910
• Andrea Hansen: Bioinformatik : Ein Leitfaden für Naturwissenschaftler, 2004 Birkhaeuser Verlag, ISBN 3764362537
• Roland Fleißner: Sequence alignment and phylogenetic inference, 2004 Logos Berlin, ISBN 3832505881
• Bernhard Haubold, Thomas Wiehe: Introduction to Computational Biology. An Evolutionary Approach, 2006 Birkhaeuser Verlag, ISBN 3764367008

Siehe auch

• Clustal
• Dotplot