Kontekst biologiczny
Cząsteczka RNA występuje najczęściej jako pojedyncza nić, która może zaginać się
i tworzyć pary zasad sama ze sobą. Komplementarne pary zasad to: A–U, G–C
oraz słabsza para wobble G–U. Prowadzi to do powstawania struktur drugorzędowych
takich jak hairpin loops, internal loops czy bulges.
Algorytm Nussinov (1978) znajduje maksymalną liczbę par zasad w sekwencji RNA,
zakładając brak pseudowęzłów. Jest to jeden z fundamentalnych algorytmów
programowania dynamicznego w bioinformatyce.
Relacja rekurencyjna
M[i][j] = max {
M[i+1][j],
M[i][j−1],
M[i+1][j−1] + δ(i,j),
maxi<t<j( M[i][t] + M[t+1][j] )
}
gdzie δ(i,j) to ocena pary zasad:
C–G = +3, A–U = +2, G–U = +1
(G–U tylko gdy włączone parowanie wobble), 0 w przeciwnym przypadku.
Warunek: j − i > k (minimalna długość pętli).
Pseudokod — Traceback
TRACEBACK(i, j):
jeśli j − i ≤ k: return
jeśli M[i][j] == M[i+1][j]:
TRACEBACK(i+1, j)
w.p.p. jeśli M[i][j] == M[i][j−1]:
TRACEBACK(i, j−1)
w.p.p. jeśli δ(i,j) > 0 i M[i][j] == M[i+1][j−1] + δ(i,j):
zapisz parę (i, j)
TRACEBACK(i+1, j−1)
w.p.p.:
znajdź t: M[i][j] == M[i][t] + M[t+1][j]
TRACEBACK(i, t)
TRACEBACK(t+1, j)
Złożoność
Czasowa
O(n³)
Pamięciowa
O(n²)
Trzy zagnieżdżone pętle przy wypełnianiu macierzy (długość podsekwencji,
pozycja startowa, punkt bifurkacji) dają złożoność sześcienną. Macierz n×n
wymaga pamięci kwadratowej.