Lückenstrafe - Gap penalty

Eine Lückenstrafe ist eine Methode zum Bewerten von Ausrichtungen von zwei oder mehr Sequenzen. Beim Alignieren von Sequenzen kann das Einführen von Lücken in die Sequenzen es einem Alignment-Algorithmus ermöglichen, mehr Termen zuzuordnen, als dies bei einem lückenlosen Alignment der Fall ist. Es ist jedoch wichtig, Lücken in einem Alignment zu minimieren, um ein nützliches Alignment zu erstellen. Zu viele Lücken können dazu führen, dass eine Ausrichtung bedeutungslos wird. Lückenstrafen werden verwendet, um Ausrichtungsbewertungen basierend auf der Anzahl und Länge der Lücken anzupassen. Die fünf Haupttypen von Lückenstrafen sind konstant, linear, affin, konvex und profilbasiert.

Anwendungen

• Genetische Sequenzausrichtung – In der Bioinformatik werden Lücken verwendet, um genetische Mutationen zu berücksichtigen, die durch Insertionen oder Deletionen in der Sequenz auftreten, manchmal auch als Indels bezeichnet . Insertionen oder Deletionen können aufgrund von Einzelmutationen , unausgeglichenem Crossover in der Meiose , Fehlpaarungen von verrutschten Strängen und chromosomaler Translokation auftreten . Die Vorstellung einer Lücke in einem Alignment ist in vielen biologischen Anwendungen wichtig, da die Insertionen oder Deletionen eine ganze Untersequenz umfassen und oft von einem einzigen Mutationsereignis ausgehen. Darüber hinaus können einzelne Mutationsereignisse Lücken unterschiedlicher Größe erzeugen. Daher müssen beim Scoring die Lücken als Ganzes bewertet werden, wenn zwei DNA-Sequenzen ausgerichtet werden. Die Betrachtung mehrerer Lücken in einer Sequenz als eine größere einzelne Lücke verringert die Zuordnung hoher Kosten zu den Mutationen. Zum Beispiel können zwei Proteinsequenzen relativ ähnlich sein, sich jedoch in bestimmten Intervallen unterscheiden, da ein Protein im Vergleich zum anderen eine andere Untereinheit aufweisen kann. Die Darstellung dieser unterschiedlichen Teilsequenzen als Lücken ermöglicht es uns, diese Fälle als „gute Übereinstimmungen“ zu behandeln, obwohl es lange aufeinanderfolgende Läufe mit indel-Operationen in der Sequenz gibt. Daher vermeidet die Verwendung eines guten Gap-Penalty-Modells niedrige Punktzahlen in Ausrichtungen und verbessert die Chancen, eine echte Ausrichtung zu finden. In genetischen Sequenz-Alignments werden Lücken als Striche (-) auf einem Protein/DNA-Sequenz-Alignment dargestellt.
• Unix- Diff- Funktion - berechnet den minimalen Unterschied zwischen zwei Dateien ähnlich wie bei der Plagiatserkennung.
• Rechtschreibprüfung - Lückenstrafen können dabei helfen, richtig geschriebene Wörter mit dem kürzesten Bearbeitungsabstand zu einem falsch geschriebenen Wort zu finden. Lücken können auf einen fehlenden Buchstaben im falsch geschriebenen Wort hinweisen.
• Plagiaterkennung – Lückenstrafen ermöglichen es Algorithmen zu erkennen, wo Abschnitte eines Dokuments plagiiert sind, indem Lücken in Originalabschnitte eingefügt und identische Abschnitte abgeglichen werden. Die Lückenstrafe für ein bestimmtes Dokument quantifiziert, wie viel von einem bestimmten Dokument wahrscheinlich Original oder Plagiat ist.

Bioinformatik-Anwendungen

Globale Ausrichtung

