Articles

Paarweise Ausrichtung von Nukleotidsequenzen unter Verwendung maximaler exakter Übereinstimmungen

Oktober 15, 2020 by admin

Ansatz

In unserem vorgeschlagenen Algorithmus besteht der erste Schritt zum Ausrichten von Sequenzen darin, MEMs zwischen Sequenzen durch direkten Vergleich zu extrahieren. Abbildung 3a ist ein Beispiel, das ein Ziel und eine Abfragesequenz vergleicht, wobei CTC und AAA zwei durch den Vergleich identifizierte MEMs sind. Jede Gruppe kontinuierlicher identischer Symbole im Vergleich führt zu einem MEM, auch wenn es nur aus einem einzigen übereinstimmenden Symbol besteht., Um alle MEMs zwischen den Sequenzen zu extrahieren, muss die Abfragesequenz jeweils ein Symbol nach rechts und nach links verschoben werden (siehe Abb. 3b). Nach jeder Schicht muss der Vergleichsschritt wiederholt werden, um neue MEMs zu identifizieren. Zum Beispiel die dritte Zeile in Abb. 3b stellt den Fall dar, in dem die Abfragesequenz nach rechts verschoben und mit der Zielsequenz verglichen wird. Das Ergebnis des Vergleichs identifiziert AAAAGC als neues MEM. Alle anderen MEMs, die durch Verschiebungs-und Vergleichsoperationen extrahiert wurden,sind ebenfalls in Abb. 3b., Drei der MEMs (Mx, My und Mz) werden mit verschiedenen Farben hervorgehoben, um sie später zu erläutern.

Im Affine-Gap-Scoring-Modell wird der Alignment Score AS mit Eq berechnet., 1 wobei Nm die Anzahl der Übereinstimmungen ist, die jeweils eine Übereinstimmungsbewertung von Rm erhalten,Nx die Anzahl der Nichtübereinstimmungen ist, die jeweils eine Nichtübereinstimmungsstrafe von Px erhalten, Nein ist die Anzahl der Spaltöffnungen, die jeweils eine Lücke erhalten offene Strafe von Po und Ng ist die Gesamtlänge aller Lücken, Jede Lücke erhält eine Lückenverlängerungsstrafe von Pg. Für jede Gruppe kontinuierlicher Lücken würde sich eine Lücke öffnen. Wenn beispielsweise zwei Lücken in der Ausrichtung vorhanden sind, wobei die Länge der ersten Lücke drei und die Länge der zweiten Lücke vier beträgt, gibt es zwei Spaltöffnungen (No=2) und die Gesamtlänge der Lücke beträgt sieben (Ng=3+4=7).,

$$ {}AS = (N_{m} \times R_{m}) – ((N_{x} \times P_{x}) + (N_{o} \times P_{o}) + (N_{g} \times P_{g})) $$

(1)

Angesichts der Liste aller MEMs, die Ausrichtung kann berechnet werden mit der teilweisen Ausrichtung. Betrachten Sie beispielsweise MEMs Mx, My und Mz in Abb. 3b.Die Teilausrichtungen, die durch verschiedene Kombinationen von Mx, My und Mz zusammen mit der Anzahl der Übereinstimmungen, Nichtübereinstimmungen und Lücken sowie den resultierenden Ausrichtungswerten vorgenommen werden, sind in Abb. 4. Die Ausrichtung, die nur Mx und Mz enthält, führt zur höchsten Ausrichtungsbewertung., Beachten Sie, dass sich My und Mz überlappen und wenn beide in derselben Ausrichtung betrachtet werden, wird die Überlappung von Mz ausgeschlossen. Unter Berücksichtigung aller MEMs in Abb. dies führt zu vielen weiteren Kombinationen, bei denen keine von ihnen eine höhere Punktzahl erreicht.

Abb. 4

Alle möglichen Kombinationen von MEMs in der Ausrichtung

