Articles

Pairwise alignment of nucleotide sequences using maximal exact matches (Polski)

by admin

Approach

w naszym proponowanym algorytmie, pierwszym krokiem w kierunku wyrównania sekwencji jest wyodrębnienie MEMs pomiędzy sekwencjami poprzez bezpośrednie porównanie ich. Rysunek 3a jest przykładem, który porównuje cel i sekwencję zapytań, gdzie CTC i AAA są dwoma memami zidentyfikowanymi przez porównanie. Każda grupa ciągłych identycznych symboli w porównaniu daje MEM, nawet jeśli składa się tylko z jednego pasującego symbolu., Aby wyodrębnić wszystkie memy pomiędzy sekwencjami, Sekwencja zapytań musi być przesunięta w prawo i w lewo o jeden symbol na raz (patrz Rys. 3b). Po każdej zmianie krok porównania należy powtórzyć, aby zidentyfikować nowe MEMs. Na przykład, trzecia linia na Rys. 3b reprezentuje przypadek, w którym sekwencja zapytań jest przesunięta w prawo o jeden symbol i jest porównywana z sekwencją docelową. Wynik porównania określa AAAAGC jako nowy MEM. Wszystkie pozostałe MEMs wyodrębnione przez operacje shift i compare są również podświetlone na Rys. 3b., Trzy MEMs (Mx, My i Mz) są podświetlone różnymi kolorami, które zostaną użyte do późniejszego wyjaśnienia.

rys. 3

ekstrakcja MEM za pomocą operacji shift i compare. Identyfikacja MEMs poprzez bezpośrednie porównanie sekwencji. b zapytanie jest przesuwane w lewo, aż ostatni symbol w sekwencji zapytań zostanie wyrównany do pierwszego symbolu w sekwencji docelowej. Następnie Sekwencja zapytań jest przesuwana w prawo, aż pierwszy symbol w sekwencji zapytań zostanie wyrównany do ostatniego symbolu docelowej sekwencji., Po każdym przesunięciu nakładająca się część sekwencji zapytania i sekwencji docelowych jest porównywana w celu identyfikacji nowych memów. Trzy MEMs (Mx, My i MZ) są podświetlone różnymi kolorami, które można wykorzystać do późniejszego wyjaśnienia

w modelu punktacji afinicznej wynik wyrównania obliczany jest za pomocą korektora., 1 Gdzie Nm to liczba meczów, z których każdy otrzymuje wynik meczu Rm,Nx to liczba niedopasowań, z których każdy otrzymuje karę niedopasowania px, No to liczba otworów lukowych, z których każdy otrzymuje karę otwarcia luki po, a Ng to całkowita długość wszystkich luk, z których każda Luka otrzymuje karę rozszerzenia luki PG. Dla każdej grupy luki ciągłej istnieje otwór luki. Na przykład, jeśli w wyrównaniu są dwie szczeliny, gdzie długość pierwszej szczeliny wynosi trzy, a długość drugiej szczeliny wynosi cztery, to istnieją dwa otwory szczeliny (No=2), a całkowita długość szczeliny wynosi siedem (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)

wyrównanie można obliczyć za pomocą częściowych wyrównań. Na przykład rozważmy MEMs Mx, My I Mz na Rys. 3b. częściowe wyrównania wykonane przez wzięcie różnych kombinacji Mx, My i Mz wraz z liczbą dopasowań, niedopasowań i luk, a także wynik wyrównania są pokazane na Rys. 4. Wyrównanie, które obejmuje tylko Mx i Mz, daje najwyższy wynik wyrównania., Zauważ, że My i Mz nakładają się na siebie i gdy oba są brane pod uwagę w tym samym wyrównaniu, nakładanie się jest wykluczone z MZ. Biorąc pod uwagę wszystkie MEMs na Rys. 3b daje o wiele więcej kombinacji, w których żadna z nich nie osiąga wyższego wyniku.

rys. 4

wszystkie możliwe kombinacje memów w wyrównaniu

