Mehrfaches Sequenz-Alignment

Die ersten 90 Positionen eines Protein-Mehrfachsequenz-Alignments von Instanzen des sauren ribosomalen Proteins P0 (L10E) aus mehreren Organismen. Generiert mit ClustalW.

EIN multiples Sequenzalignment (MSA) ist ein Sequenzausrichtung aus drei oder mehr biologischen Sequenzen, im Allgemeinen Protein , DNS , oder RNS. Im Allgemeinen wird angenommen, dass der Eingabesatz von Abfragesequenzen ein hat evolutionär Beziehung, durch die sie eine Linie teilen und von einem gemeinsamen Vorfahren abstammen. Aus der resultierenden MSA kann eine Sequenzhomologie abgeleitet und eine phylogenetische Analyse durchgeführt werden, um die gemeinsamen evolutionären Ursprünge der Sequenzen zu bewerten. Visuelle Darstellungen der Ausrichtung wie im Bild rechts veranschaulichen Mutationsereignisse wie Punktmutationen (Änderungen einzelner Aminosäuren oder Nukleotide), die als unterschiedliche Zeichen in einer einzelnen Ausrichtungsspalte erscheinen, und Insertions- oder Deletionsmutationen (oder Indels), die als Lücken erscheinen in einer oder mehreren der Sequenzen im Alignment. Multiples Sequenzalignment wird häufig verwendet, um die Sequenzkonservierung von Proteindomänen, Tertiär- und Sekundärstrukturen und sogar einzelnen Aminosäuren oder Nukleotiden zu bewerten.

Multiples Sequenzalignment bezieht sich auch auf den Prozess des Alignments eines solchen Sequenzsatzes. Weil es fast unmöglich ist, drei oder mehr Sequenzen von biologisch relevanter Länge von Hand auszurichten, rechnerisch Algorithmen werden verwendet, um die Alignments zu erstellen und zu analysieren. MSAs erfordern ausgefeiltere Methoden als paarweise Ausrichtung weil sie rechnerisch aufwendiger herzustellen sind. Die meisten Mehrfachsequenz-Alignment-Programme verwenden eher heuristische Verfahren als globale Optimierung, da das Identifizieren des optimalen Alignments zwischen mehr als ein paar Sequenzen mittlerer Länge unerschwinglich rechenintensiv ist.

Dynamische Programmierung und Rechenkomplexität

Das direkteste Verfahren zur Herstellung einer MSA verwendet die dynamische Programmiertechnik, um die global optimale Ausrichtungslösung zu identifizieren. Bei Proteinen umfasst diese Methode normalerweise zwei Sätze von Parametern: eine Lückenstrafe und eine Substitutionsmatrix, die der Ausrichtung jedes möglichen Aminosäurepaars basierend auf der Ähnlichkeit der chemischen Eigenschaften der Aminosäuren und der Evolutionswahrscheinlichkeit Punkte oder Wahrscheinlichkeiten zuweist Mutation. Für Nukleotidsequenzen kann eine Substitutionsmatrix verwendet werden, aber da es nur vier mögliche Standardzeichen pro Sequenz gibt und sich die einzelnen Nukleotide typischerweise nicht sehr in der Substitutionswahrscheinlichkeit unterscheiden, bestehen die Parameter für DNA- und RNA-Sequenzen normalerweise aus einer Lückenstrafe, einer positiven Punktzahl für Zeichenübereinstimmungen und eine negative Punktzahl für Nichtübereinstimmungen.

Zum n einzelne Sequenzen erfordert das Verfahren den Aufbau der n -dimensionales Äquivalent der Matrix, die in standardmäßiger paarweiser dynamischer Programmierung gebildet wird. Der Suchraum wächst also exponentiell mit zunehmendem n und ist auch stark von der Sequenzlänge abhängig. Um das globale Optimum für zu finden n Sequenzen auf diese Weise hat sich als NP-vollständiges Problem erwiesen. Verfahren zum Reduzieren des Suchraums, indem zuerst eine paarweise dynamische Programmierung für jedes Paar von Sequenzen im Abfragesatz durchgeführt wird und nur der Lösungsraum in der Nähe dieser Ergebnisse durchsucht wird (wobei effektiv der Schnittpunkt zwischen lokalen Pfaden gefunden wird, die jede paarweise optimale Lösung unmittelbar umgeben), wird die Technik der dynamischen Programmierung wiedergegeben effizienter. Das sogenannte 'Sum of Pairs'-Verfahren wurde im Softwarepaket MSA implementiert, ist aber für viele MSA-Anwendungen, die das gleichzeitige Alignment von Dutzenden oder sogar einigen Hundert Sequenzen erfordern, immer noch unpraktisch. Dynamische Programmiermethoden werden jetzt nur noch verwendet, wenn eine äußerst hochwertige Ausrichtung einer kleinen Anzahl von Sequenzen erforderlich ist, und als Benchmarking-Standard bei der Bewertung neuer oder verfeinerter heuristischer Techniken.