Die Prüfung aller möglichen Kombinationen von MEMs wäre erschöpfend., Im Abschnitt „Ausrichtungsalgorithmus“ beschreiben wir einen neuartigen dynamischen Programmieralgorithmus DP-MEM, der effizient die beste Kombination findet, ohne alle Fälle zu berücksichtigen. DP-MEM muss wissen, welche Teile der Sequenzen übereinstimmen, nicht jedoch die tatsächlichen Symbole in den Sequenzen. Die Eingabe in DP-MEM ist die Positionierung von MEMs im Ziel und in den Abfragesequenzen, die während des im Abschnitt „MEM-Extraktion“ beschriebenen MEM-Extraktionsprozesses erhalten werden., Wie MEMs mit ihren Positionen dargestellt werden und wie die Anzahl der Übereinstimmungen, Nichtübereinstimmungen und Lücken berechnet werden, wenn MEMs in einer Ausrichtung kombiniert werden, wird im Rest dieses Abschnitts erläutert. Abbildung 5 ist ein weiteres Beispiel für die Ausrichtung mit sechs MEMs (M1 bis M6), die die Ausrichtung zwischen Zielsequenz T und Abfragesequenz Q bilden. Jedes MEM Mi wird als Tripel ganzzahliger Zahlen dargestellt: die Startpositionen in T und in Q (STi bzw. SQi) und seine Länge (Li)., Die Endpositionen in T und in Q können später berechnet werden (Φ2E von Algorithmus 2). Tabelle 1 listet die Länge und die Positionierung von M1 bis M6 in T und in f:

Tabelle 1 Start-und Endposition von MEMs in Fig., 5

Tabelle 2 Computing Anzahl der Abweichungen und Lücken zwischen MEMs in Abb. 5

Falls zwischen Mi und Mj sowohl Fehlanpassungen als auch Lücken bestehen, werden alle Lücken als kontinuierlich betrachtet, um die Lücke zu verringern offene Strafe (für eine offene Lücke wird nur eine Lücke angewendet). Somit wird für alle benachbarten MEMs, die Lücken zwischen ihnen haben, nur eine offene Lücke Strafe angewendet., Die Platzierung von Nichtübereinstimmungen und die einzige kontinuierliche Lücke ist nicht wichtig, da dies den Ausrichtungswert nicht beeinflussen würde. Wir gehen davon aus, dass die Mismatch-Strafe konstant ist (dies ist für DNA-Sequenzen üblich).

MEM-Extraktion

Es gibt Methoden, um maximale exakte Übereinstimmungen zwischen langen Sequenzen wie einem ganzen Genom zu extrahieren. Diese Methoden basieren jedoch auf der Vorverarbeitung und Indizierung einer oder beider Sequenzen, was eine zeitaufwändige Operation ist. In DNA Read Aligner wird beispielsweise das Referenzgenom einmal indiziert, und bei jeder Ausrichtung eines neuen Lesevorgangs wird derselbe Index verwendet., Wir suchen nach einem schnellen Algorithmus, um MEMs zwischen relativ kurzen Sequenzen zu identifizieren, die sich für jede Ausrichtung ändern. Eine Brute-Force-Methode für dieses Problem (zusätzliche Datei 1: Abschnitt II) ist langsam und ineffizient(mit der Komplexität von O (n3)). Wir schlagen eine schnelle parallele Methode auf Bitebene vor, um den MEM-Extraktionsprozess zu beschleunigen. Unsere MEM-Extraktionsmethode basiert auf den in Abb. 3b. Der erste Schritt besteht darin, Sequenzen mit Bitvektoren darzustellen, wobei A, C, T und G als 00, 01, 10 bzw. 11 codiert sind (zusätzliche Datei 1: Abschnitt III)., Abbildung 6 veranschaulicht ein Beispielsequenzpaar zusammen mit entsprechenden Bitvektordarstellungen. In einem commodity computer, das maschinenwort ist in der regel 64 bits, die aufnehmen können 32 nukleotid symbole. Da eine Sequenz normalerweise größer als 32 Symbole ist, wird der entsprechende Bitvektor in mehreren Maschinenwörtern gespeichert. Jede Operation auf Bitvektoren von Sequenzen der Größe n Symbole wirkt auf $\lceil \frac {n}{32} \rceil $ Maschinenwörter.

