\section{Hľadanie približných výskytov vzorky podľa editačnej vzdialenosti}
Hľadáme pozície $i$ také, že existuje $j \leq i$ t.ž. $d_E(P,T[j,i]) \leq k$ \par
\begin{center}
\includegraphics[width=0.35\textwidth]{figures/l17-kresba3}
\end{center}
Doteraz sme si predstavili riešenia podobných problémov:
\begin{displaymath}
\begin{array}{lll}
d_E(P,T[i-m+1..i]) = 0 & O(n)& \textrm{KMP}\\
d_H(P,T[i-m+1..i]) \leq k & O(nk)& \textrm{sufixový strom + lca} \\
\end{array}
\end{displaymath}
Možné riešenia nášho problému:
\begin{itemize}
    \item dynamické progamovanie $O(mn)$
    \item kombinované dynamické progamovanie, sufixové stromy a lca $O(nk)$ (nebudeme robiť)
\end{itemize}

Pripomeňme si, že hľadanie zarovnania pri výpočte editačnej vzdialenosti môžeme reprezentovať aj ako hľadanie najkratšej cesty v grafe z vrcholu $(0,0)$ do $(m,n)$. Tentokrát ale chceme zarovnať reťazec $P$ ku krátkemu kusu $T$, zmeníme teda aj graf.
% obrazok
\begin{center}
\includegraphics[width=0.65\textwidth]{figures/l17-kresba4}
\end{center}
\begin{itemize}
    \item pridáme na začiatok vrchol $s$
    \item pridáme hrany $(s,(0,j)) \forall j=0 \dots n$ s cenou 0
    \item cesta zo $s$ do $(m,i)$ zodpovedá zarovnaniu $T[j\dots i]$, kde $j$ je taká, že cesta začína  hranou $(s,(0,j-1))$
    \item spustíme dynamické programovanie, ako sme mali predtým, až na prvý riadok, lebo tam použijeme hrany $(s,(0,j))$ s cenou $0$
    \item vypíšeme $i$ také, že  $A[m,i] \leq k$
\end{itemize}

Takto budeme vypisovať konce, ak chceme nájsť začiatky, tak spustíme tento algoritmus na reverz slova
\subsubsection*{Patologický prípad}
$T=a^n$, $m = n / 2$ \par
$P=a^m$, $k = n / 2$ \par
Výskytom je každá dvojica $(i,j)$, z toho vyplýva kvadratický počet výskytov.
Toto pre nás nie je efektívne a čo koby sme pre každý koniec vypísali najlepší začiatok?\par
$B_0[i,j] = l$, t.ž. $l$ je posledný vrchol grafu $0$, kde prechádza min, cestou z $s$ do $(i,j)$.
Pokiaľ nás zaujíma aj konkrétne zarovnanie a nie len jeho cena, bude v poli $A[i,j]$ cesta z $s$ do $(i,j)$,
v $B[i,j]$ budeme ukladať poslednú hranu $(m,j)$ pre $ A[n,j] \leq k$.\par
Nepotrebujeme si pamätať celú tabuľku so všetkými vypočítanými hodnotami, ale stačia nám posledné 2 riadky,
z ktorých vieme dopočítať zvyšné nasledujúce. Teda pamäťová zložitosť je $O(n+m)$.

\section{Úvod do bioinformatiky}
Bioinformatika je odvetvie na hranici informatiky a biológie, ktoré skúma matematické modely skúmaných biologických problémov. \par

\begin{enumerate}
    \item reťazce = sekvencie
    \item stromy
    \item veľa pravdepodobnosti a štatistiky
\end{enumerate}

\subsection{Reťazce DNA}
$\Sigma = \{ A,C,G,T\}$ \par
DNA je molekula s genetickou informáciou. Ľudský genóm(DNA) pozostáva z 24 reťazcov s celkovou dĺžkou $\sim 10^9$.
DNA = digitálny zápis, ktorý obsahuje predpisy na výrobu proteínov. Sú uložené v tabuľke, ktorú naývame \textbf{genetický kód}: $\{ A,C,G,T\}^3 \rightarrow$ aminokyselina \par
\textbf{Príklad:} $ATG \rightarrow M$ \par
DNA okrem proteínov hovorí aj kedy, kde a v akých množstvách sa má ktorý proteín tvoriť. Táto oblasť je stále predmetom skúmania, lebo stále ešte nepoznáme do detailov, ako tento mechanizmus funguje.
\subsection{RNA}
$\Sigma = \{ A,C,G,U\}$ \par
Má dvojakú funkciu, buď je to enzým alebo potom môže mať funkciu dočasne uchovávať informáciu z DNA
%obrazok RNA
\subsection{Proteíny}
Proteín je reťazec nad 20 prvkovou abecedou - 20 rôznych aminokyselín. V ľudskom organizme je asi $20000$ rôznych proteínov.\par
Dĺžka jedného proteínu je $\sim 100 - 1000$. Proteíny by sme mohli nazvať ako HW bunky. \par
Majú rozličné ulohy, napr. 
enzýmy - katalyzátory,
dôležité pre štruktúru bunky, signalizácia a iné.