Progressive Ausrichtungskonstruktion

Ein Verfahren zum Durchführen einer heuristischen Ausrichtungssuche ist die progressive Technik (auch als hierarchisches oder Baumverfahren bekannt), die eine endgültige MSA aufbaut, indem zuerst eine Reihe von paarweisen Ausrichtungen an aufeinanderfolgend weniger eng verwandten Sequenzen durchgeführt wird. Solche Verfahren beginnen damit, zuerst die beiden am engsten verwandten Sequenzen auszurichten und dann nacheinander die nächst am engsten verwandte Sequenz in dem Abfragesatz mit dem im vorherigen Schritt erzeugten Alignment auszurichten. Das anfängliche „am stärksten verwandte“ Paar wird durch ein effizientes Clustering-Verfahren wie Neighbour-Joining basierend auf einer einfachen heuristischen Suche des Abfragesatzes mit einem Tool wie FASTA bestimmt. Progressive Techniken konstruieren daher automatisch einen Stammbaum sowie ein Alignment.

Eine wesentliche Einschränkung progressiver Methoden ist ihre starke Abhängigkeit von der anfänglichen Zuweisung der Verwandtschaft und von der Qualität der anfänglichen Ausrichtung. Die Verfahren sind somit auch empfindlich gegenüber der Verteilung von Sequenzen im Abfragesatz; Die Leistung verbessert sich, wenn die Verwandtschaft zwischen Abfragesequenzen eher ein relativ glatter Gradient als weit voneinander entfernte Cluster ist. Die Leistung verschlechtert sich auch erheblich, wenn alle Sequenzen in dem Satz ziemlich entfernt verwandt sind, weil Ungenauigkeiten in der anfänglichen Ausrichtung dann wahrscheinlicher sind. Die meisten modernen progressiven Methoden modifizieren ihre Bewertungsfunktion mit einer sekundären Gewichtungsfunktion, die Skalierungsfaktoren einzelnen Mitgliedern des Abfragesatzes auf nichtlineare Weise basierend auf ihrer phylogenetischen Entfernung von ihren nächsten Nachbarn zuweist. Eine vernünftige Wahl der Gewichtung kann bei der Bewertung der Verwandtschaft helfen und die Auswirkungen relativ schlechter anfänglicher Ausrichtungen früh in der Progression mildern.

Progressive Alignment-Methoden sind effizient genug, um sie in großem Maßstab für viele Sequenzen zu implementieren, und werden häufig auf öffentlich zugänglichen Webservern ausgeführt, sodass Benutzer die interessierenden Anwendungen nicht lokal installieren müssen. Eine sehr beliebte progressive Alignment-Methode ist die Clustal-Familie, insbesondere die gewichtete Variante ClustalW, auf die von einer großen Anzahl von Webportalen wie GenomeNet, EBI und EMBNet zugegriffen wird. Unterschiedliche Portale oder Implementierungen können sich in der Benutzeroberfläche unterscheiden und dem Benutzer unterschiedliche Parameter zugänglich machen. Clustal wird ausgiebig für die phylogenetische Baumkonstruktion und als Eingabe für die Proteinstrukturvorhersage durch Homologiemodellierung verwendet.

Eine andere übliche progressive Alignment-Methode namens T-Coffee ist langsamer als Clustal und seine Derivate, erzeugt aber im Allgemeinen genauere Alignments für entfernt verwandte Sequenzsätze. T-Coffee verwendet die Ausgabe von Clustal sowie ein anderes lokales Alignment-Programm LALIGN, das mehrere lokale Alignment-Anforderungen zwischen zwei Sequenzen findet. Die resultierende Ausrichtung und der phylogenetische Baum werden als Richtlinie verwendet, um neue und genauere Gewichtungsfaktoren zu erstellen.