analiza wszystkich możliwych kombinacji memów byłaby wyczerpująca., W dziale „Alignment algorithm” opisujemy nowatorski algorytm programowania dynamicznego DP-MEM, który skutecznie wyszukuje najlepszą kombinację bez uwzględniania wszystkich przypadków. DP-MEM musi wiedzieć, które części sekwencji pasują, ale nie rzeczywiste symbole w sekwencjach. Wejście do DP-MEM jest pozycjonowanie MEMs w celu i w sekwencjach zapytań, które są uzyskiwane podczas procesu ekstrakcji MEM opisanego w sekcji „ekstrakcja MEM”., W pozostałej części tej sekcji wyjaśniono, w jaki sposób MEMs są reprezentowane wraz z ich pozycjami oraz jak obliczana jest liczba dopasowań, niedopasowań i luk, gdy MEMs są łączone w wyrównanie. Rysunek 5 to kolejny przykład wyrównania z sześcioma memami (M1 do M6), które tworzą wyrównanie między sekwencją docelową T i sekwencją zapytań Q. dla uproszczenia w tym przykładzie nie ma nakładania się między memami. Każda MEM Mi jest reprezentowana jako potrójna liczba całkowita: pozycje początkowe w T i w Q (odpowiednio STi i SQi) oraz jej długość (Li)., Pozycje końcowe w T i Q można obliczyć później (Φ2E algorytmu 2). Tabela 1 przedstawia długość i położenie M1 do M6 w T i w Q.

rys. 5
tabela 1 pozycja początkowa i końcowa MEMS na rys., 5
Table 2 Computing number of mismatches and luk between MEMs in Fig. 5

w przypadku rozbieżności i luk między Mi i Mj, wszystkie luki są uważane za ciągłe w celu zmniejszenia kary otwartej Luki (tylko jedna kara Otwarta luki jest stosowana dla ciągłej luki). Tak więc dla wszystkich sąsiednich memów, które mają przerwy między nimi, stosuje się tylko jedną karę otwartą., Rozmieszczenie niedopasowań i jedynej ciągłej luki nie jest ważne, ponieważ nie wpłynie to na wynik wyrównania. Zakładamy, że kara niedopasowania jest stała (jest to zwykle dla sekwencji DNA).

ekstrakcja MEM

istnieją metody wyodrębniania maksymalnie dokładnych dopasowań między długimi sekwencjami, takimi jak cały genom. Jednak metody te opierają się na wstępnym przetwarzaniu i indeksowaniu jednej lub obu sekwencji, co jest czasochłonną operacją. Na przykład w DNA read aligner, Genom odniesienia jest indeksowany raz, a ten sam indeks jest używany za każdym razem, gdy nowy odczyt jest wyrównywany., Szukamy szybkiego algorytmu do identyfikacji memów pomiędzy stosunkowo krótkimi sekwencjami, które zmieniają się dla każdego wyrównania. Metoda brute force dla tego problemu (dodatkowy plik 1: Sekcja II) jest powolna i nieefektywna(ze złożonością O (n3)). Proponujemy szybką metodę równoległą na poziomie bitów, aby przyspieszyć proces ekstrakcji MEM. Nasza metoda ekstrakcji MEM opiera się na przesunięciu i porównaniu operacji pokazanych na Rys. 3b. pierwszym krokiem jest przedstawienie sekwencji z wektorami bitowymi, gdzie A, C, T i G są kodowane odpowiednio jako 00, 01, 10 i 11 (dodatkowy plik 1: Sekcja III)., Rysunek 6 ilustruje przykładową parę sekwencji wraz z odpowiadającymi jej reprezentacjami wektorowymi. W komputerze towarowym słowo maszynowe ma zwykle 64 bity, które mogą pomieścić 32 symbole nukleotydów. Ponieważ ciąg jest zwykle większy niż 32 symbole, odpowiedni bit-wektor jest przechowywany w wielu słowach maszynowych. Każda operacja na bitowych wektorach sekwencji o symbolach wielkości n działa na słowach maszynowych \(\lceil \frac {n}{32} \rceil\).

rys., 6

Reprezentacja sekwencji z wektorami bitowymi. Wyjście XOR (X) z podświetlonymi memami. Krawędzie bit-wektor (e) identyfikuje początek i koniec każdego MEMs