\par
\subsection{Evolúcia}
Mutácia mení DNA a z toho pri evolúcii vznikajú rozdiely medzi rôznymi druhmi. Keďže je mutácia veľký zásah do organizmu, uchytia sa len tie, ktoré nrerobia nič zlé, alebo sú pozitývne pre jedinca. \par
Operácie ktoré menia DNA:
\begin{itemize}
    \item substitúcia, insercia, delécia
    \item duplikácia, preusporiadanie veľkých blokov
\end{itemize}

Keď porovnáme DNA dvoch ľudí, zistíme, že sa líšia približne v $0.1\%$ znakov. \par
človek a šimpanz sa líšia v $1\%$ znakov $\rightarrow 6 $mil. rokov \par
človek a myš sa líšia v $30\%$ znakov $\rightarrow 75 $mil. rokov \par
%obrazok
\begin{center}
\includegraphics[width=0.45\textwidth]{figures/l17-kresba5}
\end{center}
Z tohto vidíme, že existujú ostrovčeky podobností v mori iných sekvencií. Vidíme že v tých miestach pravdepodobne došlo k veľkej zmene. Taktiež z podobnosti môžeme dedukovať, že funkcie, ktoré sú veľmi dôležité pre život bunky nie sú zmutované a nachádzame aj $200$ znakov dlhé rovnaké sekvencie.\par

\begin{equation}
    \begin{array}{llllll}
    A&T&C&G&G&A\\
    A&-&C&G&G&A\\
    \end{array}
    \label{priklad_hypoteza}
\end{equation}
Jedna z hypotéz je, že napr. reťazce \ref{priklad_hypoteza} vznikli zo spoločného predka inserciou / deléciou. Z tohto príkladu si môžeme uvedomiť, že \textbf{zarovnanie} = \textbf{hypotéza o evolúcii}. Preto najdôležitejší problém, ktorý rieši bioinformatika je \textbf{lokálne zarovnanie}.

\section{Lokálne zarovnanie}
Dané sú $S$ a $T$, nájdi zarovanie medzi podslovami $S[i\dots j]$ a $T[p\dots q]$ s čo najväčšou podobnosťou $k$. \par
Použitie lokálneho zarovnania:
\begin{itemize}
    \item hypotéty o evolúcii
    \item určovanie funkcií na základe podobnosti
    \item na základe podobnosti nájsť zachované dôležité regióny DNA
\end{itemize}
%obrazok
%\begin{center}
%\includegraphics[width=0.45\textwidth]{figures/l17-kresba6}
%\end{center}

Toto zarovnanie zodpovedá ceste z $(i-1,p-1)$ do $(j,q)$.
Ako modifikovať graf?
%obrazok

Pridáme hrany $(s,(i,p)) \forall i = 0 \dots m, \forall p = 0 \dots n $ s cenou 0.
%\par \begin{center}
%\includegraphics[width=0.45\textwidth]{figures/l17-kresba7}
%\end{center}
Naša výsledná rekurencia:

\begin{equation}
    A = \left\{ \begin{array}{l}
             0 \\
             A[i-1,j-1]+ w(S[i],T[i])\\
             A[i,j-1]+ w(-,T[j])\\
             A[i-1,j]+ w(S[i],-)\\
        \end{array}
    \right.
\end{equation}
Konce zarovnaní $(j,q)$ t.ž. $A[j,q] \geq k$. \par
Náš cieľ:
%obrazok
Chceme vypísať neprekrývajúce sa rozdielne zarovnania matice. \par

\subsection{Lokálne zarovnania s dlhými inzerciami a deléciami}
Uvedomme si, že po istej sekvencie mohol byť vložený iný úsek genetickej informácie a teda mali by sme to brať ako jednu inzerciu. Preto musíme ešte pridať hrany:
$$ (i,j) \rightarrow (i,k) j < k \textrm{, váha }1$$
$$ (i,j) \rightarrow (k,j) i < k \textrm{, váha }1$$
Čo bude teraz rekurencia?

\begin{equation}
    A[i,j] = \max
    \left\{ \begin{array}{l}
             A[i-1,j-1]+w(S[i],T[j]) \\
             \max_{k < i} A[k,j] - 1\\
             \max_{k < j} A[i,k] - 1\\
        \end{array}
    \right.
\end{equation}

Časová zložitosť je O(m.n(m+n))
\par
Lepšie riešenie: majme 3 kópie každého vrcholu $(i,j)_u$ - uhlopriečka, $(i,j)_v$ - vodorovne, $(i,j)_z$ - zvislo.
\par
Kam sa dostaneme z $(i,j)$?
\begin{equation}
    \begin{array}{lllll}
             (i,j)_u& \rightarrow & (i,j+1)_v & -1& \textrm{začiatok insercie alebo delécie}\\
             (i,j)_z& \rightarrow & (i,j+1)_v & -1& \textrm{začiatok insercie alebo delécie}\\
             (i,j)_{u|v}& \rightarrow & (i+1,j)_z & -1& \textrm{začiatok insercie alebo delécie}\\
             (i,j)_v& \rightarrow & (i,j+1)_v & 0& \textrm{pokračovanie}\\
             (i,j)_z& \rightarrow & (i+1,j)_z & 0& \textrm{pokračovanie}\\
             (i,j)_{u|v|z}& \rightarrow & (i+1,j+1)_u & w(S[i],T[i])&\\
    \end{array}
\end{equation}

Potom počítame maximumum z 9 možností a teda dostávame časovú zložitosť: O(m.n) lebo máme $9mn$ hrán.



