superstring.tex

\chapter{Hľadanie nadslova}

Problém, ktorý riešime v tejto práci sa dá rozdeliť na dve základné úrovne.
Prvou z nich je hľadanie $k$-nadslova vstupných slov, druhou je indexácia
čítaní pomocou $k$-nadslova.

V tejto kapitole sa pozrieme na prvú z týchto úrovní, pozrieme sa na zložitosť problému
a na spôsob, akým vieme $k$-nadslovo hľadať efektívne, pokiaľ sú splnené pre naše
použitie rozumné predpoklady.

Mohlo by sa zdať, že hľadanie $k$-nadslova je slabšou verziou problému hľadania
spoločného nadslova, keďže ľubovoľné nadslovo nejakej množiny reťazcov bude zároveň
$k$-nadslovom tejto množiny reťazcov a ľahko vidno, že naopak to neplatí.

Na druhú stranu, každé slovo dlhé $n > k$ vieme rozvinúť na $n - k + 1$ slov dlhých
presne $k$ tak, že hľadané nadslovo ostane presne to isté. V ďalšej časti si zhrnieme
a popíšeme zopár výsledkov o zložitosti problému najkratšieho $k$-nadslova.


%##################################################################################
\section{Zložitosť problému}
%##################################################################################

\begin{defn}
Pod pojmom \emph{rozhodovací problém $k$-nadslova} budeme rozumieť nasledovné:
Pre danú množinu slov $S$, v ktorej každé slovo má dĺžku presne $k$,
a dané $l$ zistiť, či existuje $k$-nadslovo množiny $S$ dlhé nanajvýš $l$.
\end{defn}

Najprv sa pozrieme na problém pre neobmedzenú abecedu. Keďže tento problém je
vo svojej podstate rovnaký ako rozhodovací problém nadslova s fixnou dĺžkou reťazcov, môžeme využiť mnohé výsledky
pre obyčajný problém nadslova: pre $k \leq 2$ je problém polynomiálne riešiteľný,
pre $k \ge 3$ je $\mathcal{NP}$-úplný pomocou redukcie z problému hamiltonovskej
kružnice v orientovanom grafe \cite{superstring}. Konštrukciu pre $k = 3$ si popíšeme.