Da progressive Methoden Heuristiken sind, die nicht garantiert zu einem globalen Optimum konvergieren, kann es schwierig sein, die Qualität der Ausrichtung zu bewerten, und ihre wahre biologische Bedeutung kann unklar sein. Ein sehr aktuelles semi-progressives Verfahren, das die Alignment-Qualität verbessert und keine verlustbehaftete Heuristik verwendet, während es noch in Polynomialzeit läuft, wurde im Programm PSAlign implementiert.

Iterative Methoden

Eine Reihe von Methoden zur Herstellung von MSAs bei gleichzeitiger Verringerung der Fehler, die progressiven Methoden innewohnen, werden als 'iterative' klassifiziert, da sie ähnlich wie progressive Methoden funktionieren, aber die anfänglichen Sequenzen wiederholt neu ausrichten und der wachsenden MSA neue Sequenzen hinzufügen. Ein Grund dafür, dass progressive Verfahren so stark auf ein qualitativ hochwertiges Anfangs-Alignment angewiesen sind, ist die Tatsache, dass diese Alignments immer in das Endergebnis einfließen – das heißt, wenn eine Sequenz einmal in der MSA ausgerichtet wurde, wird ihr Alignment nicht weiter betrachtet. Diese Näherung verbessert die Effizienz auf Kosten der Genauigkeit. Im Gegensatz dazu können iterative Verfahren zu zuvor berechneten paarweisen Alignments oder Sub-MSAs zurückkehren, die Teilmengen der Abfragesequenz enthalten, um eine allgemeine Zielfunktion zu optimieren, wie z. B. das Finden eines Alignment-Scores hoher Qualität.

Eine Vielzahl subtil unterschiedlicher Iterationsmethoden wurde implementiert und in Softwarepaketen verfügbar gemacht; Überprüfungen und Vergleiche waren hilfreich, aber verzichten Sie im Allgemeinen darauf, eine 'beste' Technik zu wählen. Das Softwarepaket PRRN/PRRP verwendet einen Hill-Climbing-Algorithmus, um seinen MSA-Alignment-Score zu optimieren, und korrigiert iterativ sowohl Alignment-Gewichte als auch lokal divergierende oder 'lückenhafte' Bereiche des wachsenden MSA. PRRP funktioniert am besten, wenn ein Alignment verfeinert wird, das zuvor mit einer schnelleren Methode erstellt wurde. Die Ausrichtung einzelner Motive erfolgt dann mit einer Matrixdarstellung ähnlich einem Dot-Matrix-Plot in einer paarweisen Ausrichtung. Eine alternative Methode, die schnelle lokale Ausrichtungen als Ankerpunkte oder 'Seeds' für eine langsamere globale Ausrichtungsprozedur verwendet, ist in der CHAOS/DIALIGN-Suite implementiert.

Eine dritte beliebte iterationsbasierte Methode namens MUSCLE (Multiple Sequence Alignment by Log-Erwartung) verbessert progressive Methoden mit einem genaueren Abstandsmaß, um die Verwandtschaft zweier Sequenzen zu bewerten. Das Abstandsmaß wird zwischen den Iterationsstufen aktualisiert (obwohl MUSCLE in seiner ursprünglichen Form nur 2–3 Iterationen enthielt, je nachdem, ob die Verfeinerung aktiviert war).

Versteckte Markov-Modelle

Hidden-Markov-Modelle sind probabilistische Modelle, die allen möglichen Kombinationen von Lücken, Übereinstimmungen und Nichtübereinstimmungen Wahrscheinlichkeiten zuweisen können, um die wahrscheinlichste MSA oder Menge möglicher MSAs zu bestimmen. HMMs können eine einzelne Ausgabe mit der höchsten Punktzahl erzeugen, aber auch eine Familie möglicher Ausrichtungen erzeugen, die dann auf biologische Signifikanz bewertet werden können. Da es sich bei HMMs um Wahrscheinlichkeitsrechnungen handelt, erzeugen sie nicht jedes Mal dieselbe Lösung, wenn sie auf demselben Datensatz ausgeführt werden. daher kann nicht garantiert werden, dass sie zu einer optimalen Ausrichtung konvergieren. HMMs können sowohl globale als auch lokale Ausrichtungen erzeugen. Obwohl HMM-basierte Verfahren erst vor relativ kurzer Zeit entwickelt wurden, bieten sie erhebliche Verbesserungen der Rechengeschwindigkeit, insbesondere für Sequenzen, die überlappende Regionen enthalten.