Ein globales Alignment führt ein Ende-zu-Ende-Alignment der Abfragesequenz mit der Referenzsequenz durch. Idealerweise ist diese Ausrichtungstechnik am besten für eng verwandte Sequenzen ähnlicher Länge geeignet. Der Needleman-Wunsch-Algorithmus ist eine dynamische Programmiertechnik , die verwendet wird, um eine globale Ausrichtung durchzuführen. Im Wesentlichen unterteilt der Algorithmus das Problem in eine Menge von Teilproblemen und verwendet dann die Ergebnisse der Teilprobleme, um eine Lösung für die ursprüngliche Abfrage zu rekonstruieren.

Halbglobale Ausrichtung

Die Verwendung von semi-globalem Alignment existiert, um eine bestimmte Übereinstimmung innerhalb einer großen Sequenz zu finden. Ein Beispiel umfasst das Suchen von Promotoren innerhalb einer DNA-Sequenz. Im Gegensatz zum globalen Alignment kompromittiert es keine Endlücken in einer oder beiden Sequenzen. Wenn die Endlücken in einer Sequenz 1 bestraft werden, aber nicht in Sequenz 2, wird ein Alignment erzeugt, das Sequenz 2 innerhalb von Sequenz 1 enthält.

Lokale Ausrichtung

Beispiel für die Ausrichtung der Proteinsequenz

Ein lokales Sequenz-Alignment stimmt mit einem zusammenhängenden Unterabschnitt einer Sequenz mit einem zusammenhängenden Unterabschnitt einer anderen überein. Der Smith-Waterman-Algorithmus ist motiviert, indem er Punkte für Übereinstimmungen und Nichtübereinstimmungen angibt. Übereinstimmungen erhöhen die Gesamtpunktzahl einer Ausrichtung, während Nichtübereinstimmungen die Punktzahl verringern. Eine gute Ausrichtung hat dann eine positive Bewertung und eine schlechte Ausrichtung eine negative Bewertung. Der lokale Algorithmus findet ein Alignment mit der höchsten Punktzahl, indem es nur Alignments mit positiver Punktzahl berücksichtigt und das beste aus diesen auswählt. Der Algorithmus ist ein dynamischer Programmieralgorithmus . Beim Vergleich von Proteinen verwendet man eine Ähnlichkeitsmatrix, die jedem möglichen Rest eine Punktzahl zuordnet. Die Bewertung sollte für ähnliche Reste positiv und für unähnliche Restepaare negativ sein. Lücken werden normalerweise unter Verwendung einer linearen Lückenfunktion bestraft, die eine anfängliche Bestrafung für eine Lückenöffnung und eine zusätzliche Bestrafung für Lückenerweiterungen zuweist, wodurch die Lückenlänge erhöht wird.

Bewertungsmatrix

Blosum-62 Matrix

Substitutionsmatrizen wie BLOSUM werden zum Sequenz-Alignment von Proteinen verwendet. Eine Substitutionsmatrix weist einen Score zum Ausrichten jedes möglichen Paars von Resten zu. Im Allgemeinen sind verschiedene Substitutionsmatrizen darauf zugeschnitten, Ähnlichkeiten zwischen Sequenzen zu erkennen, die unterschiedlich stark divergieren. Eine einzelne Matrix kann über einen relativ breiten Bereich evolutionärer Veränderungen hinweg einigermaßen effizient sein. Die BLOSUM-62-Matrix ist eine der besten Substitutionsmatrizen zum Nachweis schwacher Proteinähnlichkeiten. BLOSUM-Matrizen mit hohen Zahlen sind für den Vergleich eng verwandter Sequenzen bestimmt, während Matrizen mit niedrigen Zahlen für den Vergleich entfernter verwandter Sequenzen konzipiert sind. BLOSUM-80 wird beispielsweise für Ausrichtungen verwendet, die in der Reihenfolge ähnlicher sind, und BLOSUM-45 wird für Ausrichtungen verwendet, die voneinander abweichen. Bei besonders langen und schwachen Ausrichtungen kann die BLOSUM-45-Matrix die besten Ergebnisse liefern. Kurze Alignments lassen sich leichter mit einer Matrix mit einer höheren "relativen Entropie" als der von BLOSUM-62 erkennen. Die BLOSUM-Reihe enthält keine Matrizen mit relativen Entropien, die für kürzeste Abfragen geeignet sind.

