zaver.tex

\chapter*{Záver}
\addcontentsline{toc}{chapter}{Záver}

V tejto práci sme sa zaoberali indexáciou potenciálne veľkej sady
čítaní tak, aby bolo možné vyhodnocovať dotazy na podreťazce dĺžky presne $k$.
Základným prístupom k problému bolo nájdenie $k$-nadslova
k čítaniam a vytvorenie pomocných polí a štruktúr, aby sme vedeli
odpovedať na dotazy o pôvodných čítaniach.

Popísali sme si spôsob, ako nájsť zaručene najkratšie $k$-nadslovo
v polynomiálnom čase, pokiaľ je nutný podgraf $k$-grafu čítaní
súvislý. Ďalej sme si popísali spôsob, ako vieme hľadať $k$-nadslovo
aj v nesúvislom $k$-grafe, pričom toto $k$-nadslovo bude dlhšie
od najkratšieho možného o najviac $(k-1)$-násobok počtu komponentov.
Taktiež sme si popísali, ako vieme s využitím náhody nájsť nejaké
o málo dlhšie nadslovo v čase lineárne závislom od veľkosti $k$-grafu.

Pri indexácii sme si popísali tri základné typy dotazov, na ktoré vieme
s využitím $k$-nadslova odpovedať.
Podobne ako spomenuté dotazy vieme riešiť aj zvyšné dotazy spomenuté v
článku N. Philippe a kol. \cite{gk_arrays}, spomenuté v prvej kapitole
tejto práce:
\begin{enumerate}
    \item Ktoré čítania obsahujú daný podreťazec $f$? \\
          Túto otázku sme riešili priamo v práci v sekcii \ref{sekcia:index_ktore}.
    \item Koľko čítaní obsahuje daný podreťazec $f$? \\
          Túto otázku vieme riešiť podobne, ako počet výskytov podreťazca
          v čítaniach, stačí odlišne vypočítať pole počtov výskytov.
    \item Na ktorých pozíciach v čítaniach sa nachádza daný podreťazec $f$? \\
          Táto otázka sa dá zodpovedať pomocou rovnakých štruktúr, ako prvá.
          Pri počítaní si nebudeme ukladať iba, ktoré čítanie sme práve našli,
          uložíme si aj pozíciu v ňom.
    \item Koľkokrát sa dohromady vyskytuje daný podreťazec $f$ v čítaniach? \\
          Túto otázku sme riešili piamo v práci v sekcii \ref{sekcia:index_pocet}.
\end{enumerate}

Zvyšné dotazy sú len modifikáciou prvých štyroch, keď nás zaujímajú iba čítania,
ktoré daný podreťazec obsahujú iba raz. Takéto dotazy vieme spracovať s pomocou
malých prispôsobení navrhovaných dátových štruktúr.

Testovanie našej štruktúry ukázalo, že naša štruktúra je pre
väčšie $k$ efektívnejšia než CR-index \cite{cr_index}, zatiaľ čo pre menšie $k$
je od neho horšia. Na dátach pochádzajúcich zo sekvenovania s väčšou chybovosťou naša štruktúra síce zaberá
o niečo viac pamäte, ale dotazy vie spracovávať rýchlejšie.

V tejto práci sme neriešili chyby v čítaniach, keďže vieme odhadnúť, že každá
chyba v dátach môže $k$-nadslovo predĺžiť najviac o $2*k - 1$. Keďže je však
naša štruktúra efektívnejšia pre väčšie $k$, riešenie chýb môže patriť
k nevyhnutným krokom k použiteľnosti našej štruktúry pre relatívne veľké hodnoty $k$.

Na druhú stranu, s riešením chýb podobným ako v CR-indexe prichádzajú aj skryté úskalia. Jedným z nich
je nutnosť pri každom dotaze na podreťazec $r$ spracovať viacero reťazcov,
ktoré mohli vzniknúť ako oprava nejakého čítania, ktoré pôvodne $r$ obsahovalo.
Druhým z nich je odpovedanie na otázky o počte výskytov. Keďže niektoré $k$-tice
sú uložené v pozmenenej podobe, je nutné aj pri počítaní overovať jednotlivé
čítania.

Malým problémom, ktorý sme nepreskúmali je spôsob, akým sa dá vysporiadať sa
s dotazmi na podreťazce kratšie ako $k$. Keďže jediný problém spôsobujú začiatky
čítaní, jedno možné riešenie by mohlo využívať nejako vhodne reprezentované
pozície, na ktorých sa nachádza prvá $k$-tica z nejakého čítania.

Ďalším problémom do budúcnosti je otázka, či neexistuje ešte iný spôsob, ako
sformulovanť nadslovo, s pomocou ktorého by sa dali implementovať
ešte efektívnejšie štruktúry. Jedna možná formulácia je nadslovo so skóre,
v ktorom si môžeme dovoliť rozdeliť čítanie na dve časti za cenu nejakého
záporného skóre, do ktorého sa premietne nutnosť nejakým spôsobom uložiť
informáciu o tomto rozdelení.