Strukturę drugorzędową możemy zapisać na kilka sposobów
BP to dosłownie lista par
Jeśli każdy nukleotyd w sekwencji ma przypisany indeks (np. od 1 do 17), to pary kanoniczne możemy zapisać jako listę par indeksów
Przykładowy plik w formacie BP:
1 17
2 16
3 15
4 14
5 13
6 12
BPSEQ pozwala zapisać jednocześnie informację o sekwencji i strukturze drugorzędowej
Każda linia w pliku BPSEQ składa się z trzech kolumn:
Przykładowy plik w formacie BPSEQ:
1 G 17
2 G 16
3 G 15
4 A 14
5 C 13
6 C 12
7 U 0
8 U 0
9 C 0
10 C 0
11 C 0
12 G 6
13 G 5
14 U 4
15 C 3
16 U 2
17 C 1
CT pozwala przedstawić również RNA składające się z kilku nici
Pierwsza linia w pliku CT zawiera łączną liczbę nukleotydów
Każda kolejna linia w pliku CT składa się z 6 kolumn:
Dzięki kolumnom 3 i 4 można przedstawić koniec jednego i początek drugiego łańcucha
Ostatnia kolumna przydaje się jeśli struktura RNA w formacie CT (numerowanie od 1 do N) przedstawia fragment większej struktury (np. numerowany od 1000 do 1000+N)
Przykładowy plik w formacie CT:
20
1 g 0 2 20 1
2 C 1 3 19 2
3 A 2 4 18 3
4 G 3 5 17 4
5 A 4 6 16 5
6 G 5 7 15 6
7 A 6 8 14 7
8 G 7 9 13 8
9 C 8 10 12 9
10 G 9 0 11 10
11 c 0 2 10 11
12 G 1 3 9 12
13 C 2 4 8 13
14 U 3 5 7 14
15 C 4 6 6 15
16 U 5 7 5 16
17 C 6 8 4 17
18 U 7 9 3 18
19 G 8 10 2 19
20 C 9 0 1 20
Dot-bracket (czasami nazywany dot-parenthesis) to bardzo zwięzły format, w którym strukturę opisuje ciąg znaków takiej samej długości jak sekwencja
W formacie dot-bracket niesparowanemu nukleotydowi odpowiada znak
kropki .
, natomiast sparowane nukleotydy połączone
są nawiasami - w jednym miejscu jest (
a w drugim
)
Często pliki w formacie dot-bracket składają się z trzech linii:
>
i nazwa łańcucha (np.
>strand_A
)W przypadku cząsteczek RNA składających się z kilku łańcuchów, wystarczy zapisać kilka takich trójek:
>strand_A
gCAGAGAGCG
((((((((..
>strand_B
cGCUCUCUGC
..))))))))
Coraz częściej spotyka się rozszerzony format dot-bracket (extended dot-bracket), w którym dopuszcza się dodatkowe znaki:
-
dla oznaczenia tzw. brakującej reszty (zdarza
się, że sekwencja cząsteczki RNA jest znana, ale eksperymentalnie nie
udało się rozwiązać struktury dla wybranych nukleotydów)[]
, {}
oraz
<>
do oznaczenia pseudowęzłów (jeszcze wyższe rzędy
oznacza się parami wielka/mała litera: Aa
, Bb
,
itd.)Przykładowa struktura w rozszerzonym formacie dot-bracket:
>strand_A
gGAACCGGUGCGCAUAACCACCUCAGUGCGAGCAA
......[[[.{((....((]]]...).).}.))..
Trzeba zauważyć, że rozszerzony dot-bracket jako jedyny format koduje wprost obecność pseudowęzłów
Co więcej, jeśli struktura RNA zawiera pseudowęzeł, to istnieje wiele możliwości jej zapisu w rozszerzonym formacie dot-bracket (zakładając pewne kryteria oceny, mamy do czynienia z problemem optymalizacyjnym)
Wynikają z tego następujące wnioski:
Istnieje kilka algorytmów do zamiany {BP, BPSEQ, CT} → dot-bracket (Antczak et al., 2018; Zok et al., 2020)
Jednym z podstawowych jest FCFS (First-Come-First-Served)
\begin{algorithm}
\begin{algorithmic}
\PROCEDURE{FCFS}{$ bps $}
\STATE {$ stems \gets $} \CALL{FindStems}{$ bps $}
\STATE \CALL{SortByStartIndex}{$ stems $}
\STATE {$ stems[0].order \gets 0 $}
\FOR {$ i \gets 1 $ \TO $ n - 1 $}
\STATE {$ available \gets \{ $ true, true, true, $ ... \} $} \COMMENT {all orders available initially}
\FOR {$ j \gets 0 $ \TO $ i - 1 $}
\STATE {$ conflicted \gets $} \CALL{AreConflicted}{$ stems[i], stems[j] $}
\IF {$ conflicted $}
\STATE {$ available[stems[j].order] \gets $ false}
\ENDIF
\ENDFOR
\STATE {$ order \gets 0$}
\WHILE {$ available[order] = $ false}
\STATE {$ order \gets order + 1 $}
\ENDWHILE
\STATE {$ stems[i].order \gets order $}
\ENDFOR
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}
Ściągnij pliki wejściowe
Napisz program do konwersji z formatu dot-bracket do BPSEQ (ocena 3.0)
$ ./convert 1ET4-A.dbn
1 G 0
2 G 0
3 A 0
...
33 C 12
34 A 0
35 A 0
Napisz program znajdujący motyw hairpin (ocena 3.5)
$ ./hairpins 7K16-P.bpseq
13-CGAAAG-18
Napisz program znajdujący motyw stem (ocena 4.0)
$ ./stems 1ET4-A.bpseq
7-GGU-9 22-CCA-20
11-C-11 30-G-30
12-GC-13 33-CG-32
18-C-18 28-G-28
19-C-19 26-G-26
Napisz program znajdujący motyw single strand (ocena 4.5)
$ ./single_strands 1ET4-A.bpseq
1-GGAACCG-7
9-UGC-11
13-CAUAAC-18
22-CUCAG-26
26-GUG-28
28-GCG-30
30-GAG-32
33-CAA-35
Zaimplementuj algorytm FCFS (ocena 5.0)
$ ./fcfs.py 7K16-P.bpseq
gGCAAGGUACGGCGAAAGCCGUAGGGGCUUGAGAACCCCCCCUCCCCACUC
((...[[((((((....))))))((((...{{{...)))))).]]...}}}
Prawidłowe odpowiedzi można sprawdzić tutaj