Indels

Während der DNA-Replikation neigt die Replikationsmaschinerie dazu, beim Duplizieren der DNA zwei Arten von Fehlern zu machen. Diese beiden Replikationsfehler sind Insertionen und Deletionen einzelner DNA-Basen aus dem DNA-Strang (Indels). Indels können schwerwiegende biologische Folgen haben, indem sie Mutationen im DNA-Strang verursachen, die zur Inaktivierung oder Überaktivierung des Zielproteins führen können. Wenn beispielsweise ein Indel mit einem oder zwei Nukleotiden in einer kodierenden Sequenz auftritt, wird das Ergebnis eine Verschiebung im Leseraster oder eine Leserastermutation sein , die das Protein inaktiv machen kann. Die biologischen Folgen von Indels sind oft schädlich und werden häufig mit menschlichen Pathologien wie Krebs in Verbindung gebracht . Allerdings sind nicht alle Indels Frameshift-Mutationen. Treten Indels in Trinukleotiden auf, ist das Ergebnis eine Verlängerung der Proteinsequenz, die auch Auswirkungen auf die Proteinfunktion haben kann.

Typen

Diese Grafik zeigt den Unterschied zwischen den Arten von Lückenstrafen. Die genauen Zahlen ändern sich für verschiedene Anwendungen, aber dies zeigt die relative Form jeder Funktion.

Konstante

Dies ist die einfachste Art der Lückenstrafe: Jede Lücke wird unabhängig von ihrer Länge mit einer festen negativen Punktzahl bewertet. Dies ermutigt den Algorithmus, weniger und größere Lücken zu machen, die größere zusammenhängende Abschnitte hinterlassen.

ATTGACCTGA
||   |||||
AT---CCTGA

Ausrichtung zweier kurzer DNA-Sequenzen, wobei '-' eine Lücke von einem Basenpaar darstellt. Wenn jedes Spiel 1 Punkt wert war und die gesamte Lücke -1, ergibt sich die Gesamtpunktzahl: 7 − 1 = 6.

Linear

Verglichen mit der konstanten Lückenstrafe berücksichtigt die lineare Lückenstrafe die Länge (L) jeder Einfügung/Löschung in die Lücke. Wenn daher die Strafe für jedes eingefügte/gelöschte Element B ist und die Länge der Lücke L; die Gesamtlückenstrafe wäre das Produkt der beiden BL. Diese Methode bevorzugt kürzere Lücken, wobei die Gesamtpunktzahl mit jeder weiteren Lücke abnimmt.

ATTGACCTGA
||   |||||
AT---CCTGA

Im Gegensatz zu einer konstanten Lückenstrafe wird die Größe der Lücke berücksichtigt. Bei einem Spiel mit Punktzahl 1 und jeder Lücke -1 beträgt die Punktzahl hier (7 − 3 = 4).

Affin