z reprezentacją bit-wektorów sekwencji, przesunięcie sekwencji o jeden symbol jest takie samo jak przesunięcie bit-wektora o dwa bity, a porównywanie sekwencji można wykonać za pomocą instrukcji XOR (32 symbole na raz). W wyjściu XOR (X) 00 oznacza, że symbole są dopasowane, a Sekwencja 00 pokazuje MEM., Zbiór operacji przesuniętych i bitowych, jak pokazano w algorytmie 1, oblicza X, a następnie wektor bitowy krawędzi (E), w którym początek i koniec każdego MEM są podświetlone setami bitów (bitów o wartości jednego). Rysunek 6 przedstawia wektory bitów X i E z podświetlonymi memami. Pozycjonowanie MEMs w sekwencjach jest następnie obliczane z wektora bitowego krawędzi (dodatkowy plik 1: Sekcja IV).,

algorytm wyrównywania

w sekcji „podejście” pokazujemy, że biorąc pod uwagę różne kombinacje MEMs i obliczając wynik wyrównania dla odpowiedniego wyrównania, można zidentyfikować kombinację MEMs, która daje maksymalny wynik wyrównania. Jednak badanie wszystkich możliwych kombinacji MEMs jest naiwnym rozwiązaniem. Bardziej systematycznym sposobem skutecznego znalezienia osiowania jest wykorzystanie programowania dynamicznego.

programowanie dynamiczne to metoda podejścia do rozwiązania problemu poprzez definiowanie i rozwiązywanie mniejszych podproblemów., Rozwiązania podproblemów są używane do rozwiązania większego problemu na każdym etapie. Proces jest powtarzany, dopóki wszystkie podproblemy nie zostaną rozwiązane. Ostatecznie rozwiązaniem jednego z podproblemów byłoby rozwiązanie początkowego problemu. Gdy wszystkie podproblemy są rozwiązane proces backtracking identyfikuje szereg rozwiązań, które przyczyniają się do ostatecznego rozwiązania. W programowaniu dynamicznym powinna istnieć kolejność danych wejściowych, po której przebiega procedura rekurencji.

sortujemy wszystkie memy według pozycji ich końca w sekwencji zapytań (EQ)., MEMs kończące się w tej samej pozycji są uporządkowane w dowolny sposób. Podproblem jth jest znalezienie wyrównania kolejnych t I Q, które kończą się na jth MEM Mj (odpowiednio T I Q). Pokażemy, że taka kolejność MEM jest wystarczająca do obsługi prawidłowej rekurencji.

na posortowanej liście memów, EQi=EQj wskazuje, że jeden z Mi lub Mj w pełni pokrywa się z drugim MEM w sekwencji zapytań. Ponieważ w Φ2B algorytmu 2 Obszar nakładania się jest wykluczony, Mi i Mj nie mogą być w tym samym wyrównaniu., Tak więc podproblemy ith i jth są rozwiązywane niezależnie od siebie, a kolejność i I j na posortowanej liście może być dowolna. Jeśli EQk>EQj (k> j na posortowanej liście), Mk nie może być częścią wyrównania kończącego się na Mj. W ten sposób podproblemy jth mogą być rozwiązywane niezależnie od rozwiązania podproblemu kth. Zauważ, że możliwe jest również sortowanie memów na podstawie ich pozycji końcowej w sekwencji docelowej (ET) przy użyciu podobnego uzasadnienia.

Nasz proponowany algorytm programowania dynamicznego (DP-MEM) jest opracowany w algorytmie 2., Dla przykładowego MEMs wyodrębnionego na Rys. 3b, dynamiczna tabela programowania i wartość pośrednia obliczona w algorytmie są pokazane na rysunkach. Odpowiednio 7 i 8. Wejście do DP-MEM jest listą MEMs, gdzie każdy MEM (Mj) jest trójką liczb całkowitych . Drugie wejście n to liczba memów na liście. Wyjście S jest wynikiem wyrównania dla sekwencji. Algorytm drukuje indeksy wszystkich memów tworzących wyrównanie, gdzie pierwsza i ostatnia drukowana Liczba są indeksami, odpowiednio, najbardziej prawych i najbardziej lewych memów w wyrównaniu., Wszystkie kroki algorytmu 2 są komentowane w następujący sposób:

