Zobrazenie zdroja stránky CB03

==Zarovnávanie sekvencií, opakovanie==
* Uvažujme skórovanie zhoda +3, nezhoda -1, medzera -2
* Reťazce TAACGG a CACACT

Globálne zarovnanie
* Rekurencia: A[i,j] = max {A[i-1,j]-2, A[i,j-1]-2, A[i-1,j-1]+s(x_i, y_j) }, pričom A[0,i]=-2i, A[i,0]=-2i
<pre>
        C   A   C   A   C   T
    0  -2  -4  -6  -8  -10  -12
T  -2  
A  -4  
A  -6  
C  -8  
G  -10  
G  -12  
</pre>

<!-- 
        C   A   C   A   C   T
    0  -2  -4  -6  -8 -10 -12
T  -2  -1  -3  -5  -7  -9  -7
A  -4  -3   2   0  -2  -4  -6
A  -6  -5   0   1   3   1  -1
C  -8  -3  -2   3   1   6   4
G -10  -5  -4   1   2   4   5
G -12  -7  -6  -1   0   2   3


 T  A  -  A  C  G  G
 C  A  C  A  C  -  T
-1  3 -2  3  3 -2 -1
-->

Lokálne zarovnanie
* Rekurencia: A[i,j] = max {0, A[i-1,j]-2, A[i,j-1]-2, A[i-1,j-1]+s(x_i, y_j) }, pričom A[0,i]=0, A[i,0]=0
<pre>
        C   A   C   A   C   T
    0   0   0   0   0   0   0
T   0 
A   0 
A   0 
C   0 
G   0 
G   0 
</pre>

<!--

        C   A   C   A   C   T
    0   0   0   0   0   0   0
T   0   0   0   0   0   0   3
A   0   0   3   1   3   1   1
A   0   0   3   2   4   2   0
C   0   3   1   6   4   7   5
G   0   1   2   4   5   5   6
G   0   0   0   2   3   4   4

 A  -  A  C
 A  C  A  C
 3 -2  3  3
-->

==Dotploty==
* Dotplot je graf, ktory ma na kazdej osi jednu sekvenciu a ciarky zobrazuju lokalne zarovnania (cesty v matici)
* Niekoľko príkladov dotplotov: {{pdf|Cb-dotplots}}
* Prvé príklady dotplotov porovnávajú rôzne mitochondriálne genomy
* Tieto boli vytvorene pomocou nastroja YASS http://bioinfo.lifl.fr/yass/yass.php 
* Dalsi priklad je zarovnanie genu Oaz Drosophila zinc finger s genomickym usekom chr2R:10,346,241-10,352,965
* Trochu iny dotplot, ktory funguje pre proteiny a nerobi lokalne zarovnania, iba spocita skore bez medzier v kazdom okne danej vysky a nakresli ciaru ak prekroci urcenu hodnotu
* http://emboss.bioinformatics.nl/cgi-bin/emboss/dotmatcher
* Vyskusame protein escargot voci sebe s hodnotami http://pfam.xfam.org/protein/ESCA_DROME window 8 threshold 24
* Pomocou YASSu vyskusame kluster zhlukov PRAME z ludskeho genomu

==Dynamické programovanie v Exceli==

===Práca so vzorcami v tabuľkovom procesore (Excel, LibreOffice, ...)===
* Okrem konkrétnych hodnôt, napr. 0.3, môžu byť aj vzorce, ktoré začínajú =, napr =0.3*0.3 dá do políčka 0.09 (* znamená násobenie)
* Vo vzorcoch môžeme používať aj hodnoty z iných políčok, napr. =A2+B2 dáme do políčka C2, zobrazí sa tam súčet
* Ak políčko so vzorcom skopírujeme do iného políčka, Excel sa snaží uhádnuť, ako zmeniť vzorec
** Ak sme v C2 mali =A2+B2 a skopírovali sme to do C3, vzorec sa zmení na =A3+B3
* Ak niektoré adresy políčok majú zostávať rovnaké aj pri kopírovaní, dáme pred písmeno aj číslo $,
** Ak v C2 máme =A2+$B$2 a skopírujeme to do C3, dostaneme =A3+B2
* Dolár môžeme dať aj pred iba jednu súradnicu (stĺpec alebo riadok), tá sa potom nebude pri kopírovaní meniť