Typische HMM-basierte Verfahren funktionieren, indem sie eine MSA als eine Form eines gerichteten azyklischen Graphen darstellen, der als Graph partieller Ordnung bekannt ist und aus einer Reihe von Knoten besteht, die mögliche Einträge in den Spalten einer MSA darstellen. In dieser Darstellung wird eine Spalte, die absolut konserviert ist (d. h. alle Sequenzen in der MSA teilen sich ein bestimmtes Zeichen an einer bestimmten Position), als ein einzelner Knoten mit so vielen ausgehenden Verbindungen codiert, wie es mögliche Zeichen in der nächsten Spalte von gibt die Ausrichtung. In Begriffen eines typischen Hidden-Markov-Modells sind die beobachteten Zustände die einzelnen Alignment-Spalten, und die 'verborgenen' Zustände stellen die vermutete Vorfahrensequenz dar, von der angenommen wird, dass die Sequenzen in dem Abfragesatz abstammen. Eine effiziente Suchvariante des dynamischen Programmierverfahrens, bekannt als der Viterbi-Algorithmus, wird im Allgemeinen verwendet, um die wachsende MSA sukzessive an der nächsten Sequenz in dem Abfragesatz auszurichten, um eine neue MSA zu erzeugen. Dies unterscheidet sich von progressiven Alignment-Verfahren, da das Alignment früherer Sequenzen bei jeder neuen Sequenz-Hinzufügung aktualisiert wird. Wie progressive Verfahren kann diese Technik jedoch durch die Reihenfolge beeinflusst werden, in der die Sequenzen im Abfragesatz in das Alignment integriert werden, insbesondere wenn die Sequenzen entfernt verwandt sind.

Es sind mehrere Softwareprogramme verfügbar, in denen Varianten von HMM-basierten Verfahren implementiert wurden und die für ihre Skalierbarkeit und Effizienz bekannt sind, obwohl die ordnungsgemäße Verwendung eines HMM-Verfahrens komplexer ist als die Verwendung gebräuchlicherer progressiver Verfahren. Das einfachste ist POA (Partial-Order Alignment); Eine ähnliche, aber allgemeinere Methode ist im Paket SAM (Sequence Alignment and Modeling System) implementiert. SAM wurde als Quelle für Alignments zur Proteinstrukturvorhersage verwendet, um am CASP-Strukturvorhersageexperiment teilzunehmen und eine Datenbank vorhergesagter Proteine ​​in der zu entwickeln Hefe Art S. cerevisiae. HMM-Methoden können auch für die Datenbanksuche mit HMMer verwendet werden.

Genetische Algorithmen und Simulated Annealing

Standard-Optimierungstechniken in der Informatik – die beide von physikalischen Prozessen inspiriert wurden, diese aber nicht direkt reproduzieren – wurden ebenfalls in dem Versuch verwendet, qualitativ hochwertige MSAs effizienter herzustellen. Bei einer solchen Technik wurden genetische Algorithmen für die MSA-Produktion verwendet, um zu versuchen, den hypothetischen Evolutionsprozess, der zu der Divergenz im Abfragesatz führte, weitgehend zu simulieren. Die Methode funktioniert, indem eine Reihe möglicher MSAs in Fragmente zerlegt und diese Fragmente wiederholt neu angeordnet werden, wobei Lücken an verschiedenen Positionen eingefügt werden. Eine allgemeine Zielfunktion wird während der Simulation optimiert, am allgemeinsten die Maximierungsfunktion 'Summe von Paaren', die in auf dynamischer Programmierung basierenden MSA-Verfahren eingeführt wird. Eine Technik für Proteinsequenzen wurde im Softwareprogramm SAGA (Sequence Alignment by Genetic Algorithm) implementiert und ihr Äquivalent in RNA heißt RAGA.