rys. 7

dynamiczna tabela programowania używana w algorytmie 2 do przetwarzania wyodrębnionych memów na Rys. 3b. komórki i I j reprezentują wartość \(s_{I}^{j}\). Puste komórki nie są oceniane W Φ2. Ocena komórek ze znakiem krzyżowym jest pomijana w Φ2A. wartość początkowa Sj jest obliczana w Φ1. Wartość końcowa Sj i jej źródło (co maksymalizuje Sj) są podświetlane dla każdego wiersza. Najwyższy Sj (S13) to wynik wyrównania., M13 jest ostatnim MEM w wyrównaniu, a mem przed tym to MW=M3. Ponieważ W = -1, M3 jest pierwszym MEM w wyrównaniu. System punktacji dla tego wyrównania to Rm=2, Px = 3, Po = 4 i Pe=1

rys. 8

wartości pośrednie do obliczenia \(s_{I}^{j}\) na Rys. 7. Zauważ, że Sij na tym rysunku odnosi się do \(s_ {i}^{j}\)

  • Φ1: punktuje każdy MEM dla wszystkich jego pasujących symboli., Zauważ, że w Mj są symbole pasujące do Lj. Sj oznacza najwyższy wynik wyrównania dla wyrównania kończącego się na Mj. Inicjowanie Sj w tym kroku jest podobne do obliczania wyniku częściowego wyrównania, gdy tylko Mj jest uwzględniony w wyrównaniu. W służy do backtrackingu. Wartość -1 wskazuje, że obecny Sj jest uzyskiwany przez uwzględnienie samego Mj w wyrównaniu.

  • Φ2: Obliczanie Sj dla każdego MEM (Mj)., Aby obliczyć Sj, dla każdego MEM Mi, gdzie mi pojawia się przed Mj na liście, algorytm dodaje Mj do wyrównania kończącego się na Mi (rozszerzając wcześniej znalezione wyrównania) i szuka rozszerzenia, które maksymalizuje Sj (rozwiązując większy podproblem używając wcześniej rozwiązanych podproblemów).

  • Φ2A: pomija rozszerzenie, gdy nie jest to możliwe. Jeśli ETi>ETj, to Mi zawiera część sekwencji docelowej, która jest poza wyrównaniem kończącym się na Mj i rozszerzenie nie jest możliwe. Jeśli EQi = EQj lub ETi = ETj lub SQI≥SQJ lub STi≥STj, to jeden z MEMs całkowicie pokrywa się z drugim MEM., W tym przypadku Mi i Mj nie mogą być w zgodzie ze sobą.

  • Φ2B: obliczanie długości nakładania się mi i Mj. Jeśli \({MO} _ {i}^{J}\) jest mniejsze lub równe zeru, to nie ma na siebie nałożenia.

  • Φ2C: zachowanie kopii Mj przed wykluczeniem nakładania się.

  • Φ2D: jeśli istnieje nakładanie się, z wyłączeniem nakładania się z Mj

  • Φ2E: Obliczanie położenia końcowego Mj w T i Q.

  • Φ2F: Obliczanie odległości (liczby symboli) między mi i Mj w T i Q.

  • Φ2G: Obliczanie liczby niedopasowań i odstępów między Mi i MJ.,

  • Φ2H: Obliczanie kary za niedopasowanie i luki między Mi i Mj (\(p_ {I}^{j}\)). Jeśli istnieje luka, odejmuje się tylko jedną karę otwartą luki.

  • Φ2I: Obliczanie wyniku wyrównania \(\left (S_{I}^{J}\right)\), gdy MJ jest dodawane do wyrównania kończącego się na Mi. Wynik dla wszystkich pasujących symboli w Mj (Lj×Rm) jest dodawany do wyniku wyrównania dla wyrównania kończącego się na Mi (Si). Następnie odejmuje się karę za luki i niedopasowania między Mi i Mj\(\left (p_{I}^{J}\right)\).,

  • Φ2J: jeśli rozszerzenie Mj do wyrównania kończącego się w Mi spowoduje wynik \(\left (S_ {I}^{J} \ right)\) wyższy niż bieżący wynik dla Mj (Sj), to nowy wynik jest przechowywany w SJ. Również W jest ustawione na i, aby śledzić Mi, które maksymalizują wynik dla Mj.

  • Φ2K: przywrócenie wartości Mj przed wykluczeniem, aby Mj mógł być używany w innych rozszerzeniach wyrównania.

  • Φ3: Szukam MEM z najwyższym Sj. Ten MEM jest ostatnim MEM w wyrównaniu (Me)., Najwyższy wynik (Se) jest zwracany jako S, który jest najwyższym wynikiem wyrównania dla danej sekwencji. Indeks MEM, który maksymalizuje Sj jest przechowywany w e, aby rozpocząć śledzenie ode mnie.

  • Φ4: w wyrównaniu, najbliższy poprzedni MEM dla mnie jest ten, który maksymalizuje wynik wyrównania dla mnie. Indeks takiego Mem jest przechowywany w W. w rezultacie iteracja f←w odwiedza indeks wszystkich memów w wyrównaniu. Gdy W jest równe -1, Mf jest pierwszym MEM w wyrównaniu i iteracja jest zatrzymywana.,