===Späť k minciam===
* Vráťme sa k príkladu s rozmieňaním mincí a skúsme si ho "naprogramovať" v Exceli, resp. spreadsheet aplikácii v OpenOffice
* Vseobecna formulacia:
** Vstup: hodnoty k minci m_1,m_2,...,m_k a cielova suma X (vsetko kladne cele cisla)
** Vystup: najmensi pocet minci, ktore potrebujeme na zaplatenie X
* My pouzijeme mince hodnot 1,3,4
* Spravime si tabulku, kde si pre kazdu sumu i=0,1,2,...X pamatame A[i]=najmensi pocet minci, ktore treba na vyplatenie sumy i (ak je viac moznosti, zoberieme lubovolnu, napr. najvacsiu)
<pre>
i      0    1    2    3    4    5    6    7    8    9  
A[i]   0    1    2    1    1    2    2    2    2    3
</pre>
* vzorec  A[i] = min { A[i-1]+1, A[i-3]+1, A[i-4]+1 } 
* aby sme nemuseli zvlast uvazovat hodnoty mensie ako 4, (kde sa neda A[i-4]), urcime si A[-1], A[-2] atd ako nejake velke cislo (napr 100), takze vzorec plati pre vsetky i>0
<pre>
i      -4  -3  -2  -1  0    1    2    3    4    5    6    7    8    9  
A[i]  100 100 100 100  0    1    2    1    1    2    2    2    2    3
</pre>

* v exceli si najskor spravime horny riadok tabulky
** do nejakeho policka (napr, B4) zapiseme prvu hodnotu (-4)
** do susedneho C4 zapiseme vzorec =B4+1, dostaneme hodnotu -3
*** vzorce zacinaju znamienkom =
***B4 je suradnica policka o jedno vlavo, k nej pripocitame 1
** policko C4 nakopirujeme do riadku kolkokrat chceme, dostaneme hodnoty -2, -1, 0, 1,... 
*** kopirovat sa da tahanim laveho dolneho rohu okienka
*** vzorec sa automaticky posuva na =C4+1, =D4+1, atd
** o riadok nizsie do B5..E5 napiseme hodnotu 100 (okienka A[-4]..A[-1])
** do F5 dame 0 (okienko A[0] nasej tabulky)
** do G5 napiseme vzorec =MIN(F5+1,D5+1,C5+1), t.j. A[1] = min(A[1-1]+1,A[1-3]+1,A[1-4]+1)
** tento vzorec potom nakopirujeme do riadku tabulky
** F5 sa bude posuvat na G5, H5,... a podobne ostatne dva cleny

'''Cvičenie:'''
* Ako by sme zmenili na inu mincovu sustavu, napr. 1,2,5?
* Stiahnite si subor zo stranky predmetu a skuste si tuto zmenu urobit [http://compbio.fmph.uniba.sk/vyuka/mbi-data/cb03/mince.ods]


==Dynamické programovanie v Exceli (2)==

===Zarovnávanie sekvencií v Exceli===
* skusme si dynamicke programovanie pre globalne zarovnanie naprogramovat v Exceli
* budeme postupovat podobne ako pri minciach, ale potrebujeme dve specialne funkcie: MID(text,od,dlzka) z textu vyberie urcitu cast. Pomocou toho si vstupny text rozdelime na jednotlive pismena, ktore si napiseme do zahlavia tabulky
* vsimnite si pouzivanie dolarov v nazvoch policok: ak je pred menom stlpca alebo riadku $, tento sa neposuva ked vzorec kopirujem do inych policok
* IF(podmienka,hodnota1,hodnota2) vyberie bud hodnotu 1 ak je podmienka splnena alebo hodnotu2 ak nie je. Napr IF(F$8=$B12 ,1,-1) zvoli skore +1 ak sa hodnota v F8 rovna hodnote v B12 a skore -1 ak sa nerovnaju.

'''Cvicenie:''' 
* Zmente tabulku tak, aby skore pre zhody, nezhody a medzery bolo dane bunkami B1, B2 a B3 tabulky. Staci zmenit vzorce a policka D9, C10 a D10 a nakopirovat do zvysku tabulky. Ake bude skore najlepsieho zarovnania sekvencii AACGTA a ACACCTA ak skore nezhody je -2 a medzery -3?
* Ako treba zmenit vzorce, aby sme pocitali lokalne zarovnanie?
* Subor najdete [http://compbio.fmph.uniba.sk/vyuka/mbi-data/cb03/dynprog.ods tu]