Die Technik des simulierten Ausheilens, bei der eine vorhandene MSA, die durch ein anderes Verfahren hergestellt wurde, durch eine Reihe von Neuanordnungen verfeinert wird, um optimalere Bereiche des Ausrichtungsraums zu finden als den, den die eingegebene Ausrichtung bereits einnimmt. Wie bei der Methode des genetischen Algorithmus maximiert das simulierte Glühen eine objektive Funktion wie die Funktion der Summe der Paare. Simuliertes Glühen verwendet einen metaphorischen 'Temperaturfaktor', der die Geschwindigkeit bestimmt, mit der Umlagerungen fortschreiten, und die Wahrscheinlichkeit jeder Umlagerung; Die typische Verwendung wechselt Perioden mit hohen Umlagerungsraten mit relativ geringer Wahrscheinlichkeit (um weiter entfernte Regionen des Ausrichtungsraums zu erkunden) mit Perioden mit niedrigeren Raten und höheren Wahrscheinlichkeiten ab, um lokale Minima in der Nähe der neu 'kolonisierten' Regionen gründlicher zu erkunden. Dieser Ansatz wurde im Programm MSASA (Multiple Sequence Alignment by Simulated Annealing) implementiert.

Motivfindung

Anordnung der sieben Caspasen von Drosophila, die nach Motiven gefärbt sind, wie sie von MEME identifiziert wurden. Wenn Motivpositionen und Sequenzausrichtungen unabhängig voneinander generiert werden, korrelieren sie oft gut, aber nicht perfekt, wie in diesem Beispiel.

Das Auffinden von Motiven, auch als Profilanalyse bekannt, ist eine Methode zum Lokalisieren von Sequenzmotiven in globalen MSAs, die sowohl ein Mittel zum Erstellen eines besseren MSA als auch ein Mittel zum Erstellen einer Bewertungsmatrix zur Verwendung beim Durchsuchen anderer Sequenzen nach ähnlichen Motiven ist. Eine Vielzahl von Verfahren zum Isolieren der Motive wurde entwickelt, aber alle basieren auf der Identifizierung kurzer hochkonservierter Muster innerhalb des größeren Alignments und der Konstruktion einer Matrix ähnlich einer Substitutionsmatrix, die die Aminosäure- oder Nukleotidzusammensetzung jeder Position im mutmaßlichen Motiv widerspiegelt . Die Ausrichtung kann dann unter Verwendung dieser Matrizen verfeinert werden. Bei der Standardprofilanalyse enthält die Matrix Einträge für jedes mögliche Zeichen sowie Einträge für Lücken. Alternativ können statistische Musterfindungsalgorithmen Motive als Vorläufer einer MSA und nicht als Ableitung identifizieren. In vielen Fällen, wenn der Abfragesatz nur eine kleine Anzahl von Sequenzen oder nur stark verwandte Sequenzen enthält, werden Pseudozählungen hinzugefügt, um die in der Bewertungsmatrix widergespiegelte Verteilung zu normalisieren. Insbesondere korrigiert dies Nullwahrscheinlichkeitseinträge in der Matrix auf Werte, die klein, aber ungleich Null sind.

Die Blockanalyse ist eine Methode zum Auffinden von Motiven, die Motive auf Regionen ohne Gap in der Ausrichtung beschränkt. Blöcke können aus einer MSA generiert werden oder sie können aus nicht ausgerichteten Sequenzen unter Verwendung eines vorberechneten Satzes gemeinsamer Motive extrahiert werden, die zuvor aus bekannten Genfamilien generiert wurden. Die Blockbewertung beruht im Allgemeinen eher auf dem Abstand von Zeichen mit hoher Häufigkeit als auf der Berechnung einer expliziten Substitutionsmatrix. Der BLOCKS-Server stellt ein interaktives Verfahren bereit, um solche Motive in nicht ausgerichteten Sequenzen zu lokalisieren.

Der statistische Musterabgleich wurde sowohl unter Verwendung des Erwartungsmaximierungsalgorithmus als auch des Gibbs-Samplers implementiert. Eines der gebräuchlichsten Tools zum Finden von Motiven, bekannt als MEME, verwendet Erwartungsmaximierung und Hidden-Markov-Methoden, um Motive zu generieren, die dann von seinem Begleiter MAST in der kombinierten Suite MEME/MAST als Suchwerkzeuge verwendet werden.