w naszym algorytmie nie penalizujemy niedopasowań i luk przed pierwszym MEM i po ostatnim MEM w wyrównaniu. Skutkuje to lokalnym algorytmem wyrównywania. Biorąc pod uwagę te kary, algorytm generuje globalne wyrównanie (dodatkowy plik 1: Sekcja V).

równanie do obliczenia \(p_{I}^{j}\) W Φ2H algorytmu 2 zakłada, że nie ma pasującego symbolu między T i Q w obszarze między Mi i Mj (wszystkie symbole są liczone jako niedopasowania lub luki)., Chociaż to założenie nie jest prawdziwe dla wszystkich Mi, zawsze jest prawdziwe dla Mi, które prowadzi do maksimum \(s_{i}^{j}\), które unieważnia efekt błędnego założenia dla innych Mi. Jako dowód, Załóżmy, że istnieje pasujący symbol w obszarze między Mi i Mj. Pasującym symbolem będzie MEM (Mk). Mk jest już rozszerzony do wyrównania kończącego się na Mi. Tak więc, przy przedłużaniu Mj do Mk uzyskuje się wyższy wynik w porównaniu z przedłużaniem Mj do Mi.

Łańcuchowanie nasion colinear, jak omówiono w były szeroko stosowane w wyrównaniu dużych sekwencji, tj. wyrównanie genomu do genomu., Został on również użyty do identyfikacji regionów kandydujących do odczytu ze względu na zestaw MEMs w BWA. Algorytmy łańcuchowe z punktacją są podobne do zaproponowanego przez nas algorytmu programowania dynamicznego (DP-MEM). Istnieją jednak różnice, które sprawiają, że DP-MEM nadaje się do parowego wyrównania krótkich sekwencji. DP-MEM bierze pod uwagę, że wszystkie MEMs w pewnej wielkości luki są dostarczane na wejściu i optymalizuje liczbę iteracji w algorytmie. DP-MEM wdraża również podejście heurystyczne, aby zrekompensować efekt krótkich memów usuniętych z listy wejściowej, wynikających z przerw między memami.,

Optymalizacja

biorąc pod uwagę sekwencje o długości n, algorytm do wyodrębniania memów (podany w sekcji „ekstrakcja MEM”) wymaga operacji 2(N−1) shift i 2n−1 na wektorach bitowych (każda działa na \(\lceil \frac {n}{32} \rceil \) słów maszynowych), które skutkują algorytmem o złożoności O(n2) do wytworzenia wektorów bitowych krawędzi dla danej pary sekwencji. Złożoność funkcji, która oblicza pozycjonowanie MEMs z wektora bitowego krawędzi i sortuje je na podstawie korektora, nie została jeszcze dodana. Ponadto, jeśli M MEMs są ekstrahowane, Φ2 algorytmu 2 (DP-MEM) ma złożoność O (m2)., Biorąc pod uwagę złożoność ekstrakcji MEM i DP – mem, mem-Align jest znacznie wolniejszy od dostępnych algorytmów wyrównywania. Aby przyspieszyć proces, przedstawiamy kilka optymalizacji dla MEM-Align, które osiąga szybszy czas pracy poprzez rezygnację z dokładności. Z drugiej strony Wprowadzamy metody poprawy dokładności przy minimalnej utracie wydajności.