Prvým krokom redukcie v článku Gallanta, Meiera a Storera je skonštruovať orientovaný
graf $G'$ s vopred určeným počiatočným aj koncovým vrcholom, v ktorom každý vrchol $V$
okrem koncového spĺňa $d_O(V) > 1$. Pre daný orientovaný graf $G$
skonštruujú nový graf rozdelením niektorého vrchola na počiatočný vrchol $s$ a
koncový vrchol $t$ tak, že počiatočný si zachová všetky vychádzajúce a koncový
všetky vchádzajúce hrany. Pre dodržanie veľkosti stupňa pridajú ešte tri vrcholy
$t', a, b$, pridajú hrany z každého vrchola do $t'$ a navyše hrany $(t, a), (t, b),
(a, b), (b, a), (a, t')$. Tento nový graf $G'$ obsahuje hamiltonovskú cestu práve vtedy,
keď graf $G$ obsahuje hamiltonovskú kružnicu.

Druhým krokom redukcie je skonštruovať z upraveného grafu množinu slov. Abecedu
týchto slov definujú ako $\Sigma = V \cup B \cup S$, kde $V$ sú vrcholy grafu označené
číslami od $1$ po $n$ ($1$ je počiatočný a $n$ koncový vrchol), $B = \{ \bar{v} | v \in V \}$
je množina označených vrcholov a $S = \{\#, \$, \% \}$.

Ďalej skonštruujú množinu slov prislúchajúcich hranám vrchola $v$ ako \\
$A_v = \{ \bar{v}w_i\bar{v} | w_i \in R_v\} \cup \{ w_i \bar{v} w_{i \oplus 1} | w_i \in R_v\}$,
kde $R_v$ je postupnosť hrán vychádzajúcich z $v$ a $\oplus$ je sčítanie modulo $d_O(v)$.
Nakoniec skonštruujú množiny $C = \{ \bar{v} \# v | v \in V\}$ a $T = \{ \% \# \bar{1}, \bar{n} \# \$\}$.
Nakoniec v článku dokážu, že graf $G'$ obsahuje hamiltonovskú cestu práve vtedy, keď
existuje nadslovo množiny slov $C \cup T \cup (\bigcup\limits_{v \in V} A_v)$.

Dôležitou vlastnosťou tejto konštrukcie je, že stačí, aby každý reťazec mal dĺžku $3$. Ďalšou dobrou
vlastnosťou je, že konštrukcia používa $(2n + 10)$-znakovú abecedu.

%--------------------------------------------------------------------------------
\subsection{Obmedzená veľkosť abecedy}
%--------------------------------------------------------------------------------

S obmedzenou veľkosťou abecedy $\Sigma$ je náročné hovoriť o zložitosti problému, keďže
slov dĺžky $k$ nad obmedzene veľkou abecedou je konečne veľa. Za dobrý odhad
zložitosti problému však považujeme také číslo $n$, že pomocou rozhodovacieho
problému $k$-nadslova vieme rozhodovať aj ľubovoľnú inštanciu problému
hamiltonovskej kružnice s nanajvýš $n$ vrcholmi.

Pri probléme s obmedzenou abecedou si teda vieme vystačiť s vhodným zakódovaním
ľubovoľnej abecedy $\Sigma_V$ do obmedzene veľkej abecedy $\Sigma_M$. Jediná vec, ktorú potrebujeme zaručiť
je, že v $k$-nadslove sa nebudú kódy jednotlivých znakov prekrývať. Inštanciu
problému s neobmedzenou abecedou potom vieme prekódovať do inštancie s obmedzenou
abecedou a z každého $k$-nadslovu nájdeného v inštancii s obmedzenou abecedou
vieme zrekonštruovať $k$-nadslovo pre pôvodnú inštanciu.

Pre jednoduchosť budeme uvažovať iba $k$ deliteľné tromi. Pre ostatné $k$ sa
potom dá použiť podobná konštrukcia z inštancie problému orietovanej hamiltonovskej cesty,
kde je graf ešte navyše bipartitný. Všetky kódovania budeme konštruovať tak, aby
každému znaku z pôvodnej abecedy zodpovedalo rovnako dlhé slovo z obmedzenej abecedy.

Ako prvý si rozoberieme prípad, kde $|\Sigma_M| = n \ge 3$. Bez ujmy na všeobecnosti,
nech $\Sigma = \{0, 1, \ldots, n-1, \$ \}$. Znaky v abecede $\Sigma_V$ si očíslujeme
číslami od $0$ po $|\Sigma_V| - 1$. Ako kód $i$-teho znaku použijeme reťazec
$x \$ $, kde $x$ je číslo $i$ zapísané v $(n-1)$-tkovej sústave, doplnené nulami tak,
aby malo dĺžku presne $\frac{k}{3} - 1$. Keďže sa každý znak končí zarážkou nepoužitou na
inom mieste v kóde, kódy jednotlivých znakov sa nemôžu prekrývať.

Pri uvedenom kódovaní má každý kód pôvodného znaku dĺžku presne $\frac{k}{3}$. Keďže
konštrukcia inštancie problému nadslova k inštancii problému orientovanej hamiltonovskej
kružnice používa iba slová dĺžky $3$, všetky slová, ktoré vygenerujeme v našom kódovaní,
budú mať dĺžku $k$. Keďže zakódovať vieme nanajvýš $(n-1)^{\frac{k}{3} - 1}$ rôznych
vrcholov, pre dané $k$ vieme problém orientovanej hamiltonovskej cesty s nanajvýš
$\frac{(n-1)^{\frac{k}{3}-1} - 10}{2}$ vrcholmi zredukovať na problém hľadania
najkratšieho $k$-nadslova reťazcov nad $n$-znakovou abecedou.

%###############################################################################
\section{Abstrakcia}
%###############################################################################

Po zdôvodnení a dokázaní zložitosti riešeného problému sa pozrieme na spôsob, akým ho budeme
riešiť. Ako prvé si objasníme abstrakciu problému, na ktorej riešenie postavíme.

Sadu vstupných slov si budeme reprezentovať ako mierne upravený ohodnotený de Bruijnov \cite{de_bruijn}
graf stupňa $k - 1$ nad abecedou $\Sigma$. Každej hrane symbolicky priradíme reťazec,
ktorého dĺžka bude vždy zároveň hodnotou hrany.
Naše riešenie, čiže nejaké spoločné $k$-nadslovo, budeme reprezentovať ako sled v tomto grafe.

\begin{figure}

\centerline{\includegraphics[width=0.5\textwidth]{images/graph-2-1-3.pdf}}

\caption[Príklad grafu]{Príklad $2$-grafu množiny $\{\texttt{ACG}, \texttt{CGA} \}$. \emph{Nutné} hrany sú vyznačené
červenou farbou, čierne hrany sú \emph{nepovinné}.}

\label{obr:graf}

\end{figure}

Vrcholmi grafu budú všetky $(k-1)$-tice znakov, ktoré sa vyskytujú v aspoň jednom slove. Hrany
v grafe pôjdu z každého vrchola do každého, vrátane slučiek. Tieto hrany si rozdelíme na dve
skupiny: \emph{nutné} a \emph{nepovinné}. Za \emph{nutnú} hranu označíme každú takú hranu
$e = ( (x_1 x_2 \ldots x_{k-1}), (y_1 y_2 \ldots y_{k-1}))$, pre ktorú platí $x_{i+1} = y_{i}$ pre
každé $i$ v rozsahu od $1$ po $k - 2$ a zároveň $k$-tica znakov $x_1 y_1 y_2 \ldots y_{k-1}$ sa
vyskytuje v aspoň jednom slove. Ostatné hrany budú \emph{nepovinné}.

Než si popíšeme, aké reťazce priradíme hranám, budeme potrebovať poriadne zadefinovať
ešte jeden pojem.

\begin{defn}
Nech $s_1$ a $s_2$ sú reťazce znakov nad abecedou $\Sigma$ a nech $z$ je najdlhší reťazec taký, že
$$\exists x, y \in \Sigma^*: s_1 = xz \wedge s_2 = zy \wedge |x| \ge 1 $$
Potom prekryvom reťazca $s_1$ s reťazcom $s_2$ označíme reťazec $z$ a dokončením $s_1$ v $s_2$ označíme
taký reťazec $y$, ktorý spĺňa $s_2 = zy$.
\end{defn}

Každej hrane z vrchola $S_1$ do vrchola $S_2$ priradíme dokončenie $S_1$ v
$S_2$. Pripomíname, že hodnotou tejto hrany bude dĺžka priradeného reťazca.
Takto skonštruovaný graf k množine vstupných slov $S$ budeme ďalej označovať ako
\textbf{\boldmath$k$-graf množiny \boldmath$S$}. Konkrétny príklad môžeme vidieť
v obr. \ref{obr:graf}.

Kvôli časti o implementácii si zadefinujeme ešte pojem \emph{nutného podgrafu}.
Pod pojmom \emph{nutný podgraf} $k$-grafu množiny $S$ budeme rozumieť faktorový
podgraf $k$-grafu množiny $S$ obsahujúci iba nutné hrany.

Môžeme si všimnúť, že reťazec priradený každej nutnej hrane bude mať vždy jeden
znak. Ďalším pozorovaním,
ktoré sa nám bude hodiť najmä pri implementácii je, že reťazec priradený každej
hrane vieme vypočítať iba z označení jej koncových vrcholov. Ďalej, každý vrchol
v nutnom podgrafe $k$-grafu množiny $S$ má vstupný aj výstupný vrchol zhora
ohraničený veľkosťou abecedy. Posledné dôležité
pozorovanie je, že každá hrana má kladnú cenu.

Slovo prislúchajúce sledu v $k$-grafe množiny $S$ získame ako zreťazenie $zr$, kde $z$ je
označenie prvého vrchola sledu a $r$ sú pospájané reťazce priradené hranám v takom
poradí, v akom sa tieto hrany nachádzajú v slede.

Formálnejšie zapísané, nech $slovo(V)$ označuje reťazec dĺžky $k-1$, označenie vrchola
$V$ a $slovo(e)$ označuje reťazec priradený hrane $e$. Potom $slovo(w)$, slovo
prislúchajúce sledu $w = V_1 e_1 V_2 e_2 \ldots e_{n-1} V_n$ skonštruujeme nasledovne: 
$$slovo(w) = slovo(V) \cdot slovo(e1) \cdot slovo(e2) \cdots slovo(e_{n-1}).$$
Pre prázdny sled $w$ definujeme $slovo(w) = \varepsilon$, čiže prázdne slovo.

Z tejto konštrukcie vidíme, že dĺžku slova priradeného neprázdnemu sledu vieme
vypočítať ako $k-1 + \sum \limits_{i=1}^{n-1} cena(e_i)$

Sled v $k$-grafe množiny $S$ budeme volať \emph{korektný}, ak obsahuje všetky nutné hrany.
Teraz si dokážeme, že slovo prislúchajúce korektnému sledu v $k$-grafe množiny $S$ je
$k$-nadslovom množiny $S$. K tomu budeme potrebovať ešte jednu pomocnú lemu.

\begin{lema}
\label{vertex_end_lemma}
    Nech $V_1 e_1 V_2 e_2 \ldots e_{n-1} V_n$ je neprázdny sled v $k$-grafe nejakej množiny $S$.
    Potom sa reťazec $r$ prislúchajúci tomuto sledu končí $(k-1)$-ticou znakov zhodnou
    s označením vrchola $V_n$.
\end{lema}

Keďže túto lemu je možné dokázať čisto technickou matematickou indukciou, dôkaz prenechávame
čitateľovi.

\iffalse
\begin{proof}
    $1^0:$ Ak $n$ je rovné $1$, sled obsahuje iba jeden vrchol. Podľa konštrukcie slova
           priradeného sledu bude toto slovo totožné s označením prvého a zároveň aj
           posledného vrchola v slede.

    $2^0:$ Nech $w_1 = V_1 e_1 \ldots V_{j-1}$ a $w_2 = V_1 e_1 \ldots V_j$. Podľa konštrukcie slova $slovo(w_2)$ platí
           $$ slovo(w_2) = slovo(V_1) \cdot slovo(e_1) \cdots slovo(e_{j-1}) = slovo(w_1) \cdot slovo(e_{j-1})$$
           Ďalej potrebujeme rozobrať dva prípady:
           \begin{enumerate}
            \item Ak je hrana $e_{j-1}$ \emph{nutná}, tak platí
                  $$ \exists x_1, x_2 \ldots x_k \in \{A, C, G, T \}: V_{j-1} = (x_1  \ldots  x_{k-1}) \wedge V_j = (x_2 \ldots  x_k)$$
                  a podľa konštrukcie hrany a priradenia jej reťazca, $slovo(e_{j-1}) = x_n$.
                  Z indukčného predpokladu vyplýva, že $\exists q \in \{ A, C, G, T\}^*: slovo(w_1) = q \cdot x_1 \cdot x_2 \cdots x_{k-1}$. Keď to
                  spojíme dohromady, dostaneme
                  $$ slovo(w_2) = slovo(w_1) \cdot slovo(e_{j - 1}) = q \cdot x_1 \cdots x_{k - 1} \cdot slovo(e_{j - 1}) = $$
                  $$ = q \cdot x_1 \cdots x_{k - 1} \cdot x_k = q' \cdot x_2 \cdots x_k = q' \cdot slovo(V_j),$$
                  kde $q' = qx_1$.

            \item Ak je hrana $e_{j - 1}$ \emph{nepovinná}, tak z konštrukcie \emph{nepovinnej} hrany a jej priradeného reťazca
                  vyplýva:
                  $$ \exists x, y, z \in \{ A, C, G, T\}^* : slovo(V_{j - 1}) = xz \wedge slovo(V_{j}) = zy \wedge slovo(e_{j - 1}) = y.$$
                  Opäť z indukčného predpokladu vyplýva $ \exists q \in \{A, C, G, T\}^*: slovo(w_1) = q \cdot slovo(V_{j-1}) = q \cdot xz$.
                  Keď to poskladáme dohromady, dostaneme
                  $$ slovo(w_2) = slovo(w_1) \cdot slovo(e_{j - 1}) = q \cdot x \cdot z \cdot slovo(e_{j - 1}) = q \cdot x \cdot z \cdot y = $$
                  $$ = q \cdot x \cdot slovo(V_j).\qedhere$$

           \end{enumerate}
\end{proof}
\fi

\begin{veta}
    Nech $W$ je korektný sled v $k$-grafe množiny $S$. Potom $slovo(W)$ je $k$-nadslovom množiny slov $S$.
\end{veta}

\begin{proof}
Vezmime si ľubovoľné slovo $w$ také, že $|w| = k$ a $w$ je podslovom nejakého slova z $S$. Nech $x_1, x_2, \cdots x_k$
sú znaky tohto slova v poradí. Potom sa v grafe vyskytujú vrcholy $V_1 = (x_1, x_2, \cdots, x_{k-1})$ a $V_2 = (x_2, x_3, \cdots x_k)$ také,
že z $V_1$ ide hrana $e$ do $V_2$ a $e$ je nutná. Z toho vyplýva, že $W$ = $U_1 V_1 e V_2 U_2$, kde $U_1, U_2$ sú nejaké časti sledu.
Z predošlej lemy potom vyplýva, že existuje $q \in \Sigma^*$ také, že $slovo(U_1 V_1) =  q \cdot x_1 \cdots x_{k - 1}$, a teda
$$slovo(W) = slovo(U_1 V_1 e V_2 U_2) = q \cdot x_1 \cdots x_{k - 1} \cdot slovo(e) \cdot slovo (V_2 U_2) = q \cdot w \cdot slovo(V_2 U_2).\qedhere$$
\end{proof}

Pre úplnosť uvedieme ešte jednu dobrú vlastnosť $k$-grafu množiny $S$, ktorá neskôr uľahčí
konštrukciu $k$-nadslova.

\begin{lema}
\label{shortest_edge_lemma}
    Nech $U$ a $V$ sú vrcholmi $k$-grafu množiny $S$. Potom najlacnejší sled začínajúci v $U$
    a končiaci vo $V$ obsahujúci aspoň jednu hranu, má rovnakú cenu, ako hrana $e$ z vrchola $U$ do $V$.
\end{lema}

\begin{proof}
    Sporom. Nech $w := U e_1 U_1 e_2 \cdots e_n V$ je kratšia cesta. Z lemy \ref{vertex_end_lemma} vieme,
    že aj $slovo(U e V)$ aj $slovo(w)$ sa končia označením vrchola $V$, zároveň, keďže $w$ má
    menšiu cenu ako $e$, platí $|slovo(w)| < |slovo(U e V)|$. To je ale v spore s tým, že prekryv
    $U$ s $V$ je najdlhší možný, $slovo(w)$ nám dáva návod, ako zostrojiť kratší.
\end{proof}

%--------------------------------------------------------------------------------
\subsection{Vlastnosti abstrakcie}
%--------------------------------------------------------------------------------

Zatiaľ čo každému korektnému sledu v abstrakcii prislúcha práve jedno $k$-nadslovo, nie
každé $k$-nadslovo vieme reprezentovať ako sled v našom grafe.

Vezmime si ako vstupné slová \verb_ACG_ a \verb_CGA_ a $k$ rovné trom. Graf prislúchajúci
takémuto vstupu je znázornený na obrázku \ref{obr:graf}.
V grafe máme tri vrcholy zodpovedajúce dvojiciam \verb_(AC)_, \verb_(CG)_ a
\verb_(GA)_. Hrany aj s označením, ktoré budeme používať ďalej: 
\begin{itemize}
    \item \emph{nutná} hrana $e_1$ z vrchola \verb_(AC)_ do \verb_(CG)_ s priradeným reťazcom \verb_G_,
    \item \emph{nutná} hrana $e_2$ z vrchola \verb_(CG)_ do \verb_(GA)_ s priradeným reťazcom \verb_A_,
    \item \emph{nepovinná} hrana $e_3$ z vrchola \verb_(AC)_ do \verb_(GA)_ s reťazcom \verb_GA_,
    \item \emph{nepovinná} hrana $e_4$ z vrchola \verb_(CG)_ do \verb_(AC)_ s reťazcom \verb_AC_,
    \item \emph{nepovinná} hrana $e_5$ z vrchola \verb_(GA)_ do \verb_(AC)_ s reťazcom \verb_C_,
    \item \emph{nepovinná} hrana $e_6$ z vrchola \verb_(GA)_ do \verb_(CG)_ s reťazcom \verb_CG_.
    \item \emph{nepovinná} hrana $e_7$ z vrchola \verb_(AC)_ do \verb_(AC)_ s reťazcom \verb_AC_,
    \item \emph{nepovinná} hrana $e_8$ z vrchola \verb_(CG)_ do \verb_(CG)_ s reťazcom \verb_CG_,
    \item \emph{nepovinná} hrana $e_9$ z vrchola \verb_(GA)_ do \verb_(GA)_ s reťazcom \verb_GA_.
\end{itemize}

Celkom ľahko vidíme, že najkratšie možné $k$-nadslovo musí mať aspoň štyri znaky. Vhodné $k$-nadslovo takejto
dĺžky naozaj existuje, napríklad \verb_ACGA_. V našom grafe ho vieme reprezentovať ako sled:
$$\texttt{(AC)} e_1 \texttt{(CG)} e_2 \texttt{(GA)}$$

Ak sa ale pozrieme napríklad na slovo \verb_TTACGTTTCGATT_, neexistuje žiaden sled, ktorému prislúcha toto $k$-nadslovo,
keďže žiaden vrchol ani hrana neobsahujú znak \verb_T_. Ľahko ale vidíme, že toto slovo vieme skrátiť
vynechaním znakov \verb_T_, ktoré sa nemôžu objaviť v žiadnom $k$-nadslove konštruovanom k sledu,
na stále vyhovujúce nadslovo \verb_ACGCGA_. Toto slovo vieme reprezentovať ako sled:
$$\texttt{(AC)} e_1 \texttt{(CG)} e_8 \texttt{(CG)} e_2 \texttt{(GA)}$$

Zdá sa teda, že ak nejakú časť $k$-nadslova nevieme reprezentovať ako časť sledu v $k$-grafe, môžeme ju
nejakým spôsobom vynechať. Túto vlastnosť si ďalej zhrnieme. Predtým si zadefinujeme konštrukciu sledu k
ľubovoľnému $k$-nadslovu.

\begin{defn}
    Nech $S$ je množina slov nad abecedou $\Sigma$, $s = x_1 x_2 \cdots x_n$ je nejakým slovom nad abecedou $\Sigma$,
    nech $G$ je $k$-grafom množiny $S$, nech \\
    $Z = \{ i \in \{1 \ldots n - k + 2 \} | (x_i x_{i+1} \cdots x_{i+k-2}) \in V(G) \}$, čiže $Z$ je množina takých indexov v $s$, že
    $(k-1)$-tica písmen začínajúca na tejto pozícii označuje vrchol v grafe $G$
    a nech $v_i$ je $i$-ty najmenší prvok množiny $Z$. Potom pre neprázdnu množinu $Z$ určíme \textit{$k$-sled slova $s$ pri množine $S$} ako
    $$sled_{k,S}(s) = V_1 e_1 V_2 e_2 \cdots e_{p-1} V_p,$$
    kde $V_i = (x_{v_i} x_{v_i + 1} \cdots x_{v_i + k - 2})$ a $e_i$ je hrana medzi $V_i$ a $V_{i+1}$. Pre prázdnu
    množinu $Z$ určíme $sled_{k, S}(s)$ ako prázdny sled.
\end{defn}

Na túto konštrukciu sa vieme pozerať aj tak, že zo slova $s$ vytiahne tie časti -- vrcholy, ktoré vieme reprezentovať
v našom grafe $G$ a pospája ich hranami. To, že táto konštrukcia zachytáva všetky pre nás dôležité časti slova
a zároveň ho nenafúkne, si ďalej dokážeme.

\begin{veta}
    Nech $s = x_1 x_2 \cdots x_n$ je $k$-nadslovom množiny $S$. Potom aj $slovo(sled_{k,S}(s))$ je
    $k$-nadslovom množiny $S$.
\end{veta}

\begin{proof}
    Nech $q = a_1 a_2 \cdots a_k$ je ľubovoľná $k$-tica písmen vyskytujúca sa v nejakom slove množiny $S$.
    Keďže $s$ je $k$-nadslovom množiny $S$, platí nasledovné: 
    $$\exists i : a_1 = x_i \wedge a_2 = x_{i+1} \wedge \ldots \wedge a_k = x_{i+k-1}$$
    Zároveň z konštrukcie $k$-grafu množiny $S$ vyplýva, že obsahuje vrcholy \\
    $U_1 := (x_i x_{i+1} \cdots x_{i+k-2})$
    a $U_2 := x_{i+1} x_{i+2} \cdots x_{i+k-1}$. Tým pádom množina $Z$ z konštrukcie sledu obsahuje aj $x_i$, aj
    $x_{i+1}$, čiže $sled_{k,S}(s)$ obsahuje podsled $U_1 e U_2$ a teda $slovo (sled_{k,S}(s))$ obsahuje $q$.
\end{proof}

\begin{veta}
    Nech $S$ je množina slov nad abecedou $\Sigma$, $n$ je prirodzené a $k \ge 2$ je celé číslo, nech $s = a_1 a_2 \cdots a_n$ je
    nejakým slovom nad $\Sigma$. Potom $|slovo(sled_{k,S}(s))| \leq |s|.$
\end{veta}

\begin{proof}
    Nech $G$ je $k$-graf množiny $S$. Dokážeme matematickou indukciou na $n$, dĺžku slova $s$.

    $1^0:$  $n < k-1$. Tento prípad pokrýva napríklad prázdne slová $s$, čiže je vhodný ako báza indukcie.
            
            V $s$ sa nenachádza žiadna $(k-1)$-tica písmen, čiže množina $Z$ z konštrukcie $k$-sledu bude prázdna, teda aj $sled_{k,S}(s)$ bude
            prázdny, čiže $slovo (sled_{k,S}(s)) = \varepsilon, |\varepsilon| = 0 \leq n$.

    $2^0:$  Položíme $s' := a_1 a_2 \cdots a_{n-1}$, čiže $s$ skrátený o posledný znak. 
            V indukčnom kroku nás zaujímajú iba slová $s$ dĺžky aspoň $k - 1$. Rozoberieme tri základné možnosti:
            \begin{itemize}
                \item $(a_{n-k+2} a_{n-k+3} \cdots a_n) \notin V(G).$ Množina $Z$ z konštrukcie sledu bude rovnaká
                      pre $s$ aj $s'$, čiže $slovo(sled_{k,S}(s)) = slovo (sled_{k,S}(s'))$ a teda \\ 
                      $|slovo(sled_{k,S}(s))| = |slovo(sled_{k,S}(s'))| \leq |s'| < |s|$, kde prvá nerovnosť vyplýva z indukčného predpokladu.
                \item $(a_{n-k+2} a_{n-k+3} \cdots a_n) \in V(G)$ a $sled_{k,S}(s')$ je prázdny. Potom množina $Z$ z konštrukcie
                      sledu k $s$ bude obsahovať jeden prvok, čiže $sled_{k,S}(s)$ obsahuje iba jeden vrchol. Preto $|slovo(sled_{k,S}(s))| = k - 1 \leq |s|$.
                \item $V_0 := (a_{n-k+2} a_{n-k+3} \cdots a_n) \in V(G)$ a $sled_{k,S}(s')$ je neprázdny. Položíme \\
                      $j := max \{ i \in \{1 \ldots n - k + 1 \} | (x_i x_{i+1} \cdots x_{i+k-2}) \in V(G) \}$,
                      čiže začiatok poslednej $(k-1)$-tice zodpovedajúcej nejakému vrchola v $G$ a $s'' := a_1 a_2 \cdots a_{j+k-2}$,
                      čiže $s'$ skrátené po koniec poslednej $(k-1)$-tice zodpovedajúcej nejakému vrchola v $G$. Slová $s'$ a $s''$ majú
                      rovnakú množinu $Z$ z konštrukcie sledu, čiže majú priradený rovnaký sled a teda $slovo(sled_{k,S}(s')) = slovo(sled_{k,S}(s''))$.

                      Položme $sled_{k,S}(s'') = V_1 e_1 \cdots V_p$. Sled k slovu $s$ obsahuje práve jeden vrchol navyše, čiže $sled_{k,S}(s) = V_1 e_1 \cdots V_p e_p V_0$,
                      kde $e_p$ je hrana z $V_p$ do $V_0$. Z konštrukcie slova k sledu vieme nasledovné: \\
                      $$slovo(sled_{k,S}(s)) = slovo(V_1) slovo(e_1) slovo(e_2) \cdots slovo(e_p) = $$
                      $$ = slovo(sled_{k,S}(s'')) \cdot slovo(e_p).$$
                        Podľa lemy \ref{vertex_end_lemma} sa $slovo(sled_{k,S}(s''))$ končí označením vrchola $V_q$, čiže rovnako, ako $s''$,
                      podobne sa $slovo(sled_{k,S}(s))$ končí tou istou $(k-1)$-ticou ako $s$, z indukčného predpokladu vyplýva, že $|slovo(sled_{k,S}(s''))| \leq |s''|$.
                      Ak by teda platilo $|slovo(sled_{k,S}(s))| > |s|$, bolo by dokončenie $s$ v $s''$ kratšie, než dokončenie $V_0$ vo $V_q$,
                      čo je v spore s tým, že prekryv $V_0$ s $V_q$ je definovaný ako najdlhší možný, podobne ako v dôkaze lemy \ref{shortest_edge_lemma}.
                      Aj v tomto prípade teda platí indukčný krok. \qedhere
            \end{itemize}
    
\end{proof}

\begin{dosl}
    Nejaké najkratšie $k$-nadslovo množiny $S$ zodpovedá nejakému najlacnejšiemu \emph{korektnému} sledu v $k$-grafe množiny $S$.
\end{dosl}

%##################################################################################
\section{Algoritmus na hľadanie najkratšieho $k$-nadslova}
%##################################################################################

V predošlej časti sme si dokázali, že pre nájdenie najkratšieho $k$-nadslova množiny slov $S$
nám stačí nájsť najlacnejší korektný sled v $k$-grafe množiny $S$, čiže sled, ktorý obsahuje
všetky \emph{nutné} hrany grafu. Ide o pomerne známy \textbf{problém vidieckeho poštára} z grafovej teórie,
ktorý je vo všeobecnom prípade $\mathcal{NP}$-ťažký \cite{ruralpostman}.

Ukazuje sa však, že pokiaľ podgraf $k$-grafu množiny $S$ obsahujúci iba \emph{nutné} hrany je súvislý,
tento problém je polynomiálne riešiteľný a riešenie je takmer zhodné s riešením \textbf{problému čínskeho
poštára} na orientovaných grafoch \cite{rural_postman_connected}. Keďže zamýšľané použitie $k$-nadslova je na reprezentáciu sekvenčných čítaní, ktoré sú
krátkymi podreťazcami celého genómu s vysokou mierou pokrytia, je pomerne pravdepodobné, že nutné hrany
$k$-grafu týchto čítaní budú tvoriť stále súvislý graf, prípadne že budú obsahovať iba málo komponentov.
Najprv sa teda pozrieme, ako hľadať $k$-nadslovo v súvislom $k$-grafe.

%--------------------------------------------------------------------------------
\subsection{Súvislý graf}
%--------------------------------------------------------------------------------

Problém čínskeho poštára \cite{chinesepostman} sa zaoberá hľadaním najlacnejšieho sledu v grafe takého, že
každou hranou prejde aspoň raz.

Základnou myšlienkou riešenia problému čínskeho poštára je pridať hrany s čo najmenším súčtom do grafu
tak, aby obsahoval Eulerovský ťah \cite{chinesepostman}. Tento prístup funguje preto, že každý sled priamo
zodpovedá Eulerovskému ťahu pre nejaké doplnenie hrán do grafu.

Súvislý orientovaný graf obsahuje Eulerovskú kružnicu práve vtedy, keď vstupný stupeň $d_I$ je rovný
výstupnému stupňu $d_O$ v každom vrchole, Eulerovský ťah existuje aj v prípade, keď sa v najviac
dvoch vrcholoch vstupný a výstupný stupeň líšia o jedna. Ak teda $k$-graf množiny $S$ má túto
vlastnosť, nájdenie korektného sled je už len záležitosťou nájdenia Eulerovského ťahu.

Pokiaľ nutný podgraf $k$-graf množiny $S$ túto vlastnosť nemá, potrebujeme čo najlacnejšie pridať hrany z vrcholov s 
$d_O < d_I$ do vrcholov s $d_I < d_O$, pričom využívať môžeme aj nepovinné hrany.
Z lemy \ref{shortest_edge_lemma} vyplýva, že najlacnejšia cesta medzi dvomi vrcholmi je hrana medzi
nimi, čiže zaujímať nás budú iba hrany medzi vrcholmi. Z toho vyplýva aj konštrukcia nasledovného grafu,
ktorého schematické znázornenie uvádzame v obr. \ref{obr:toky}.

\begin{defn}
    Nech $G$ je $k$-graf množiny $S$ a $G'$ je jeho nutný podgraf. Tokovým grafom grafu $G$
    označíme graf $H$, ktorého množinu vrcholov skonštruujeme nasledovne:
    $V(G') = \{s, t\} \cup V_h \cup V_p$, kde $V_h$ (hladné) je množina $\{ v \in V(G) | d_O^{G'}(v) > delta_I^{G'}(v) \}$
    a $V_p$ (presýtené) je množina $\{ v \in V(G) | d_I^{G'}(v) > delta_O^{G'}(v)\}$. Vrcholy množiny $V_h$
    budeme volať hladné, vrcholy množiny $V_p$ presýtené.
    Hrany grafu $H$ budú troch typov:
    \begin{enumerate}
        \item Tie hrany z grafu $G$, ktoré idú z presýteného vrchola do hladného s cenou rovnakou ako v $G$ a kapacitou $\infty$,
        \item Hrany od $s$ do každého vrchola vo $V_p$ s cenou $0$. Kapacitu takéhoto typu hrany do vrchola $U$ určíme ako $d_I^{G'}(U) - d_O^{G'}(U)$,
        \item Hrany od každého vrchola z $V_h$ do $t$ s cenou $0$. Kapacitu takéhoto typu hrany z vrchola $U$ určíme ako $d_O^{G'}(U) - d_I^{G'}(U)$.
    \end{enumerate}
    Žiadne iné hrany v grafe $H$ nebudú.
\end{defn}

Nájdenie najlacnejšieho maximálneho toku v tokovom grafe $k$-grafu bude zodpovedať
najlacnejšiemu možnému pridaniu hrán do nutného podgrafu $k$-grafu tak, aby v ňom existovala Eulerovská
kružnica. Jednoducho pre každý nasýtený vrchol $V$ a hladný vrchol $U$ pridáme $x$ hrán z $V$ do $U$,
kde $x$ je veľkosť toku tečúca z vrchola $V$ do $U$.

\begin{figure}

\centerline{\includegraphics[width=0.6\textwidth]{images/toky-2.pdf}}

\caption[Ukážka tokových grafov]{Ukážka tokových grafov. Naľavo je znázornený základný tokový graf, napravo je znázornený
tokový graf s obmedzením maximálneho toku.}

\label{obr:toky}

\end{figure}


Keďže náš korektný sled nemusí začínať aj končiť v tom istom vrchole, potrebujeme
nájsť v skutočnosti najlacnejší tok, ktorý je o $1$ menší než maximálny a pridať hrany podľa neho.
Takýto tok môžeme nájsť napríklad pomocou algoritmu Edmondsa a Karpa \cite{mincost_maxflow} v
čase $O(n^3)$, kde $n$ je počet vrcholov v tokovom grafe nášho $k$-grafu, prípadne pomocou akéhokoľvek potenciálne rýchlejšieho
algoritmu na dve simulácie, kde v prvej zistíme hodnotu maximálneho toku a v druhej vhodným pridaním jedného vrchola vynútime
obmedzenie najväčšieho toku na požadovanú hodnotu (obr. \ref{obr:toky}).

Ako posledné nám teda stačí nájsť Eulerovský ťah v takto upravenom grafe a zrekonštruovať z neho
nadslovo. Týmto sme si popísali polynomiálny algoritmus na hľadanie $k$-nadslova, pokiaľ je
nutný podgraf $k$-grafu súvislý. Pre rekapituláciu si celý algoritmus uvedieme v dôkaze nasledujúcej
vety.

\begin{veta}
    Nech $S$ je množina slov dlhých aspoň $k$ nad abecedou $\Sigma$. Potom ak je nutný podgraf $k$-grafu množiny $S$
    súvislý, existuje polynomiálny algoritmus na hľadanie $k$-nadslova.
\end{veta}

\begin{proof}
    Uvedieme si algoritmus, ktorý $k$-nadslovo nájde. Ku každému kroku uvedieme aj časovú zložitosť od počtu slov v
    množine $S$, pre jednoduchosť za predpokladu, že každý reťazec má rozumne malú fixnú dĺžku.
    \begin{enumerate}
        \item Zostav nutný podgraf $k$-grafu zo vstupných slov a prečísluj vrcholy do intervalu $\left[0, pocet\right)$. $O(nk)$
        \item Vyrieš problém najlacnejšieho maximálneho toku na tokovom grafe. $O(n^3)$
        \item Pridaj hrany do grafu podľa výsledného toku. $O(n^2)$
        \item Nájdi Eulerovský ťah. $O(n)$
        \item Transformuj Eulerovský ťah na $k$-nadslovo. $O(nk)$ \qedhere
    \end{enumerate}
\end{proof}

Poslednou vecou, ktorou sa budeme zaoberať v súvislom prípade, je časová zložitosť. Všetky časti
algoritmu sa vykonávaju v čase lineárne závislom od veľkosti vstupu, okrem druhého a tretieho bodu.
V týchto bodoch je pomerne nepravdepodobné, že existuje riešenie rýchlejšie, než kvadratické. To je
spôsobené tým, že v najhoršom prípade môžu takmer všetky vrcholy grafu mať $d_I$ rôzne od $d_O$
a algoritmus, ktorý nájde najlepšie priradenie, sa potrebuje pozrieť na každú hranu.

Keďže hľadanie
$k$-nadslova chceme využiť do dátovej štruktúry schopnej reprezentovať milióny až stovky miliónov
genetických čítaní, chceli by sme nájsť nejaký spôsob, ako v lineárnom čase nájsť aspoň nejaké rozumné
pospájanie týchto vrcholov. V našom navrhovanom riešení jednoducho vyskúšame pevne stanovený počet
náhodných priradení a vyberieme z nich to najlacnejšie.

%--------------------------------------------------------------------------------
\subsection{Nesúvislý graf}
%--------------------------------------------------------------------------------

Už na začiatku sme si dokázali, že hľadanie $k$-nadslova je v istom zmysle ťažký problém. Keďže
sme si popísali a zdôvodnili polynomiálny algoritmus, ktorý vie nájsť $k$-nadslovo pre súvislý
nutný podgraf $k$-grafu vstupnej množiny, je pomerne pravdepodobné, že v našej špeciálnej
triede grafov neexistuje polynomiálne riešenie problému vidieckeho poštára.

Naše riešenie v nesúvislom prípade teda bude vyzerať úplne rovnako, v predošlom
riešení pozmeníme len posledný krok, hľadanie Eulerovského ťahu. Keďže taký v našom grafe
ani po pridaní hrán nemusí existovať, jednoducho nájdeme Eulerovský ťah v každom komponente
a výsledné slová nadpojíme na seba. Na toto sa môžeme pozerať aj tak, že si medzi niektoré
vrcholy v rôznych komponentoch pridáme hranu.

Ako sme spomínali vyššie, z povahy dát, pre ktoré hľadáme $k$-nadslovo,
je celkom pravdepodobné, že náš nutný podgraf bude súvislý, prípadne že bude mať iba málo
komponentov. Zároveň, v našom riešení pridáme nanajvýš $c - 1$ hrán navyše oproti
optimálnemu riešeniu. Ďalej vieme, že sme do grafu pridávali hrany najlacnejším spôsobom
tak, aby v každom vrchole platilo $d_I = d_I$. Keďže najväčšia možná hodnota
hrany je $k-1$, znamená to, že riešenie, ktoré takto nájdeme, bude najviac o $(k - 1)(c - 1)$ drahšie
ako optimálne, čiže takto nájdené $k$-nadslovo bude nanajvýš o toľko dlhšie od najkratšieho možného.