WikiDer > Sequenzausrichtung

Sequenzausrichtung (Englisch: Sequenzausrichtung) ist das Zusammenfügen von zwei oder mehr organischSequenzen so dass Ähnlichkeiten und Unterschiede zwischen den Sequenzen sichtbar werden. Diese Art der Ausrichtung wird in der Biologie normalerweise Computern überlassen und ist ein bekanntes Konzept in der Biologie Bioinformatik.

Die Sequenzen, Sequenzen von DNA oder Protein, werden in der Regel untereinander platziert. Ähnliche Teile bzw. Nukleotide und Aminosäuren, sind durch vertikale Balken miteinander verbunden.

Ein Beispiel für das Alignment zweier NukleotideSequenzen:

 tcctctgcctctgccatcat---caaccccaaagt |||| ||| ||||| ||||| |||||||||||| tcctgtgcatctgcaatcatgggcaaccccaaagt

Die Sequenzausrichtung ist wichtig für die Überprüfung evolutionär, strukturell und funktional Ähnlichkeiten in den Sequenzen biologischer Moleküle. Zum Beispiel Verwandtschaft (Homologie) von Sequenzen (durch Genduplikation (Genduplikation) oder von Artbildung (Artbildung) nachgewiesen werden.

Fehler (Nichtübereinstimmungen), die normalerweise durch das Fehlen eines vertikalen Balkens zwischen zwei Elementen dargestellt wird, kann erklärt werden durch Mutationen; Löcher (Lücken), dargestellt durch horizontale Linien, durch Einfügungen oder Löschungen. Diese Löcher werden auch "Indels" genannt, a Silbenwort das kommt von den Begriffen "Einfügen" und "Löschen".

Auch außerhalb der Bioinformatik sind Anwendungen möglich, zum Beispiel im Studium der study Sprachaffinität und Textvergleich.

Dynamische Algorithmen

Dynamisch Algorithmen kann helfen, das beste Alignment zwischen verschiedenen Sequenzen zu bestimmen. Die Algorithmen verwenden sogenannte Substitutionsmatrizen, in denen für jede Substitution eines Nukleotids/Aminosäure in ein anderes (Mismatch) und dasselbe (Match) ein Wert angegeben wird. Es gibt auch einen Wert für ein Indel. Eine Übereinstimmung erhält einen günstigeren Wert als ein Indel und eine Nichtübereinstimmung. Das plausibelste Alignment ist dann das Alignment mit der günstigsten Gesamtpunktzahl. Ein Mismatch und Indel verringern die Ähnlichkeit zwischen Sequenzen, was eine weniger günstige Bewertung erklärt.

Die Ausrichtung kann global oder lokal sein. Biene global Alignment werden alle Elemente verwandter Sequenzen berücksichtigt. Biene lokal Alignments können die betrachteten Sequenzen stark gegeneinander verschoben sein, so dass verschobene Domänen (Domain-Shuffling) kann wieder zusammengebaut werden. Bei einem Alignment zweier Sequenzen wird für jede Sequenz eine Untermenge gesucht, wobei beide Untermengen das größtmögliche globale Alignment aufweisen. Es wird also eine lokale Ähnlichkeit gesucht, wobei der Rest der Sequenz nicht berücksichtigt wird und somit den Score nicht negativ beeinflusst. Im Allgemeinen ist ein globaler Algorithmus am besten für Sequenzen mit mittlerer bis hoher Ähnlichkeit geeignet, während ein lokaler Algorithmus eher für Sequenzen mit mittlerer bis niedriger Ähnlichkeit geeignet ist. Vor allem, wenn ganze Domains in einer Sequenz getauscht oder hinzugefügt wurden.

Globale Ausrichtung

Der Unterschied ist das Ergebnis zwischen lokalem und globalem Alignment für die gleichen Sequenzen.

Ein häufig verwendeter Algorithmus zum Vergleichen zweier vollständiger Sequenzen ist der Needleman-Wunsch-Algorithmus. Dabei werden zwei Folgen in a Matrixform platziert: eine Sequenz horizontal, die andere vertikal, wie in der folgenden Tabelle:

Von dort erhält jede Box in der Matrix eine bestimmte Punktzahl. Es beginnt bei Null, danach wird jedes zweite Quadrat gefüllt. Jedes Match, Mismatch und Indel wird gemäß der Substitutionsmatrix bewertet. Jede Box erhält nun einen der folgenden Werte:

• Der Wert des Kästchens diagonal oben links plus der Ersatzwert des Kästchens selbst. Wenn die Box beispielsweise ein A (Sequenz 1) gegenüber einem A (Sequenz 2) platziert, ist dieser Wert positiv. Ein Mismatch, zum Beispiel ein A gegen ein C, wird weniger gut punkten.
• Der Wert des obigen Kästchens plus dem Wert eines Indels. Es wird hier davon ausgegangen, dass zum Erreichen der Box ein Indel in der horizontalen Reihenfolge für die beste Ausrichtung zwischen den beiden erforderlich ist.
• Der Wert des linken Kästchens plus dem Wert eines indel. Wie im vorherigen Punkt, aber dann ein Layout in der anderen Reihenfolge.

Die Box erhält immer den Wert dieser drei Möglichkeiten, der die günstigste Punktzahl ergibt (je nach gewählter Matrix kann dies sowohl das Minimum als auch das Maximum sein). Eine erweiterte Version, die Originalversion, dieses Algorithmus berücksichtigt auch die Länge von Indels. Bei zwei oder mehr Indels wird nicht der Wert des Indels in die Berechnung verwendet, sondern a Funktion die die Anzahl der aufeinanderfolgenden Indel berücksichtigt. Dies hat auch einen biologischen Wert: Es ist wahrscheinlicher, dass ${displaystyle n}$ indels fand gleichzeitig statt in ${displaystyle n}$ getrennte Zeiten.

Schließlich wird das Feld in der unteren rechten Ecke so ausgefüllt. Die Reihenfolge wird also rückwärts bestimmt: Der Wert des Kästchens rechts unten ergibt sich aus einer der drei Möglichkeiten. Dann wird die bewusste Möglichkeit untersucht: Kommt der Wert aus einer Substitution (Match oder Mismatch), dann ist die günstigste Ausrichtung diejenige, bei der sich die letzten Elemente der Ausrichtung gegenüberliegen. Kommt der Wert aus dem Kästchen oberhalb oder links vom betrachteten Objekt, wird ein Format in die Ausrichtung gelegt. Im nächsten Schritt wird dann dieses vorherige Kästchen angeschaut, wonach der Vorgang bis links oben wiederholt wird.

Lokale Ausrichtung

Eine Illustration des Smith-Waterman-Algorithmus

Der bekannteste lokale Alignment-Algorithmus ist eine Variante des Needleman-Wunsch-Algorithmus: der Smith-Waterman-Algorithmus. Der große Unterschied besteht darin, dass hier keine "ungünstigen" Noten vergeben werden. Ein Indel und eine Nichtübereinstimmung erhalten den Wert Null; nur ein Match bekommt ein günstig Wert. Die Matrix wird auf die gleiche Weise gefüllt, aber jetzt wird der günstigste Wert in der Matrix berücksichtigt. Von dort wird es dann auf die gleiche Weise zu den vorherigen Schritten zurückgeführt, die den bewussten Wert bestimmt haben. Dadurch entsteht letztendlich die lokale Ausrichtung.

Als Erweiterung können die Teile, die außerhalb der Ausrichtung liegen, auch lokalen Ausrichtungen in einem in unterzogen werden iterativer Prozess.

Substitutionsmatrizen

Bekannte Aminosäuresubstitutionsmatrizen basieren auf der PAM- und BLOSUM-Matrix. Darin wird jeder Aminosäure ein Wert für die Substitution dieser Aminosäure in einer der Aminosäuren zugeordnet. Der Wert gibt die Wahrscheinlichkeit wieder, mit der die Aminosäure in einer Sequenz durch die zweite – nicht unbedingt unterschiedliche – Aminosäure ersetzt wird.

PAM

Die Werte in PAM-Matrizen basieren auf Vergleichen zwischen eng verwandten Aminosäureketten. PAM steht für "point Accepted mutation", ein Maß für den Unterschied zwischen Sequenzen. Ein PAM ist der Unterschied, der auftritt, wenn sich 1% der Aminosäuren ändern. Der Wert einer Zelle, angenommen ${Anzeigestil (i, j)}$, in der Matrix steht für das beobachtete Frequenz mit welcher Aminosäure ${Anzeigestil i}$ durch Aminosäure ersetzt ${Anzeigestil j}$. Zum Beispiel hat die PAM-Matrix für die Zelle für R-R den Wert 0,9913, was bedeutet, dass 99,13% der Arginin (R) Ein Arginin verblieb im beobachteten Fall, bei dem 1% der Aminosäuren verändert waren. Die Zelle für R-N ist 0,0001, was bedeutet, dass 1% der Arginine in Asparagine (N) im gleichen Fall geändert.

Die Matrix, die eine Veränderung von 1% betrachtet, wird als PAM-1 bezeichnet. Indem man PAM-1 mit sich selbst nimmt multiplizieren, PAM-2 wird erhalten. In ähnlicher Weise lässt sich dies auf PAM verallgemeinern.${displaystyle n}$. Zum Beispiel sind 250 PAM-Einheiten jedoch nicht zu 250 % veränderte Aminosäuren; es bedeutet, dass die Menge an Veränderung, die für jede Aminosäure erforderlich ist, im Durchschnitt das 2,5-fache beträgt mutiert.

Diese Werte können dann in einem Alignment-Algorithmus verwendet werden. Der Ersatzwert hängt nun von der PAM-Matrix ab (siehe Punkt 1 in den Algorithmen). Somit wird "a"-Match und "a"-Mismatch nicht ein fester Wert zugeordnet, sondern der biologische Hintergrund berücksichtigt: Manche Übereinstimmungen und manche Mismatches treten in der Realität häufiger auf als andere, was mit PAM berücksichtigt wird. Genauer gesagt wird der neue Ersatzwert wie folgt aussehen: ${displaystyle s_{i,j}=lceil {10log_{10}{dfrac {m_{i,j}}{p_{j}}}}ceil }$. Hier ist ${displaystyle m_{i,j}}$ für den Wert in der gewählten PAM-Matrix (PAM-1, PAM-2 ...) und ${displaystyle p_{j}}$ ist der relative Frequenz von Aminosäure ${Anzeigestil j}$.

Je weniger die ausgerichteten Sequenzen verwandt sind, desto höher ist die bevorzugte PAM-Matrix.

BLOSUM

BLOSUM ist ein Akronym das steht für Blumecks substitution ichatrix. Die in der Matrix verwendeten Werte basieren auf einem multiplen Alignment (Alignment mehrerer Sequenzen aneinander) von konservierte Sequenzen (Sequenzen, die sich über Generationen und Arten nur geringfügig unterscheiden). Dem Namen der BLOSUM-Matrix folgt eine Zahl, genau wie bei PAM. BLOSUM 62 bedeutet hier zum Beispiel, dass die Werte auf Basis von Sequenzen ermittelt wurden, die zu 62 % identisch sind. Je weniger verwandt die verglichenen Sequenzen sind, desto niedriger ist die zu verwendende BLOSUM-Matrix; genau das Gegenteil von PAM.

Heuristiken

Die Needleman-Wunsch- und Smith-Waterman-Algorithmen können auf praktische Probleme stoßen. Sie bieten zwar die optimale Ausrichtung für das gegebene Bewertungssystem, aber die Komplexität davon ist relativ hoch. Sie haben ein Komplexität der Größenordnung ${Anzeigestil O(n imes m)}$, weil jedes Mal eine Matrix der Größe ${displaystyle n}$ auf ${displaystyle m}$ Muss ausgefüllt sein. In der Praxis können diese Werte Tausende von Zeichen lang sein. Dies ist rechenintensiv, macht die Implementierung (zu) rechentechnisch schwierig und wird insbesondere praktische Probleme aufwerfen, wenn eine Sequenz mit vielen anderen Sequenzen verglichen wird. Um die Rechenintensität zu reduzieren, wird häufig von Heuristiken. Dadurch wird der Suchprozess drastisch reduziert, allerdings mit dem Risiko, die beste Ausrichtung zu verpassen. Mit einer guten Heuristik ist dieses Risiko begrenzt und in der Praxis vernachlässigbar. Bekannte heuristische Algorithmen sind SCHNELL und SPRENGEN. Sie machen nicht nur eine Ausrichtung, sondern haben auch einen Wert für waarde statische Anwendbarkeit zur Ausrichtung. Es bleibt jedoch eine gewisse Chance, Fehlalarm Existenz: Suche nach a Homologie wo es nicht wirklich da ist.

SCHNELL

FASTA unterteilt die Sequenzen in sogenannte ${displaystyle k}$-Tupel, wo ${displaystyle k}$ ist eine natürliche Zahl. Die Sequenzen sind in Gruppen von aufgeteilt ${displaystyle k}$ Elemente (Buchstaben). Jeder möglichen Kombination wird ein eindeutiger Wert zugewiesen. Jedes gebildete Tupel erhält außerdem eine Sequenznummer, die seinen Platz in der Sequenz definiert. Dann werden die Sequenzen verglichen. Bei übereinstimmenden Werten wird der Unterschied in der Sequenznummer berücksichtigt. Häufige Unterschiede weisen auf Ähnlichkeiten zwischen den Sequenzen hin. Die größten Ähnlichkeitsbereiche werden dann unter Verwendung eines Bewertungssystems mit einer Substitutionsmatrix und unter Zulassen von Lücken zwischen den verknüpften Bereichen miteinander verglichen.

Die Komplexität des Algorithmus bleibt in den häufigsten Fällen in der Größenordnung ${Anzeigestil O(n)}$.

SPRENGEN

FASTA arbeitet mit exakten Übereinstimmungen zwischen den ${displaystyle k}$-tuples, BLAST ist diesbezüglich jedoch etwas flexibler. Es werden nicht nur exakte Übereinstimmungen berechnet, sondern auch Ähnlichkeiten, die innerhalb bestimmter Grenzen gewählt werden können. Die Ähnlichkeiten zwischen den Tupeln werden unter Verwendung einer Substitutionsmatrix mit einem Wert versehen. Ist dieser Wert besser als der vorgegebene Grenzwert, werden die Tupel in den weiteren Prozess einbezogen.

BLAST wendet zuerst die Heuristik an und muss dann nur mit einem Teil des ursprünglichen Problems arbeiten. Auch bei BLAST liegt die Komplexität in der Größenordnung ${Anzeigestil O(n)}$.

Mehrfachausrichtung

Das Alignment ist nicht auf den paarweisen Vergleich, d. h. zwei Sequenzen, beschränkt, sondern kann auch auf das gleichzeitige Alignment mehrerer Sequenzen angewendet werden. Die Grundidee bleibt die gleiche: Gesucht wird, wie die Sequenzen untereinander dargestellt werden können, damit ihre Beziehung deutlich wird. Wie beim paarweisen Alignment kann dem Alignment ein Bewertungswert zugewiesen werden. Eine Möglichkeit, jede ausgerichtete Spalte auszuwerten, besteht darin, jede Sequenz für die jeweilige Spaltenposition miteinander zu vergleichen und zu addieren. Dies bedeutet, dass ${displaystyle {dbinom {k}{2}}}$ (ein mathematische Kombination) Paare werden verglichen, wobei ${displaystyle k}$ steht für die Anzahl der Sequenzen.

Die Alignments selbst können mit Erweiterungen der paarweisen Alignmentalgorithmen (sowohl der Heuristik als auch der anderen) erstellt werden. Statt zwei Maße zu arbeiten, dann wird mit ${displaystyle k}$ Maße gearbeitet. Allerdings wird auch die Komplexität zunehmen. Für den Smith-Waterman-Algorithmus wird für jedes Element in der Matrix eine Berechnung der Größenordnung ${displaystyle Oleft(2^{k}ight)}$ erforderlich. Für die gesamte Matrix bedeutet dies eine Komplexität in der Größenordnung ${displaystyle Oleft(2^{k}n^{k}ight)}$, bei welchem ${displaystyle n}$ repräsentiert die Länge der Sequenzen.

In realistischen Situationen ist dies zu komplex, um nützlich zu sein. In der Praxis wird daher oft ein anderer Ansatz gewählt: die Suche nach Konsensussequenzen. Die beiden ähnlichsten Sequenzen werden gesucht und ein Konsens erstellt. Es ersetzt die beiden Sequenzen, wonach das Verfahren wiederholt wird, wobei der Konsens eine der zu berücksichtigenden Sequenzen ist. Durch erneutes Trennen der Konsensussequenzen nach dem letzten Alignment wird das Alignment erhalten. Tatsächlich, während der Suche, a Baumstruktur erstellt, die die Leitbaum heißt, eine Näherung von a Stammbaum. Die Blätter dieser Struktur sind dann die Sequenzen, die anderen Knoten sind die gebildeten Konsensus. Die Wurzel dieses Baums ist dann der Konsens aller Sequenzen. Die Mehrfachausrichtung wird dann basierend auf diesem gebildeten Baum eingerichtet. Algorithmen, die dieses Prinzip verwenden, können sich in der Art und Weise unterscheiden, wie der Konsens bestimmt wird und wie der Baum aufgebaut ist.

Bei der Suche nach Konsensussequenzen, wie z ${displaystyle {dbinom {k}{2}}}$ paarweise Alignments durchgeführt, was die obere Schranke ist ${displaystyle k^{2}}$ hast. Multipliziert man dies mit der Größenordnung, mit der eine paarweise Alginierung durchgeführt wird, ergibt sich die Gesamtgrößenordnung. Für BLAST oder FASTA ist dies eine Bestellung in der Nähe von ${displaystyle Oleft(k^{2}Nacht)}$. Ein Nachteil dieses Verfahrens besteht darin, dass Ausrichtungsfehler in einer Anfangsphase auf die folgenden Phasen übertragen werden. Es gibt Algorithmen, die versuchen, dieses Problem mit anzugehen iterativ Ausrichtungsalgorithmen, so dass Fehler in einem vorherigen Schritt korrigiert werden. Dies ist jedoch nicht immer der Fall konvergiert, wodurch es nützlich ist, die maximale Anzahl von Iterationen vorzugeben, die ausgeführt werden darf.

Das Auffinden von Konsensussequenzen erfolgt, indem nach der wahrscheinlichsten evolutionären Veränderung zwischen zwei verglichenen Sequenzen gesucht und diese innerhalb des gesamten Alignments abgeglichen wird. Es muss ein Kompromiss zwischen beiden gesucht werden.

Multiple Alginierung wird hauptsächlich verwendet, um strukturelle oder funktionelle Beziehungen zwischen Sequenzen und Sequenzfamilien zu suchen. Beispielsweise können variable und konservierte Stellen in Proteinfamilien gefunden werden und es kann Informationen über evolutionär Geschichte.

Ein bekanntes Programm zur Durchführung von Mehrfachausrichtungen ist Cluster.

Externe Links

• Explosionsserver von dem NCBIA
• Tutorial zum BLAST-Algorithmus und zur statistischen Signifikanz von Sequenzausrichtungen im Allgemeinen
• Jligner: Open Source-JavaProgramm von dynamische Programmierung-Algorithmus Smith-Waterman zur paarweisen Ausrichtung