%\usepackage{color}
%\usepackage{graphicx}

\section{Heuristické zrýchlenia pre editačnú vzdialenosť}

%$\mathcal{P}:= $'There is a bin containing two or more balls.'\par

Vypočet editačnej vzdialenosti slúži na hľadanie lokálneho zarovnania.
Základný algoritmus využíva  dynamické programovanie a beží v čaovej zložitosti O(m.n).
V niektorých prípadoch vieme pôvodný algoritmus vylepšiť. Musíme si uvedomiť, že editačnú vzdialenosť budeme rátať pre dlhé reťazce, a teda zložitosť O(n.m) je pre nás neprijateľná. Viď tabuľka \ref{cas_dyn_prog}

\begin{table}[h]
	\centering
	\begin{tabular}{|l|l|}
    \hline
    n& čas \\
    \hline
    100     & 0.0008 s \\
    1000    & 0.08 s \\
    10000   & 8 s \\
    100000  & 13 min \\
    $10^6$  & 22 hod \\
    $10^7$  & 3 mesiace \\
    $10^8$  & 25 rokov \\
    \hline
    \end{tabular}
\end{table}


\subsection{Baeza-Yates \& Perleberg 1992}
Približné výskyty vzorky s $d_E \leq k$ \par
Rozdelíme $P$ na úseky dĺžky $\lfloor {m \over k+1} \rfloor = r$

%obrazok
\begin{figure}[h]
\begin{center}
    \includegraphics[width=0.35\textwidth]{figures/l18-kresba1}
    \caption{Zarovanie}
\end{center}
\end{figure}

\textbf{P}= mno6ina kúskov \par
Každé zarovnanie má aspoň 1 kúsok bez zmeny. Zoberieme si množinu kúskov a nájdeme si všetky ich výskyty v \textbf{P} použijeme  Aho - Corasickov algoritmus. \par
Časová zložitosť: O($n+m+|I|$) \par
Vylepšeie: Budeme rátať dyn. programovaním len tam, kde sa môže vyskytovať.

%obrazok
\begin{figure}[h]
\begin{center}
    \includegraphics[width=0.55\textwidth]{figures/l18-kresba2}
\end{center}
\end{figure}

Zoberieme kúsok začínajúci na $(i,j)$.
Pre každý výskyt $(i,j) \in  I$ hľadáme približné výskyty  $P$ v $T[j-m-k,j+m+k]$ dyn. progamovaním v čase O($m^2$)

Zložitosť spolu O($n+m^2|I|$) $\Rightarrow$ budeme analyzovať \par
Praktické zlepšenia: zlučovanie prekrývajúcich sa intervalov.

%obrazok
\begin{figure}[h]
\begin{center}
    \includegraphics[width=0.55\textwidth]{figures/l18-kresba3}
\end{center}
\end{figure}

Týmto sme dosiahli, že nám stačí prehľadať menšie časti. Avšak po použití zlúčenia máme časovú zložitosť O($n+m^2$), to je taká istá ako má dynamické programovanie. \par

Budeme analyzovať $|I|$ v priemernom prípade:
$$ {1 \over {\sigma^n} }\sum_{T \in \Sigma^n}|I_{(P.T)}|$$

%obrazok skraitkovia
\begin{figure}[h]
\begin{center}
    \includegraphics[width=.75\textwidth]{figures/l18-kresba4}
\end{center}
\end{figure}

Možeme ich použiť viackrát a tak dostaneme \textbf{E}(X). Prečo práve takto? Lebo v takomto príde je to zadefinované aj keď máme nerovnomerne rozdelenú pravdepodobnosť na $\Sigma^yn$.
Môžeme použiť linearitu \textbf{E}(X+Y) = \textbf{E}(X)+\textbf{E}(Y)
     $\textbf{E}(X) = \sum_{x \textrm{ z oboru hodnôt } X} P(X = x)x$
 $$ X_{i,p} =
   \left\{
   \begin{array}{ll}
   	1 & \mbox{ak } P	=T[i\dots i+p-1], p \in P \\
	0 & \mbox{inak}	\\
  \end{array}\right.
  $$
$$X = \sum^n_{i=1} \sum_{p in P} X_{ip} $$
$$E(X)=\sum_i \sum_p E(X_{i,p})$$
$$E(X_{ip}) = P(X_{ip}=0).0 + P(X_{ip}=1).1$$
$$P(X_{ip}=1)=P(T[i]=p[i] \land T[i+1]=p[i-1]\land[i+j-1]=p[r])= $$
$$ =\prod_{j=1}^r \underbrace{P(T[i+j-1]=p[j])}_{1 \over \sigma}\leq \sigma^{-r}$$

výsledok: $E(X) = \sigma^{-r} . n . (k-1)$ \par
priemerný prípad je O$(n+n(k+1)\sigma^{-r}m^2)$
pravdepodobnosť, že $k < m / (6 log_{\sigma} m)$
$r = {\lfloor {m \over k+1} \rfloor} \geq {m \over 2k} \geq {m \over {2m / 6\log_{\sigma}m}} = 3.\log_{\sigma} m$

$\sigma^{-r} \leq \sigma^{-3\log_{\sigma}m = {1 \over m^3}}$

Celkový čas v priemernom prípade je O(n).
$10, T=4$
\begin{equation}
    \begin{array}{llll}
    6m = &10&T=4&k\leq 1\\
    &100& &k \leq 5\\
    &1000& &k \leq 33\\
    \end{array}
\end{equation}

\begin{equation}
    \begin{array}{l}
    O(m.n)\\
    O(k.n)\\
    \end{array}
    \left \}
        \textrm{v najhoršom prípade}
    \right.
