Algorytm Nussinowa

Klasa	Przewidywanie struktury kwasu nukleinowego
Wydajność w najgorszym przypadku	${\ Displaystyle O (n ^ {3})}$
Złożoność przestrzeni w najgorszym przypadku	${\ Displaystyle O (n ^ {2})}$

Algorytm Nussinova to algorytm przewidywania struktury kwasu nukleinowego stosowany w biologii obliczeniowej do przewidywania fałdowania cząsteczki RNA , który wykorzystuje zasady programowania dynamicznego . Algorytm został opracowany przez Ruth Nussinov pod koniec lat 70.

Tło

Origami RNA występuje, gdy cząsteczka RNA „zwija się” i wiąże się ze sobą. To fałdowanie często określa funkcję cząsteczki RNA. RNA fałduje się na różnych poziomach, ten algorytm przewiduje drugorzędową strukturę RNA.

Algorytm

Punktacja

Punktujemy rozwiązanie, licząc całkowitą liczbę sparowanych zasad. Zatem próba maksymalizacji wyniku, który maksymalizuje całkowitą liczbę wiązań między zasadami.

Motywacja

$_$ sekwencję $zbioru$ pochodzą _ Wyobraźmy sobie, że mamy optymalne rozwiązanie podproblemu składania do $\$$Displaystyle S_ {j-1}}$ i optymalne rozwiązanie do składania $S_{u}}$${\ displaystyle S_ {i$ do ${\ Displaystyle S_ {v}}$${\ Displaystyle i \ równoważnik u \ równoważnik v \ równoważnik j-1}$ . Teraz, aby wyrównać do $S_ {i}}$ mamy dwie opcje: ${ \$

1. Pozostaw $niesparowane$ i zachowaj strukturę do S $displaystyle S_$$-1}$ \ $wyrównania$ będzie równy wynikowi wyrównania do , ponieważ $par$ utworzono żadnych nowych
2. Połącz ${\ Displaystyle S_ {j}}$ z ${\ Displaystyle S_ {k}}$ , gdzie ${\ Displaystyle i \ leq k <j}$ . Wynik dla tego wyrównania będzie wynikiem parowania zasad plus wynik najlepszego wyrównania $S_ {i}}$${\ Displaystyle S_ {k + 1}}$ displaystyle do i ${\ Displaystyle S_ {k-1}}$ do ${\ Displaystyle S_ {j-1}}$ .

Algorytm

Rozważmy sekwencję RNA o długości $sol$ , że $i } \ w \$$A, U, C,$ .

Skonstruuj macierz $razy n$$}$ . Zainicjuj tak, że ${\ displaystyle M}$

${\ Displaystyle M (i, i) = 0}$

${\ Displaystyle M (i, i-1) = 0}$

dla ${\ Displaystyle 1 \ równoważnik ja \ równoważnik n}$ .

${\ Displaystyle M (i, j)}$ będzie zawierał maksymalny wynik dla podsekwencji ${\ Displaystyle S_ {i}... S_ {j}}$ . Teraz wypełnij wpisy $górę$ iw prawo, tak aby

${\ Displaystyle M (i, j) = \ max _ {i \ równoważnik k <j} {\ rozpocząć {przypadki} M (i, k-1) + M (k + 1, j-1) + {\ tekst {Wynik}}(S_{k},S_{j})\\M(i,j-1)\end{przypadki}}}$

gdzie ${\ Displaystyle {\ tekst {Wynik}} (S_ {k}, S_ {j}) = {\ rozpocząć {przypadki} 1, i S_ {k} {\ tekst {i}} S_ {j} {\ tekst {komplementarny }}\\0,&{\text{inaczej.}}\end{przypadki}}}$

${\ Displaystyle S_ {i}... S_ {j}}$$,$ mamy $macierz$ w S .

$określić$ strukturę złożonego RNA za pomocą śledzenia wstecznego, najpierw tworzymy pustą listę . Inicjujemy za pomocą ${\ displaystyle i=0, j = n}$ . Następnie podążamy za jednym z trzech scenariuszy.

1. Jeśli $zatrzymuje$ procedura
2. ${\ Displaystyle M (i, j) = M (i, j-1)}$ , to ustaw $Displaystyle i=i,j=j-1}$ , i kontynuuj.
3. $}$$i$ wszystkich , jeśli ${\ Displaystyle S_ {k}}$ są komplementarne i M. ${\ Displaystyle M (i, j) = M (i, k-1) + M (k + 1, j-1) + 1} , dołącz ($ k $Displaystyle (k, j)}$ do $,$ a następnie prześledź oba z ${\ Displaystyle i = i, j = k-1}$$\ Displaystyle i =k+1,j=j-1}$ ja .

Po zakończeniu śledzenia wstecznego $zawiera$ wszystkie sparowane zasady

Ograniczenia

Algorytm Nussinov nie uwzględnia trójwymiarowego kształtu RNA ani nie przewiduje pseudowęzłów RNA . Co więcej, w swojej podstawowej formie nie uwzględnia minimalnego pętli łodygi . Jednak nadal jest przydatny jako szybki algorytm do podstawowego przewidywania struktury drugorzędowej.