wyrównanie pasmowe

wyrównanie pasmowe jest znaną metodą heurystyczną przyspieszającą proces wyrównywania. Technika ta ogranicza wzór luk w wyrównaniu(dodatkowy plik 1: Sekcja VI)., W związku z tym, jeśli wyrównanie między dwoma sekwencjami nie jest zgodne z tym wzorem, algorytm nie zidentyfikuje wyrównania. W tradycyjnym programowaniu dynamicznym wyrównanie uzyskuje się po obliczeniu wartości wszystkich komórek w tabeli. Jednak przy optymalizacji wyrównania pasmowego oceniane są tylko komórki na średnicy i blisko przekątnej. gl jest szerokością pasma w pasmowym wyrównaniu, gdzie komórki dalej niż gl do średnicy nie są oceniane. Ciemniejsze komórki na Rys. 1 show the case where gl=1.,

w przeciwieństwie do tradycyjnego dynamicznego podejścia do programowania, mem-Align nie ma podobnej tabeli do zastosowania wyrównania pasmowego. Jednak okazało się, że możemy symulować ten sam efekt, ograniczając liczbę operacji zmiany w procesie ekstrakcji MEM. Na przykład, jeśli przesuniemy sekwencję zapytań do GL w prawo i w lewo, osiągniemy wyrównanie pasmowe z pasmem gl. Banded-alignment zmniejsza złożoność ekstrakcji MEM Z O(n2) do O(N. (2GL+1)), Gdzie gl jest małą i stałą wartością. Tak więc złożoność ekstrakcji MEM jest O (n), gdy stosuje się wyrównanie pasmowe., Ponadto, przy wspomnianym wyrównaniu pasmowym, prawdopodobne jest, że wydobywa się mniej memów, co przyspiesza kolejne kroki algorytmu.

krótkie usuwanie MEM

zauważyliśmy, że większość wyodrębnionych Mem jest krótka i jest wynikiem losowego dopasowania symboli. Aby przyspieszyć mem-Align, MEMs krótsze niż sl są filtrowane podczas procesu ekstrakcji MEM. Zmniejsza to liczbę memów do wyodrębnienia i przetworzenia (następnie przyspiesza algorytm). Filtrowanie krótkich MEM odbywa się poprzez rozszerzenie algorytmu 1 o zestaw operacji przesunięć i bitów (dodatkowy plik 1: Sekcja VII).,

z drugiej strony istnieją rzadkie przypadki, w których krótkie memy są częścią wyrównania; na przykład pasujący symbol otoczony niedopasowaniami. Bez posiadania wszystkich memów na liście wejściowej, DP-MEM nie jest w stanie znaleźć takiego samego wyrównania, jakie znajduje, gdy wszystkie memy istnieją na liście wejściowej. Aby zrekompensować utratę krótkich memów na wejściu, modyfikujemy Φ2H DP-MEM, aby rozważyć możliwość krótkich dopasowań między memami (dodatkowy plik 1: Sekcja VIII).

mogą wystąpić trudniejsze przypadki, w których w wyrównaniu istnieje wiele krótkich memów między dwoma memami (patrz Rys. 9)., Jedynym sposobem poprawnej identyfikacji wyniku dla obszaru między Mi i Mj w Φ2H jest zastosowanie globalnego wyrównania do tego regionu. Jednak Φ2H jest częstą operacją i powinien pozostać szybki. W związku z tym postanowiliśmy częściowo rozwiązać problem poprzez ograniczenie możliwych przypadków (metoda heurystyczna).

rys., 9

przykład, który pokazuje wiele krótkich MEM w małym obszarze między Mi i Mj w wyrównaniu