Bei der Bitvektoren-Darstellung von Sequenzen ist das Verschieben einer Sequenz um ein Symbol dasselbe wie das Verschieben des Bitvektors um zwei Bits, und das Vergleichen von Sequenzen kann mit der XOR-Anweisung erfolgen (32 Symbole gleichzeitig). In der XOR-Ausgabe (X) bedeutet 00, dass Symbole übereinstimmen, und eine Folge von 00s zeigt ein MEM., Ein Satz von Verschiebungs-und bitweisen Operationen, wie in Algorithmus 1 gezeigt, berechnet X und anschließend den Kantenbitvektor (E), in dem der Anfang und das Ende jedes MEM mit gesetzten Bits (Bits mit einem Wert von eins) hervorgehoben sind. Abbildung 6 zeigt die X-und E-Bitvektoren mit markierten MEMs. Die Positionierung von MEMs in Sequenzen wird dann aus dem Kantenbitvektor berechnet (Zusätzliche Datei 1: Abschnitt IV).,

Ausrichtungsalgorithmus

Im Abschnitt“ Ansatz “ zeigen wir, dass man durch die Berücksichtigung verschiedener Kombinationen von MEMs und die Berechnung der Ausrichtungsbewertung für die entsprechende Ausrichtung die Kombination von MEMs identifizieren kann, die zur maximalen Ausrichtungsbewertung führt. Die Untersuchung aller möglichen Kombinationen von MEMs ist jedoch eine naive Lösung. Eine systematischere Möglichkeit, die Ausrichtung effizient zu finden, ist die Verwendung der dynamischen Programmierung.

Dynamische Programmierung ist die Methode, um die Lösung eines Problems durch Definieren und Lösen kleinerer Teilprobleme zu erreichen., Lösungen für Teilprobleme werden verwendet, um bei jedem Schritt ein größeres Problem zu lösen. Der Vorgang wird wiederholt, bis alle Teilprobleme gelöst sind. Schließlich wäre die Lösung für eines der Unterprobleme die Lösung für das ursprüngliche Problem. Wenn alle Teilprobleme gelöst sind, identifiziert ein Backtracking-Prozess eine Reihe von Lösungen, die zur endgültigen Lösung beitragen. Bei der dynamischen Programmierung sollte eine Reihenfolge der Eingabedaten vorhanden sein, entlang der die Rekursionsverfahren ablaufen.