\end{equation}


%insert text 4.

hľadáme nejaké zarovnania:
$w(a,a) = 1; w(a,b) = -1; w(a,-) = w(-,a) = -\infty $ \par
lokálne zarovnanie s cenou $\geq k$. \par
Hľadáme hrany dĺžky $w$, ktoré sa zhodujú: \par

\begin{equation}
    \begin{array}{lllll}
        (i,j) & S[i \dots i + w -1] &=& S[j \dots j + w -1] \\
        \underbrace{1-11}_{1}&\underbrace{1-11}_{1}&&\underbrace{1-11}_{1}\\
    \end{array}
\end{equation}

\begin{equation}
    \begin{array}{lllll}
    A&G&T&C&A\\
    A&G&T&C&G\\
    \end{array}
\end{equation}
Nájdeme množinu dvojíc $(i,j)$, ktoré sa zhodujú (v jadrách) $S[i \dots i + w -1] = S[j \dots j + w -1]$. Pokúsime sa ísť po uhlopriečke a rozšíriť zarovnanie.
% obrazok
S rozšírením skončíme, keď je cena rozšírenia menšia alebo rovná ako cena doterajšieho najlepšieho rozšírenia. Ak je skoré vačšie ako $k$ vypíšeme. \par
Ako to môžeme robiť?
\begin{itemize}
    \item sufixové stromy O($n+m.|I|$)
    \item Aho-Corasick algoritmus O($m.n + n$)
\end{itemize}
Keď budeme analyzovať O($|I|.\min(m,n)$) zistíme, že v praxi O($|I|$) skôr závisí od $T$.\par
Prečo nenájdeme zarovnanie so skóre $\geq k$?
\begin{itemize}
    \item lebo neobsahuje jadro $w$
    \item obsahuje jadro, ale skončíme rozširovanie priskoro
    \item závisí od $T$
\end{itemize}


%obrazky w male, w velke
%obrazok skraitkovia
\begin{figure}[h]
\begin{center}
    \includegraphics[width=.85\textwidth]{figures/l18-kresba5}
\end{center}
\end{figure}

\subsection{BLAST}

Algoritmus bol vtvorený Stephenom Altschulom a spoločníkmi v roku $1990$.
Vytvoríme náhodné zarovnanie dĺžky $L$. \par
skóre v sĺpci:
\begin{itemize}
    \item $i+1$ s pravdepodobnosťou $p$
    \item $i-1$ s pravdepodobnosťou $(1-p)$
\end{itemize}
Hodíme $L$-krát mincou a tým získame zarovnanie. Potom zistíme, či sa v získanom zarovnaní nachádza za sebou $w$ jednotiek.
Následne vypočítame pravdepodobnosť P(odpoveď je áno) = 9L . Algoritmus využíva dynamické programovanie. \par
$Y$ = počet + $1$ na začiatku postupnosti
$Y = \{0,1,\dots,L\}$
\begin{equation}
    q_i=
    \left \{
        \begin{array}{ll}
        0& i<w\\
        p^w& i=w\\
        p^w+\sum_{j=0}^{w-1}p(1-p)q_i - j - 1& i>w\\
        \end{array}
    \right.
\end{equation}

% obrazok pruzky
%obrazok skraitkovia
\begin{figure}[h]
\begin{center}
    \includegraphics[width=.35\textwidth]{figures/l18-kresba6}
    \caption{Spočítame si v každom prúžku, koľko z nich obsahuje jadro}
\end{center}
\end{figure}

\begin{equation}
    \begin{array}{l}
        q_i=\sum^i_{j=0}((Y=i). P(\textrm{ jadro } | Y=j) =\\
        =\sum^{w-1}_{j=0}P(Y=i).P(\textrm{ jadro }|Y=j) + P(Y \geq w). P(\textrm{ jadro }|Y\geq w)=\\
        =\sum_{j=0}^{w-1}p^i(1-p).q_{i-j-1} + p^w
        E(|I|) = m.n.P((i,j)\in I)=m . \sigma^{-w}

    \end{array}
\end{equation}
%obrazok skraitkovia
\begin{figure}[h]
\begin{center}
    \includegraphics[width=.45\textwidth]{figures/l18-kresba7}
    \caption{na i - j - 1 môže byť jadro}
\end{center}
\end{figure}



