Definicja

Reprezentacja struktury drugorzędowej jako drzewo

Odległość Levenshteina

\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}

Przykład

. . . ( ( ( . . ) ) )
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

Interaction Network Fidelity (INF)

Przykład

Generator sekwencji

Poniższa sekwencja generuje się losowo z każdym odświeżeniem strony.

Treść zadania

Przewidywanie struktury RNA z pojedynczej sekwencji (przygotowanie raportu na ocenę 3.0)

  1. Zachowaj wylosowaną sekwencją RNA.

  2. Uruchom narzędzie RNAfold do przewidzenia struktury drugorzędowej.

  3. 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.

  4. Spis obserwacje nt. podobieństwa otrzymanych struktur drugorzędowych np. czy RNAfold i RNAstructure przewidziały podobne motywy strukturalne?

Przewidywanie struktury RNA z alignmentu wielu sekwencji (kontynuacja raportu na ocenę 3.5)

  1. Wybierz jedną z rodzin Rfam (niech każdy w grupie wybierze inną):

  2. Z menu po lewej, wybierz Alignment, a następnie dla Alignment format wybierz wartość FASTA (UNgapped)

  3. Ze ściągniętego pliku wybierz 10 pierwszych sekwencji wraz z identyfikatorami

  4. Wejdź na stronę narzędzia TurboFold z pakietu RNAstructure. Zleć zadanie jednoczesnego przewidywania struktur dla tych 10 sekwencji:

  5. Wejdź na stronę LocARNA i powtórz eksperyment z wykorzystaniem tego narzędzia:

  6. 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?

Porównywanie struktur drugorzędowych

  1. Zaimplementuj miarę INF dla struktur w formacie dot-bracket. Do raportu dołącz kod oraz przedstaw wyniki dla struktur otrzymanych wcześniej (ocena 4.0)
  2. Zaimplementuj algorytm wyznaczania odległości Levenshteina dla struktur w formacie dot-bracket. Do raportu dołącz kod oraz wyniki dla struktur otrzymanych wcześniej (ocena 4.5)
  3. Zaimplementuj zapis struktury drugorzędowej w postaci drzewa HIT oraz eksport do formatu tekstowego w wyniku przechodzenia drzewa w kolejności preorder. Do raportu dołącz kod oraz odległości Levenshteina dla tak zapisanych struktur (ocena 5.0)