Die am weitesten verbreitete Lückenstraffunktion ist die affine Lückenstrafe. Die affine Lückenstrafe kombiniert die Komponenten sowohl der konstanten als auch der linearen Lückenstrafe und nimmt die Form an . Dies führt neue Terme ein, A ist als Lückenöffnungsstrafe bekannt, B als Lückenerweiterungsstrafe und L als Länge der Lücke. Lückenöffnung bezieht sich auf die Kosten, die erforderlich sind, um eine Lücke beliebiger Länge zu öffnen, und Lückenverlängerung die Kosten, um die Länge einer bestehenden Lücke um 1 zu verlängern. Oft ist unklar, wie die Werte A und B sein sollen, da sie sich je nach Zweck. Im Allgemeinen, wenn es darum geht, eng verwandte Übereinstimmungen zu finden (zB Entfernung der Vektorsequenz während der Genomsequenzierung), sollte eine höhere Lückenstrafe verwendet werden, um Lückenöffnungen zu reduzieren. Auf der anderen Seite sollte die Lückenstrafe gesenkt werden, wenn Sie daran interessiert sind, ein weiter entferntes Spiel zu finden. Die Beziehung zwischen A und B hat auch einen Einfluss auf die Spaltgröße. Wenn die Größe der Lücke wichtig ist, wird ein kleines A und ein großes B (kostspieliger, eine Lücke zu erweitern) verwendet und umgekehrt. Nur das Verhältnis A/B ist wichtig, da die Multiplikation beider mit derselben positiven Konstanten k alle Strafen um k erhöht: kA+kBL = k(A+BL), was die relative Strafe zwischen verschiedenen Ausrichtungen nicht ändert. ${\displaystyle A+B\cdot L}$

Konvex

Die Verwendung der affinen Lückenstrafe erfordert die Zuweisung fester Strafwerte sowohl für das Öffnen als auch für die Erweiterung einer Lücke. Dies kann für die Verwendung in einem biologischen Kontext zu starr sein.

Die logarithmische Lücke nimmt die Form an und wurde vorgeschlagen, da Studien gezeigt hatten, dass die Verteilung der Indel-Größen einem Potenzgesetz gehorcht. Ein weiteres vorgeschlagenes Problem bei der Verwendung von affinen Lücken ist die Bevorzugung der Ausrichtung von Sequenzen mit kürzeren Lücken. Die logarithmische Lückenstrafe wurde erfunden, um die affine Lücke so zu modifizieren, dass lange Lücken wünschenswert sind. Im Gegensatz dazu wurde jedoch festgestellt, dass die Verwendung von logarithmatischen Modellen im Vergleich zu affinen Modellen zu schlechten Alignments geführt hatte. ${\displaystyle G(L)=A+C\ln L}$

Profilbasiert

Profil-Profil-Alignment-Algorithmen sind leistungsstarke Werkzeuge zur Erkennung von Proteinhomologiebeziehungen mit verbesserter Alignment-Genauigkeit. Profil-Profil-Alignments basieren auf den statistischen Indel-Frequenzprofilen aus mehreren Sequenz-Alignments, die durch PSI-BLAST-Suchen generiert wurden. Anstatt Substitutionsmatrizen zu verwenden, um die Ähnlichkeit von Aminosäurepaaren zu messen, erfordern Profil-Profil-Alignment-Methoden eine profilbasierte Bewertungsfunktion, um die Ähnlichkeit von Profilvektorpaaren zu messen. Profil-Profil-Ausrichtungen verwenden Lückenstraffunktionen. Die Lückeninformationen werden normalerweise in Form von Indel-Frequenzprofilen verwendet, die für die auszurichtenden Sequenzen spezifischer sind. ClustalW und MAFFT haben diese Art der Gap-Penalty-Bestimmung für ihre multiplen Sequenz-Alignments übernommen. Die Ausrichtungsgenauigkeiten können mit diesem Modell verbessert werden, insbesondere für Proteine ​​mit niedriger Sequenzidentität. Einige Profil-Profil-Ausrichtungsalgorithmen führen auch die Sekundärstrukturinformationen als einen Begriff in ihren Bewertungsfunktionen aus, was die Ausrichtungsgenauigkeit verbessert.

Zeitkomplexität vergleichen

Die Verwendung von Alignment in der Computerbiologie beinhaltet oft Sequenzen unterschiedlicher Länge. Es ist wichtig, ein Modell auszuwählen, das bei einer bekannten Eingabegröße effizient ausgeführt werden kann. Die Zeit, die für die Ausführung des Algorithmus benötigt wird, wird als Zeitkomplexität bezeichnet.

