%\usepackage{textcomp}

\section{Zostavovanie DNA sekvencií}
\subsection{Najkratšie spoločné nadslovo (shortest common superstring)}

\begin{description}
 \item [Vstup:] $S_1,S_2, \ldots, S_k \in \Sigma^*$ 
 \item [Výstup:] Najkratší reťazec $S$ taký, že každé $S_i$ je podslovo $S$.
 \item [Príklad:] $\{$ ema, ma, mamu, mama, emu $\}$ a $S = $emamamuemu
\end{description}

Predpokladáme, že žiadne $S_i$ nie je podslovo $S_j$ ak $ i \neq j $. Pretože, také slová môžme vynechať.

Uvedený problém je NP-ťažký. Aby sme to mohli ukázať, zadefinujme si k nemu rozhodovací problém:

\begin{description}
 \item [Vstup:] $S_1,S_2, \ldots S_k \in \Sigma^*$ a $t$
 \item [Výstup:] Existuje spoločné nadslovo slov $S_1,S_2, \ldots S_k$ dĺžky najviac $t$? (áno/nie)
\end{description}


\begin{veta} Rozhodovací problém pre najkratšie spoločné nadslovo je NP-ťažký.
\label{l19-np}
\end{veta}
\paragraph{Dôkaz:} 1980 Galant, Maier, Storer 

V dôkaze použijeme redukciu z nasledujúcej verzie Hamiltonovskej cesty:
\paragraph{Hamiltonovská cesta:}
\begin{description}
	\item [Vstup:] Orientovaný graf s vrcholmi $1\ldots n$, každý vrchol, okrem vrcholu $n$ má aspoň 2 výstupné hrany.
	\item [Výstup:] Existuje cesta $1$ do $n$, ktorá prechádza cez každý vrchol práve raz?
\end{description}
\begin{veta} Hamiltonovská cesta je NP-úplný problém.\end{veta}

\paragraph{Dôkaz vety \ref{l19-np}} Musíme zostrojiť polynomiálny algoritmus, ktorý na vstupe dostane graf $G$ a transformuje ho na slová $S_1, S_2, \ldots S_k $ a $t$ také, že 
slová $S_1, S_2, \ldots S_k $ majú nadslovo dĺžky $t$ práve vtedy keď $G$ má hamiltonovskú cestu.

