S → '(' S ')'
Strukturę RNA można przedstawić jako uporządkowane, etykietowane drzewo
Liść w takim drzewie odpowiada nukleotydowi niesparowanemu
Węzeł wewnętrzny reprezentuje parę nukleotydów
Korzeń drzewa jest wirtualnym węzłem rodzicem dla zewnętrznych
nukleotydów
Drzewo to można uprościć do formatu HIT (homeomorphically irreducible tree), w którym grupowane są:
Oba rodzaje drzew możemy wypisać w kolejności preorder:
U
(unpaired) lub P
(paired) podczas wychodzenia z wierzchołka, dopisując wagę w
przypadku drzew HIT i zamykając nawiasWynik dla pierwszego drzewa:
((((((((U)(U)(((((U)(U)(U)(U)P)P)P)P)(U)(((((U)(U)(U)P)P)P)P)(U)(U)(U)(U)(U)((((((U)(U)(U)(U)P)P)P)P)P)P)P)P)P)P)P)P)(U)(U)
Wynik dla drzewa HIT:
((U2)((U4)P4)(U1)((U3)P4)(U5)((U4)P5)P7)(U2)
\begin{algorithm}
\begin{algorithmic}
\FUNCTION{LevenshteinDistance}{$s:$ ciąg znaków $[1..m]$, $t:$ ciąg znaków $[1..n]$}
\STATE {$ d \gets \emptyset $} \COMMENT {$ d $ to tablica dwuwymiarowa $ [0..m][0..n] $}
\FOR {$ i \gets 0 $ \TO $ m $}
\STATE {$ d[i][0] \gets i $}
\ENDFOR
\FOR {$ j \gets 1 $ \TO $ n $}
\STATE {$ d[0][j] \gets j $}
\ENDFOR
\FOR {$ i \gets 1 $ \TO $ m $}
\FOR {$ j \gets 1 $ \TO $ n $}
\IF {$ s[i] = t[j] $}
\STATE {$ cost \gets 0 $}
\ELSE
\STATE {$ cost \gets 1 $}
\ENDIF
\STATE {$ d[i][j] \gets $ \CALL{Min}{$ d[i-1][j] + 1, d[i][j-1] + 1, d[i-1][j-1] + cost $}}
\ENDFOR
\ENDFOR
\RETURN {$ d[m][n] $}
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
...(((..)))
..(((...)))
. |
. |
. |
( |
( |
( |
. |
. |
) |
) |
) |
||
---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
. |
1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
. |
2 | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
( |
3 | 2 | 1 | 1 | 2 | 3 | 3 | 4 | 5 | 6 | 7 | 8 |
( |
4 | 3 | 2 | 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
( |
5 | 4 | 3 | 2 | 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
. |
6 | 5 | 4 | 3 | 2 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
. |
7 | 6 | 5 | 4 | 3 | 2 | 1 | 2 | 3 | 4 | 5 | 6 |
. |
8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 2 | 3 | 4 | 5 |
) |
9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 2 | 2 | 3 | 4 |
) |
10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 3 | 2 | 2 | 3 |
) |
11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 4 | 3 | 2 | 2 |
Innym sposobem na porównanie struktur RNA jest wyznaczenie podobieństwa zbiorów parowań
Oznaczmy przez \mathcal{A} zbiór par (i, j) takich, że w strukturze A istnieje para między i-tym i j-tym nukleotydem
Analogicznie oznaczmy jako \mathcal{B} zbiór par ze struktury B
Możemy teraz wyznaczyć trzy zbiory:
Na podstawie liczności tych trzech zbiorów możemy wyznaczyć miarę INF:
INF = \sqrt{\frac{TP}{TP+FN} \cdot \frac{TP}{TP+FP}}
Wartość INF mieści się w przedziale [0, 1] i jest to miara podobieństwa (im większa wartość tym bliższe sobie struktury RNA)
Uwaga! Miarę INF można wyznaczyć tylko gdy porównywane struktury mają chociaż jedną parę. W przeciwnym razie w mianowniku ułamków znalazłoby się zero.
Porównajmy:
(.(((...))).)
[((((..])))).
Zamieńmy struktury na listy par:
Wyznaczmy trzy zbiory:
Wyznaczmy wartość INF:
INF = \sqrt{\frac{3}{3+1} \cdot \frac{3}{3+2}} \approx 0.67
Poniższa sekwencja generuje się losowo z każdym odświeżeniem strony.
Zachowaj wylosowaną sekwencją RNA.
Uruchom narzędzie RNAfold do przewidzenia struktury drugorzędowej.
Wykonaj podobny eksperyment z wykorzystaniem narzędzia Fold z pakietu RNAstructure, a wynikowy plik w formacie CT przekonwertuj na dot-bracket korzystając z ct2dot.
Spis obserwacje nt. podobieństwa otrzymanych struktur drugorzędowych np. czy RNAfold i RNAstructure przewidziały podobne motywy strukturalne?
Wybierz jedną z rodzin Rfam (niech każdy w grupie wybierze inną):
Z menu po lewej, wybierz Alignment
, a następnie dla
Alignment format
wybierz
wartość FASTA (UNgapped)
Ze ściągniętego pliku wybierz 10 pierwszych sekwencji wraz z identyfikatorami
Wejdź na stronę narzędzia TurboFold z pakietu RNAstructure. Zleć zadanie jednoczesnego przewidywania struktur dla tych 10 sekwencji:
Wejdź na stronę LocARNA i powtórz eksperyment z wykorzystaniem tego narzędzia:
*.results
Porównaj struktury drugorzędowe z narzędzia TurboFold i LocARNA między sobą. Które narzędzie dało wynik bardziej zbliżony do konsensusowej struktury 2D z Rfam? Dlaczego tak uważasz?