Herausforderungen

Es gibt einige Herausforderungen, wenn es darum geht, mit Lücken zu arbeiten. Bei der Arbeit mit gängigen Algorithmen scheint es wenig theoretische Grundlage für die Form der Gap-Penality-Funktionen zu geben. Folglich muss für jede Ausrichtungssituation die Lückenplatzierung empirisch bestimmt werden. Auch werden paarweise Alignment-Gap-Strafen, wie die affine Gap-Strafe, oft unabhängig von den Aminosäuretypen im inserierten oder deletierten Fragment oder an den gebrochenen Enden implementiert, trotz des Beweises, dass spezifische Resttypen in Gap-Regionen bevorzugt werden. Schließlich impliziert das Alignment von Sequenzen das Alignment der entsprechenden Strukturen, aber die Beziehungen zwischen strukturellen Merkmalen von Lücken in Proteinen und ihren entsprechenden Sequenzen sind nur unvollkommen bekannt. Aus diesem Grund ist es schwierig, strukturelle Informationen in Gap-Strafen zu integrieren. Einige Algorithmen verwenden vorhergesagte oder tatsächliche Strukturinformationen, um die Platzierung von Lücken zu beeinflussen. Jedoch hat nur eine Minderheit von Sequenzen bekannte Strukturen, und die meisten Alignment-Probleme beinhalten Sequenzen mit unbekannter Sekundär- und Tertiärstruktur.

Verweise

Weiterlesen

• Taylor WR, Munro RE (1997). "Mehrfachsequenz-Threading: Bedingte Lückenplatzierung" . Falte Des . 2 (4): S33-9. doi : 10.1016/S1359-0278(97)00061-8 . PMID  9269566 .
• Taylor W. R. (1996). „Eine nicht-lokale Lückenstrafe für die Profilausrichtung“. Bull Math Biol . 58 (1): 1–18. doi : 10.1007/BF02458279 . PMID  8819751 . S2CID  189884646 .
• Vingron M., Waterman MS (1994). „Sequenzabgleich und Sanktionswahl. Überprüfung von Konzepten, Fallstudien und Implikationen“. J. Mol. Biol . 235 (1): 1–12. doi : 10.1016/S0022-2836(05)80006-3 . PMID  8289235 .
• Panjukow VV (1993). „Finde stetige Ausrichtungen: Ähnlichkeit und Distanz“. Comput Appl Biosci . 9 (3): 285–90. doi : 10.1093/Bioinformatik/9.3.285 . PMID  8324629 .
• Alexandrow NN (1992). „Lokale Mehrfachausrichtung durch Konsensmatrix“. Comput Appl Biosci . 8 (4): 339–45. doi : 10.1093/Bioinformatik/8.4.339 . PMID  1498689 .
• Hein J. (1989). „Eine neue Methode , die gleichzeitig ausrichtet und rekonstruieren Vorfahren Sequenzen für eine beliebige Anzahl von homologen Sequenzen, wenn der phylogeny gegeben“ . Mol Biol Evol . 6 (6): 649–68. doi : 10.1093/oxfordjournals.molbev.a040577 . PMID  2488477 .
• Henneke CM (1989). „Ein multipler Sequenz-Alignment-Algorithmus für homologe Proteine ​​unter Verwendung von Sekundärstrukturinformationen und optional Keying-Alignments an funktionell wichtigen Stellen“. Comput Appl Biosci . 5 (2): 141–50. doi : 10.1093/Bioinformatik/5.2.141 . PMID  2751764 .
• Reich JG, Drabsch H, Daumler A (1984). "Über die statistische Bewertung von Ähnlichkeiten in DNA-Sequenzen" . Nukleinsäuren Res . 12 (13): 5529–43. doi : 10.1093/nar/12.13.5529 . PMC  318937 . PMID  6462914 .