Algoritmus bude pracovať nad abecedou $ \Sigma = \{ 1,2, \ldots n \} \cup \{ \bar{1}, \bar{2}, \ldots \overline{n-1} \} \cup \{ \cent, \$, \# \}$. Pre každý vrchol 
$v \in G $ a pre každú hranu z $v$ do $w_0, w_1, \ldots w_{k-1}$ zostrojíme slová tvaru $\bar{v}w_i\bar{v}$ a $w_i\bar{v}w_{i+1 \bmod k}$. Presnejšie pre každý vrchol $v$
zostrojíme množinu slov
\[ A_v = \{ \bar{v}w_i\bar{v} : i=0 \ldots k-1 \} \cup \{w_i\bar{v}w_{i+1 \bmod k} : i=0 \ldots k-1\}\]
kde $k$ je počet odchádzajúcich hrán z $v$. Definujme si štandardné nadslovo 
\[ S_{v,w_i} = \bar{v}w_i\bar{v}w_{i+1}\bar{v}\ldots\bar{v}w_{i-1}\bar{v}w_i \]
Vidíme, že slovo $S_{v,w_i}$ je nadslovo množiny slov $A_v$. Pre každý vrchol z množiny $ v \in \{2,3,\ldots n-1\} $ definujme konektor
\[ C_v = \{ v\#\bar{v} \} \]
a nakoniec množinu terminálov
\[T = \{ \cent\#\bar{1}, n\#\$\} \]
Výstupná množina slov bude
	\[ L = (\cup_{v = 1 \ldots n-1} A_v) \cup (\cup_{v=2\ldots n-1} C_v) \cup T \]
a hľadaná dĺžka slova $t = 2m + 3n $, kde $m$ je počet hrán a $n$ je počet vrcholov grafu $G$.

\paragraph{cesta $\Rightarrow$ nadslovo} Máme hamiltonovskú cestu v $G$, ktorá prechádza vrcholmi v poradí $u_1,u_2,\ldots u_n$ ($u_1 = 1, u_n = n$). K tejto ceste
zostrojme reťazec $S = \cent\#S_{u_1,u_2}\#S_{u_2,u_3}\#\ldots\#S_{u_{n-1},u_n}\#\$$. Ukážme, že takýto reťazec $S$ je nadslovo slov z množiny $L$ a jeho dĺžka je $2m + 3n$. 
\begin{itemize}
 \item Keďže $S_{1,u_2}$ začína na $\bar{1}$ tak reťazec $\cent\#\bar{1}$ je podreťazec $S$. Podobne aj $S_{u_{n-1},u_n}$ končí na $n$, teda $n\#\$$ je podreťazec $S$.
 \item Hamiltonovská cesta obsahuje všetky vrcholy, potom $S$ obsahuje všetky reťazce $S_{i,i+1}$ pre $i=1,2,\ldots n-1 $. Vieme, že $S_{i,i+1} $ je nadslovo pre množinu $A_i$, teda $S$
	je nadslovo pre všetky $A_i$ kde $i = 1,2,\ldots n-1$.
\item Je ľahké nahliadnuť, že konektor $u_{i+1}\#\bar{u_{i+1}}$ sa nachádza v $S$ medzi $S_{u_i,u_{i+1}}\#S_{u_{i+1},u_{i+2}}$ a z toho vyplýva že aj konektor z $C_{i}$ pre $i = 2,3,\ldots n-1$ je podslovom $S$.
\end{itemize}
Dĺžka štandardného nadslova pre vrchol $v$ s $k = d_{\textrm{out}}(v)$ výstupnými hranami je $2k+2$\footnote{Index pri $w$ v štandardnom nadslove beží od $i$ po $k-1$ a potom od $0$ po $i$, čo je dokopy $ (k-1-i+1) + (i-0+1) = k+1 $.} Dĺžka $S$ je
\begin{eqnarray*}
|S| &=& \sum_{i=1}^{n-1} (2d_{\textrm{out}} + 2) + (n-2) +4 \\
&=& 2m + 2(n-1) + (n+2)\\
&=& 2m + 3n 
\end{eqnarray*}

\paragraph{nadslovo $\Rightarrow$ cesta} V $L$ je $2m+n$ reťazcov a každý z nich má dĺžku $3$. Keď ich poskladáme do nadslova môžu sa prekrývať najviac o $2$ znaky, inak by boli zhodné.
Nech sa prekrývajú o dva potom dĺžka nadreťazca je aspoň $2m+n+2$. Ale konektory a terminály sa nemôžu prekrývať o 2, pretože nemajú na kraji mrežu. Teda sa môžu najviac o jeden.
V množine $A_v$  sú možné prekryvy iba v týchto prípadoch:
\begin{enumerate}
 \item $w_i\bar{v}w_{i+1}$ a $\bar{v}w_{i+1}\bar{v}$
 \item $\bar{v}w_{i}\bar{v}$ a $w_i\bar{v}w_{i+1}$ 
\end{enumerate}
Konektory sa môžu prekrývať iba o jeden znak a to v týchto prípadoch:
\begin{enumerate}
 \item $v\#\bar{v}$ a $\bar{v}w_i\bar{v}$
 \item $w_i\bar{v}w_{i+1}$ a $w_{i+1}\#\bar{w_{i+1}}$
\end{enumerate}
Minimálna dĺžka nadslova bezohľadu na graf je $2m + 2n + \underbrace{2(n-2)}_{konektory} + 2 = 2m+3n$. Ale my máme slovo dĺžky $2m+3n$ a teda musí mať tvar
\[ \cent\#\ldots\#\underbrace{\ldots}_{S_{v,w_i}}\#\underbrace{\ldots}_{S_{w_i,z}}\#\ldots\#\$ \]
Medzi mrežami musí byť $S_{v,w_i}$ pretože za mrežou je bezprostredne $\bar{v}$ a dvojica $\#\bar{v}$ sa už nemôže nikde inde vyskytovať, lebo konektor tohto typu je len jeden. $S_{v,w_i}$ musí byť v kuse, pretože inak by narástla dĺžka slova. Analogicky za blokom $S_{v,w_i}$ musí nasledovať blok $S_{w_i,z}$. Nadslovo $S_{v,w_i}$ reprezentuje hranu $(v,w_i) \in E$ a celý reťazec reprezentuje hamiltonovskú cestu v grafe.

\subsection{Aproximácie}
\paragraph{Greedy algoritmus}
\begin{enumerate}
 \item nájdi najväčší prekryv medzi dvoma slovami, t.j. najdlhšiu $\alpha$ takú, že $S_i = \alpha\beta$ a $ S_j = \gamma\alpha$.
 \item spoj $S_i$ a $S_j$ do $\gamma\alpha\beta$
 \item opakuj 1. krok, kým nezostane iba jedno slovo
\end{enumerate}
\paragraph{hľadanie $\alpha$} Vybudujme sufixový strom pre $S_j$. Hľadáme najdlhší prefix na ceste $S_i$ v sufixovom strome, kde končí najdlhší sufix $S_j$.(najnižší taký vrchol). To vieme nájsť v $O(n)$. 

Aby sme to však nemuseli robiť pre každé $i$ a $j$ zvlášť, majme zovšeobecnený sufixový strom pre $S_1,S_2,\ldots S_k$. Pre dané $S_i$ hľadáme najhlbší prefix $S_i$, ktorý sufixom nejakého $S_j$($ j \neq i$). Hľadáme teda najdlhší dolár, ktorý nepatrí reťazcu $S_i$. Celú iteráciu vieme urobiť v $O(|S_i|)$ a celý algoritmus v čase $O(n)$. 

\paragraph{dolný odhad faktoru} Dolný odhad pre aproximačný faktor predchádzajúceho algoritmu je 2. Nech $L_k = \{ c(ab)^k, (ba)^k, (ab)^kc\} $. Potom

\begin{center}
\begin{tabular}{|c|c|c|}
	\hline
	alg.	&nadslovo&dĺžka nadslova\\
	\hline
	greedy	&$c(ab)^kc(ba)^k$ & $4k+2$ \\
	\hline
	opt.	&$c(ab)^{k+1}c$ & $2k+4$ \\
	\hline
\end{tabular}
\end{center}

Aproximačný faktor $\frac{4k+2}{2k+4} \rightarrow 2 $ pre $ k  \rightarrow \infty $. Je otvorený problém, či je to vždy najviac $2$. Dá sa ukázať, že uvádzaný algoritmus má faktor 2 pri optimalizácii počtu ušetrených znakov $ (\sum |S_i|) - c $ a tiež faktor najviac 4 pri optimalizácii dĺžky najkratšieho nadslova.

\paragraph{Maximalizácia ušetrených znakov:}
Preformulujme úlohu tak, že maximalizujeme počet ušetrených znakov $c$, potom dĺžka nadslova bude $ (\sum |S_i|) - c $. V optimálnom prípade sa takáto dĺžka bude rovnať dĺžke najkratšieho
spoločného nadslova, inak by sme mohli ešte niečo ušetriť. Teraz môžme ukázať, že takáto preformulovaná úloha sa dá aproximovať faktorom 2 pomocou už spomenutého greedy algoritmu.

\subsection{TO DO}
Dokaz pre 4-apriximaciu usetrenych znakov.