Jeśli są luki w obszarze między Mi i Mj MJ, Zakładamy, że jest tylko jedna ciągła szczelina albo na lewym lub prawym końcu obszaru. Następnie możliwe są tylko dwa wyrównania dla obszaru., Liczba pasujących symboli jest liczona w obu przypadkach w sposób sekwencyjny, a ten, który skutkuje maksymalnymi meczami, jest brany jako liczba meczów między Mi i Mj (dodatkowy plik 1: Sekcja IX). Porównywanie sekwencyjne jest kosztowną operacją i opracowujemy metodę, aby uniknąć porównywania sekwencyjnego, gdy jest to możliwe (dodatkowy plik 1: Sekcja X).

każdy inny przypadek, który nie pasuje do powyższego założenia, skutkuje wyrównaniem z niższym wynikiem., Biorąc jednak pod uwagę niski odsetek luk i niedopasowań, możliwość wystąpienia wielu luk i niedopasowań na niewielkim obszarze jest niska.

rozszerzenie efektywnego wyrównania

w Φ2 DP-MEM, Mj rozszerza wszystkie wyrównania, które kończą się {M1…Mj−1} (jeśli to możliwe). Jednak dla każdego Mj istnieje mniejszy podzbiór Ωj⊆{M1…Mj-1} taki, że rozszerzając Mj na wszystkie wyrównania kończące się Mi ω Ωj, wyrównanie kończące się Mj jest znalezione (Eq. 2). Innymi słowy, byłoby mniej \(s_{i}^{j}\) do oceny. Definicja zbioru Ωj i dowód Eq. 2 znajdują się w pliku dodatkowym 1: Sekcja XI., Definicja Ωj ma wpływ przy zastosowaniu optymalizacji usuwania krótkich MEM (dodatkowy plik 1: Sekcja XII).

$$ \max\limits_{M_{i} \in \Omega_{j}}{s_{I}^{j}} = \max\limits_{1 \leq i \leq j-1}{S_{I}^{j}} $$
(2)

wyrównanie Hybrydowe

aby zachować dokładność algorytmu, postanowił wykorzystać metodę hybrydową będącą połączeniem algorytmu mem-alignment i Smitha-Watermana. Definiujemy trzy przypadki, w których mem-Align może być niedokładne., Jeśli wyrównanie pary sekwencji spadnie do jednego z tych przypadków, używamy algorytmu Smitha-Watermana do wyrównania sekwencji. Te przypadki to:

  • gdy sekwencje są powtarzalne, a liczba wyodrębnionych memów przekracza próg TM. Okazało się, że mem-Align może powodować niedokładne wyrównanie podczas wyrównywania powtarzalnych sekwencji. Odpowiednia wartość TM zmniejsza szansę zgłaszania niedokładnego dostosowania z znikomym wzrostem średniego czasu przetwarzania.,

  • gdy obliczony wynik wyrównania dla wyrównania wygenerowanego przez mem-Align jest niższy niż próg TS. Ten przypadek najczęściej występuje, gdy występuje luka w wyrównaniu, której nie można zidentyfikować z powodu wyrównania pasmowego.

  • gdy nie istnieje żaden MEM dłuższy niż sl do wyodrębnienia (rzadki przypadek)., Jeśli sl jest ustawiona na wysoką wartość, a podobieństwo między sekwencjami jest niskie,

chociaż wysyłanie par sekwencji do zewnętrznego algorytmu powoduje dodatkowe obliczenia, liczba sekwencji wysłanych do zewnętrznego algorytmu pozostaje niewielka, jeśli odpowiednie wartości zostaną wybrane dla TM I TS.

pomijanie odległych memów

gdy odległość między Mi i Mj jest duża, nie jest prawdopodobne, że Mi i Mj będą sąsiadującymi memami w wyrównaniu., Dlatego algorytm pomija rozszerzenie, jeśli odległość między Mi i Mj jest dłuższa niż próg TD(dalsze zmniejszenie liczby \(s_{i}^{j}\), które ma być oceniane). Ta optymalizacja nieznacznie poprawia wydajność przy znikomym wpływie ubocznym na dokładność.