Wir sortieren alle MEMs nach der Position ihres Endes in Abfragesequenz (EQ)., MEMs, die an derselben Position enden, sind beliebig geordnet. Das jth-Teilproblem besteht darin, die Ausrichtung von Teilsequenzen von T und Q zu finden, die bei jth MEM Mj enden (T bzw. Wir werden zeigen, dass diese Reihenfolge von MEM ausreicht, um die korrekte Rekursion zu unterstützen.

In der sortierten Liste der MEMs gibt EQi=EQj an, dass einer von Mi oder Mj den anderen MEM in der Abfragesequenz vollständig überlappt. Da in Φ2B des Algorithmus 2 der Überlappungsbereich ausgeschlossen ist, können Mi und Mj nicht in der gleichen Ausrichtung sein., So werden ith-und jth-Teilprobleme unabhängig voneinander gelöst und die Reihenfolge von i und j in der sortierten Liste könnte beliebig sein. Wenn EQk>EQj (k>j in der sortierten Liste), Mk könne nicht Teil der Ausrichtung, endet in Mj. Somit können die jth-Teilprobleme unabhängig von der Lösung des kth-Teilproblems gelöst werden. Beachten Sie, dass es auch möglich ist, MEMs anhand einer ähnlichen Begründung nach ihrer Endposition in der Zielsequenz (ET) zu sortieren.

Unser vorgeschlagener dynamischer Programmieralgorithmus (DP-MEM) wird in Algorithmus 2 ausgearbeitet., Für das Beispiel MEMs extrahiert in Fig. 3b sind die dynamische Programmiertabelle und der im Algorithmus berechnete Zwischenwert in Fig. 7 und 8. Die Eingabe in DP-MEM ist die Liste der MEMs, wobei jedes MEM (Mj) ein Tripel von ganzen Zahlen ist . Die zweite Eingabe n ist die Anzahl der MEMs in der Liste. Die Ausgabe S ist der Ausrichtwert für die Sequenzen. Der Algorithmus druckt die Indizes aller MEMs aus, die die Ausrichtung bilden, wobei die erste und die letzte gedruckte Zahl die Indizes der MEMS ganz rechts bzw. ganz links in der Ausrichtung sind., Alle Schritte von Algorithmus 2 sind wie folgt kommentiert:

Φ1: Scoring-jedes MEM wird für alle übereinstimmenden Symbole., Beachten Sie, dass es in Mj Lj passende Symbole gibt. Sj stellt die höchste Ausrichtungsbewertung für die Ausrichtung dar, die bei Mj endet. Die Initialisierung von Sj in diesem Schritt ähnelt der Berechnung des Partial Alignment Score, wenn nur Mj in der Ausrichtung enthalten ist. W wird für Backtracking verwendet. Der Wert -1 gibt an, dass der aktuelle Sj durch Betrachten von Mj allein in der Ausrichtung erhalten wird.
Φ2: Berechnen von Sj für jedes MEM (Mj)., Um Sj zu berechnen, fügt der Algorithmus für jedes MEM Mi, bei dem Mi vor Mj in der Liste angezeigt wird, Mj zur Ausrichtung hinzu, die bei Mi endet (Erweiterung zuvor gefundener Ausrichtungen), und sucht nach der Erweiterung, die Sj maximiert (Lösung eines größeren Teilproblems unter Verwendung zuvor gelöster Teilprobleme).
Φ2A: Erweiterung überspringen, wenn dies nicht möglich ist. Wenn ETi>ETj dann Mi enthält einen Teil der zielsequenz, die über die Angleichung der Endung an Mj und die Verlängerung ist nicht möglich. Wenn EQi=EQj oder ETi=ETj oder SQi≥SQj oder STi≥STj, überlappt eines der MEMs das andere MEM vollständig., In diesem Fall können Mi und Mj nicht in einer Ausrichtung zusammen sein.
Φ2B: Berechnung der Länge der überlappung zwischen Mi und Mj. Wenn ${MO}_{i}^{j}$ kleiner oder gleich Null ist, besteht keine Überlappung.
Φ2C: Behalten Sie eine Kopie von Mj, bevor Sie Überlappungen ausschließen.
Φ2D: Wenn Überlappung besteht, ohne Überlappung von Mj
Φ2E: Berechnung der Endposition von Mj in T und Q.
Φ2F: Berechnung des Abstands (Anzahl der Symbole) zwischen Mi und Mj in T und Q.
Φ2G: Berechnung der Anzahl von Fehlanpassungen und Lücken zwischen Mi und Mj.,
Φ2H: Berechnung der Strafe für die Diskrepanzen und Lücken zwischen Mi und Mj ($P_{i}^{j}$). Wenn eine Lücke besteht, wird nur eine offene Lücke Strafe abgezogen.
Φ2I: Berechnung der Ausrichtungsbewertung $\left (S_{i}^{j}\right)$ wenn Mj zur Ausrichtungsende bei Mi hinzugefügt wird. Die Punktzahl für alle übereinstimmenden Symbole in Mj (Lj×Rm) wird dem Ausrichtwert für die Ausrichtung hinzugefügt, die bei Mi (Si) endet. Dann wird die Strafe für die Lücken und Fehlanpassungen zwischen Mi und Mj$\left (P_{i}^{j}\right)$ subtrahiert.,
Φ2J: Wenn die Erweiterung von Mj auf die Ausrichtung, die mit Mi endet, zu einer Punktzahl führt $\left (S_{i}^{j}\ right)$ höher als die aktuelle Punktzahl für Mj (Sj) dann wird die neue Punktzahl in Sj gespeichert. Auch W ist auf i eingestellt, um den Mi zu verfolgen, der die Punktzahl für Mj maximiert.
Φ2K: Stellen Sie den Wert von Mj vor dem Ausschluss wieder her, damit Mj in anderen Ausrichtungserweiterungen verwendet werden kann.
Φ3: Suche nach dem MEM mit dem höchsten Sj. Dieses MEM ist das letzte MEM in der Ausrichtung (Me)., Die höchste Punktzahl (Se) zurückgegeben wird, wie S das ist der höchste alignment-score für die gegebenen Sequenzen. Der Index des MEM, der Sj maximiert, wird in e gespeichert, um mit dem Backtracking von Me zu beginnen.
Φ4: In der Ausrichtung ist für mich die unmittelbare vorherige MEM diejenige, die die Ausrichtungsbewertung für mich maximiert. Der Index eines solchen MEM wird in W. Als Ergebnis besucht die Iteration von f←W den Index aller MEMs in der Ausrichtung. Wenn W gleich -1 ist, ist Mf das erste MEM in der Ausrichtung und die Iteration wird gestoppt.,

In unserem Algorithmus bestrafen wir keine Fehlanpassungen und Lücken vor dem ersten MEM und nach dem letzten MEM in der Ausrichtung. Dies führt zu einem lokalen Ausrichtungsalgorithmus. Durch die Berücksichtigung dieser Strafen generiert der Algorithmus eine globale Ausrichtung (Zusätzliche Datei 1: Abschnitt V).

Die zu berechnende Gleichung $P_{i}^{j}$ in Φ2H von Algorithmus 2 geht davon aus, dass im Bereich zwischen Mi und Mj kein übereinstimmendes Symbol zwischen T und Q vorhanden ist (alle Symbole werden als nicht Übereinstimmungen oder Lücken gezählt)., Obwohl diese Annahme nicht für alle Mi gilt, gilt sie immer für die Mi, die zu maximum $S_{i}^{j}$ führt, was den Effekt der Annahme für andere Mi falsch macht. Nehmen Sie als Beweis an, dass sich im Bereich zwischen Mi und Mj ein übereinstimmendes Symbol befindet. Das passende Symbol wäre ein MEM (Mk). Mk ist bereits auf die Ausrichtung erweitert, die bei Mi endet. Somit wird bei der Erweiterung von Mj auf Mk eine höhere Punktzahl erreicht, als bei der Erweiterung von Mj auf Mi.

Verkettung colinear samen wie diskutiert in wurden weit verbreitet in die ausrichtung von großen sequenzen, dh genom-zu-genom ausrichtung., Es wurde auch verwendet, um Kandidatenregionen für eine Lese gegeben eine Reihe von MEMs in BWA zu identifizieren. Verkettungsalgorithmen mit Scoring ähneln dem von uns vorgeschlagenen dynamischen Programmieralgorithmus (DP-MEM). Es gibt jedoch Unterschiede, die DP-MEM für die paarweise Ausrichtung kurzer Sequenzen geeignet machen. DP-MEM berücksichtigt, dass alle MEMs innerhalb einer bestimmten Spaltgröße in der Eingabe bereitgestellt werden und optimiert die Anzahl der Iterationen im Algorithmus. DP-MEM implementiert auch einen heuristischen Ansatz, um den Effekt von kurzen MEMs zu kompensieren, die aus der Eingabeliste entfernt wurden, was zu Lücken zwischen MEMs führt.,

Bei gegebenen Sequenzen der Länge n erfordert der Algorithmus zum Extrahieren von MEMs (bereitgestellt im Abschnitt „MEM−Extraktion“) 2(n−1) Verschiebungs-und 2n-1-Vergleichsoperationen für Bitvektoren (jeder wirkt auf $\lceil \frac {n}{32} \rceil $ Maschinenwörter), die zu einem Algorithmus mit der Komplexität von O(n2) führen, um Kantenbitvektoren für das gegebene Sequenzpaar zu erzeugen. Die Komplexität der Funktion, die die Positionierung von MEMs aus dem Kantenbitvektor berechnet und basierend auf EQ sortiert, muss noch hinzugefügt werden. Wenn m-MEMs extrahiert werden, hat Φ2 des Algorithmus 2 (DP-MEM) die Komplexität von O(m2)., In Anbetracht der Komplexität der MEM-Extraktion und DP-MEM ist MEM-Align viel langsamer als verfügbare Ausrichtungsalgorithmen. Um den Prozess zu beschleunigen, stellen wir einige Optimierungen für MEM-Align vor, die eine schnellere Laufzeit durch Einbußen bei der Genauigkeit erreichen. Andererseits führen wir Methoden ein, um die Genauigkeit bei minimalem Leistungsverlust zu verbessern.

Banded alignment

Banded alignment ist eine bekannte heuristische Methode zur Beschleunigung des Ausrichtungsprozesses. Diese Technik begrenzt das Muster der Lücken in der Ausrichtung (Zusätzliche Datei 1: Abschnitt VI)., Wenn folglich die Ausrichtung zwischen zwei Sequenzen diesem Muster nicht folgt, identifiziert der Algorithmus die Ausrichtung nicht. Bei der traditionellen dynamischen Programmierung wird die Ausrichtung erhalten, nachdem der Wert aller Zellen in der Tabelle berechnet wurde. Bei der gebänderten Ausrichtungsoptimierung werden jedoch nur Zellen auf dem Durchmesser und in der Nähe der Diagonale ausgewertet. gl ist die Breite des Bandes in gebänderter Ausrichtung, wobei Zellen, die weiter als gl zum Durchmesser sind, nicht ausgewertet werden. Dunklere Zellen in Abb. 1 zeigen Sie den Fall, in dem gl=1.,

Im Gegensatz zum herkömmlichen dynamischen Programmieransatz verfügt MEM-Align nicht über eine ähnliche Tabelle zum Anwenden der gebänderten Ausrichtung. Wir haben jedoch festgestellt, dass wir den gleichen Effekt simulieren können, indem wir die Anzahl der Schichtvorgänge im MEM-Extraktionsprozess begrenzen. Wenn wir beispielsweise die Abfragesequenz auf gl nach rechts und nach links verschieben, erreichen wir eine gebänderte Ausrichtung mit dem gl-Band. Banded-Alignment reduziert die Komplexität der MEM-Extraktion von O(n2) auf O(n. (2gl+1)), wobei gl ein kleiner und fester Wert ist. Somit ist die Komplexität der MEM-Extraktion O (n), wenn eine gebänderte Ausrichtung angewendet wird., Mit der genannten gebänderten Ausrichtung ist es auch wahrscheinlich, dass weniger MEMs extrahiert werden, was die nachfolgenden algorithmischen Schritte beschleunigt.

Kurze MEM-Entfernung

Wir haben beobachtet, dass die meisten extrahierten MEMs kurz sind und das Ergebnis zufällig übereinstimmender Symbole sind. Um MEM-Align zu beschleunigen, werden MEMs, die kürzer als sl sind, während des MEM-Extraktionsprozesses herausgefiltert. Dies reduziert die Anzahl der zu extrahierenden und zu verarbeitenden MEMs (was den Algorithmus anschließend beschleunigt). Das Filtern von kurzen MEM erfolgt durch Erweitern von Algorithmus 1 mit einer Reihe von Verschiebungs-und bitweisen Operationen (zusätzliche Datei 1: Abschnitt VII).,

Andererseits gibt es seltene Fälle, in denen kurze MEMs Teil der Ausrichtung sind; zum Beispiel ein übereinstimmendes Symbol, das von Nichtübereinstimmungen umgeben ist. Ohne alle MEMs in der Eingabeliste zu haben, kann DP-MEM nicht dieselbe Ausrichtung finden, wie sie gefunden wird, wenn alle MEMs in der Eingabeliste vorhanden sind. Um verlorene kurze MEMs in der Eingabe auszugleichen, modifizieren wir Φ2H von DP-MEM, um die Möglichkeit kurzer Übereinstimmungen zwischen MEMs zu berücksichtigen (Zusätzliche Datei 1: Abschnitt VIII).

Möglicherweise gibt es schwierigere Fälle, in denen in der Ausrichtung mehrere kurze MEMs zwischen zwei MEMs existieren (siehe Abb. 9)., Die einzige Möglichkeit, die Punktzahl für den Bereich zwischen Mi und Mj in Φ2H korrekt zu identifizieren, besteht darin, eine globale Ausrichtung auf diese Region anzuwenden. Φ2H ist jedoch eine häufige Operation und sollte schnell bleiben. Folglich haben wir beschlossen, das Problem teilweise zu überwinden, indem wir mögliche Fälle einschränken (eine heuristische Methode).

Abb., 9

Ein Beispiel, das mehrere kurze MEM in dem kleinen Bereich zwischen Mi und Mj in einer Ausrichtung zeigt

Wenn es Lücken im Bereich zwischen Mi und Mj gibt, nehmen wir an, dass es nur eine kontinuierliche Lücke entweder zum linken Ende rechtes Ende des Bereichs. Dann sind nur noch zwei Ausrichtungen für den Bereich möglich., Die Anzahl der übereinstimmenden Symbole wird für beide Fälle sequentiell gezählt und die Anzahl der Übereinstimmungen zwischen Mi und Mj, die zu maximalen Übereinstimmungen führt, wird als Anzahl der Übereinstimmungen zwischen Mi und Mj genommen (Zusätzliche Datei 1: Abschnitt IX). Der sequentielle Vergleich ist eine teure Operation und wir entwickeln eine Methode, um den sequentiellen Vergleich nach Möglichkeit zu vermeiden (Zusätzliche Datei 1: Abschnitt X).

Jeder andere Fall, der nicht der obigen Annahme entspricht, führt zu einer Ausrichtung mit einer niedrigeren Punktzahl., In Anbetracht der geringen Anzahl von Lücken und Fehlanpassungen ist die Möglichkeit, mehrere Lücken und Fehlanpassungen in einem kleinen Bereich zu haben, jedoch gering.

Effiziente Ausrichtungserweiterung

In Φ2 von DP-MEM erweitert Mj alle Ausrichtungen, die in {M1…Mj−1} enden (wenn möglich). Für jeden Mj gibt es jedoch eine kleinere Teilmenge Ωj⊆{M1…Mj-1}, so dass durch Ausdehnung von Mj auf alle Ausrichtungen, die mit einem Mi∈Ωj enden, die Ausrichtung gefunden wird, die mit Mj endet (Eq. 2). Mit anderen Worten, es müssten weniger $S_{i}^{j}$ ausgewertet werden. Definition des Satzes Ωj und des Nachweises von Eq. 2 sind in zusätzlicher Datei 1: Abschnitt XI., Die Definition von Ωj wird beeinflusst, wenn die Optimierung der kurzen MEM-Entfernung angewendet wird (Zusätzliche Datei 1: Abschnitt XII).

$$ \max\limits_{M_{i} \in \Omega_{j}}{S_{i}^{j}} = \max\limits_{1 \leq i \leq j-1}{S_{i}^{j}} $$

(2)

Hybrid-Ausrichtung

Um die Genauigkeit des Algorithmus, entschieden wir nutzen eine hybride Methode, die eine Kombination von MEM-Ausrichten und Smith-Waterman-Algorithmus. Wir definieren drei Fälle, in denen MEM-Align ungenau sein kann., Wenn die Ausrichtung eines Sequenzpaares in einen dieser Fälle fällt, verwenden wir den Smith-Waterman-Algorithmus, um Sequenzen auszurichten. Diese Fälle sind:

Wenn sich die Sequenzen wiederholen und die Anzahl der extrahierten MEMs den Schwellenwert TM überschreitet. Wir haben festgestellt, dass MEM-Align beim Ausrichten sich wiederholender Sequenzen wahrscheinlich eine ungenaue Ausrichtung erzeugt. Ein geeigneter TM-Wert verringert die Wahrscheinlichkeit einer ungenauen Ausrichtung mit einer vernachlässigbaren Erhöhung der durchschnittlichen Verarbeitungszeit.,
Wenn der berechnete Ausrichtungswert für die von MEM-Align erzeugte Ausrichtung niedriger als ein Schwellenwert TS ist. Dieser Fall tritt meistens auf, wenn in der Ausrichtung ein Spalt vorhanden ist, der aufgrund der gebänderten Ausrichtung nicht identifiziert werden kann.
Wenn kein MEM länger als sl existiert, um extrahiert zu werden (ein seltener Fall)., Wenn sl auf einen hohen Wert gesetzt ist und die Ähnlichkeit zwischen Sequenzen gering ist,

Obwohl das Senden von Sequenzpaaren an einen externen Algorithmus zu einer zusätzlichen Berechnung führt, bleibt die Anzahl der Sequenzen, die an den externen Algorithmus gesendet werden, klein, wenn geeignete Werte für TM und TS ausgewählt werden.

Überspringen entfernter MEMs

Wenn der Abstand zwischen Mi und Mj groß ist, ist es nicht wahrscheinlich, dass Mi und Mj als benachbarte MEMs in der Ausrichtung vorhanden sind., Daher überspringt der Algorithmus die Erweiterung, wenn der Abstand zwischen Mi und Mj länger als ein Schwellenwert TD ist (weitere Verringerung der Anzahl der auszuwertenden $S_{i}^{j}$). Diese Optimierung verbessert leicht die Leistung mit einem vernachlässigbaren Nebeneffekt auf die Genauigkeit.

Be Able