biolog.tex

\chapter{Základné pojmy, motivácia a súvisiace práce}

V tejto kapitole čiatateľa oboznámime so základnými biologickými
a informatickými pojmami, s ktorými sa stretneme v tejto práci, s cieľom práce
a s motiváciou pre riešenie tohto problému. Taktiež si spomenieme niekoľko
prác súvisiacich s problematikou.

\section{Biologické pojmy a motivácia}

Genetická informácia všetkých známych bunkových organizmov je uložená v
deoxyribonukleovej kyseline, skrátene nazývanej \emph{DNA}. Ide o zložitú molekulu
pozostávajúcu z dvoch chemicky naviazaných polymérových vlákien stočených
do špirálovej štruktúry. Základné stavebné prvky, z ktorých sa tieto reťazce
skladajú, sa nazývajú nukleotidy. Každý nukleotid pozostáva
z fosfátového zvyšku, deoxyribózy a dusíkatej bázy. Nukleotidy sa od seba líšia
v dusíkatej báze, ktorá môže byť štyroch typov: adenín, guanín, tymín, cytozín.

Vlákna jednej molekuly DNA sú medzi sebou prepojené práve cez dusíkaté bázy.
S tým súvisí taktiež tzv. komplementárnosť týchto vlákien. Keď v jednom vlákne
máme adenínový nukleotid, spojený je s tymínovým nukleotidom v druhom vlákne
a naopak. Podobne sa guanínový nukleotid spája s cytozínovým.

Celá genetická informácia v jednej molekule DNA je tak kódovaná v podstate iba usporiadaním nukleotidov,
pre krátkosť sa toto usporiadanie zapisuje reťazcom pozostávajúcim
zo znakov \verb_A_, \verb_G_, \verb_T_ a \verb_C_, pričom každý znak zodpovedá
príslušnej dusíkatej báze. Kvôli chemickej štruktúre vlákna DNA záleží aj na tom,
v ktorom smere tento reťazec zapisujeme, čiže napr. reťazec \verb_GGA_ je
zásadne odlišný od reťazca \verb_AGG_. Smery komplementárnych vlákien sú opačné.

Bežný organizmus obsahuje viacero molekúl DNA, ktoré sú poskladané do štruktúr
nazývaných chromozómy. Genetickú informáciu, ktorou jedinec disponuje,
nazývame súhrnne menom \emph{genóm}.

\subsection{Sekvenovanie}

Sekvenovanie je proces, ktorým získavame genóm príslušného organizmu.
Väčšina sekvenovacích postupov má spoločné črty. Pomocou zložitých chemických
a fyzikálnych procesov sa najprv zistí mnoho krátkych reťazcov, ktoré sa
v reťazci DNA nachádzajú na vopred neznámych miestach. Tieto krátke reťazce
sa nazývajú \emph{čítania}, z anglického \emph{read}.

Z týchto čítaní sa potom pomocou rôznych algoritmov zisťuje, aký bol celý reťazec DNA.
Tento proces, nazývaný \emph{skladanie sekvencií}, je pomerne náročný, keďže čítania sa nachádzajú na neznámych miestach
v DNA a navyše, väčšina metód na ich zistenie má malú šancu pomýliť sa pri určovaní
niektorého nukleotidu. Preto sa pri každej metóde sekvenovania generuje toľko čítaní, aby
v priaznivom prípade mnohonásobne pokryli celý reťazec DNA. Očakávaný počet, koľkokrát
sme pokryli jeden konkrétny nukleotid týmito čítaniami, sa nazýva \emph{pokrytie},
z anglického \emph{coverage}.

\subsection{Indexácia čítaní}

Pokiaľ máme k dispozícii DNA reťazec nejakého jedinca, môže nás zaujímať, koľko a prípadne
ktoré čítania sa prekrývajú s nejakou časťou. Pomocou takýchto dotazov vieme zisťovať
mnohé zaujímavé informácie. Jednou možnosťou je napríklad hľadať rozdiely medzi
jedincami jedného druhu, inou je zisťovať, ktoré časti DNA majú akú funkciu, prípadne
ktoré majú vôbec nejakú. Pre prípady, kedy máme k dispozícii referenčnú sekvenciu živočíšneho
druhu, existujú efektívne štruktúry, ktoré vedia na dané dotazy odpovedať.

V mnohých prípadoch však referenčnú sekvenciu k dispozícii nemáme, napriek tomu by sme
radi vedeli odpovedať na podobné otázky. Jedno možné využitie štruktúry, ktorá vie
odpovedať na takýto typ dotazov, je aj v niektorých algoritmoch na
skladanie sekvencií, napríklad GAML \cite{gaml}.

V práci Philippe, Salsona a kol. \cite{gk_arrays} sa spomína sedem bežných typov otázok,
ktoré môžeme mať na nejakú sadu čítaní:

\begin{enumerate}
    \item Ktoré čítania obsahujú daný podreťazec $f$?
    \item Koľko čítaní obsahuje daný podreťazec $f$?
    \item Na ktorých pozíciach v čítaniach sa nachádza daný podreťazec $f$?
    \item Koľkokrát sa dohromady vyskytuje daný podreťazec $f$ v čítaniach?
    \item V ktorých čítaniach sa vyskytuje podreťazec $f$ iba raz?
    \item V koľkých čítaniach sa vyskytuje podreťazec $f$ iba raz?
    \item Na ktorých pozíciach v čítaniach sa nachádza podreťazec $f$, pričom nás
    zaujímajú iba tie čítania, ktoré ho obsahujú raz?
\end{enumerate}

\section{Súvisiace práce}

Prvou význačnou prácou pri indexácii čítaní sú tzv. Gk-Arrays \cite{gk_arrays}, ktoré
vyhľadávajú podreťazce s pomocou upravených sufixových polí nad zreťazením všetkých
čítaní.
Myšlienku Gk-arrays posunuli ďalej Välimäki a Rivals, keď prišli s komprimovanou
verziou \cite{comp_gk_arrays}.

S myšlienkovo odlišným riešením prišli Boža a Jursa. Namiesto zreťazenia čítaní použili
v CR-indexe \cite{cr_index} nadslovo všetkých čítaní, v ktorom nájdu pozície všetkých čítaní
a pomocou toho odpovedajú na rôzne dotazy. Keďže čítania sú v zamýšľanom použití podreťazcami celého
genómu s malou šancou chýb, očakávaná dĺžka ich nadslova je zhruba veľkosť genómu.

\section{Ciele práce}

Jedným z problémov CR-indexu boli chyby v čítaniach. Aj s pomerne malou chybovosťou
v dátach sa pri veľkom pokrytí objaví veľa čítaní s aspoň jednou chybou, ktoré s vysokou
pravdepodobnosťou nezapadnú do nadslova a budú napísané na konci nadslova s malými
prekryvmi s inými čítaniami.

Na druhú stranu, existujú nástroje, ktorými sa dá väčšina chýb v čítaniach zdetekovať
a odstrániť. V CR-indexe pomocou takýchto nástrojov väčšinu chýb opravia a nadslovo
hľadajú k opraveným čítaniam. Keďže si chcú zachovať korektnosť, chyby ukladajú tak,
že pre každú pozíciu každého čítania vedia povedať, či sa oproti časti nadslova,
ku ktorej je čítanie zarovnané, líši.

Všetky čítania a pozície, ktoré nájdu, musia skontrolovať, či obsahujú chyby na správnych miestach.
Takéto riešenie je dobré, pokiaľ chceme odpovedať na otázky prvého, tretieho, piateho a
siedmeho typu, keďže pri nich musíme aj tak nejakým spôsobom prejsť cez všetky výsledky.
Pokiaľ nás však zaujímajú počty, prípadne iná agregovaná informácia, v takomto riešení
musíme aj tak overiť všetky potenciálne čítania, ktoré získame.

V tejto práci sa pozrieme na to, aké otázky sa dajú efektívne zodpovedať, pokiaľ
oslabíme požiadavky na nadslovo, ktoré budeme pre čítania hľadať. Po tomto nadslove
budeme požadovať iba to, aby obsahovalo každú $k$-ticu znakov, ktorá sa vyskytovala
v niektorom čítaní, pre nejaké vopred zadané $k$. Aj keď zamýšľané použitie takéhoto
prístupu sa orientuje na efektívne uchovávanie čítaní, problémy a algoritmy budeme
formulovať všeobecnejšie, aby boli použiteľné aj v prípade, že nás zaujímajú podobné
informácie o iných dátach s podobnými vlastnosťami, aké majú čítania.

\section{Definície}

Vrámci celej práce budeme považovať nulu za prirodzené číslo a polia budeme indexovať
od nuly. Pod podslovom slova $s$ budeme rozumieť súvislú podpostupnosť jeho písmen.

Jednou z centrálnych definícií bude pojem $k$-nadslova.

\begin{defn}
    Nech $k > 1$ je celé číslo. Nech $\Sigma$ je nejaká abeceda a nech $S$ je množina
    slov dlhých aspoň $k$ nad abecedou $\Sigma$. Potom $k$-nadslovom množiny $S$ nazveme také slovo
    nad abecedou $\Sigma$, pre ktoré platí, že každé podslovo dĺžky $k$ nejakého slova z $S$ je
    zároveň podslovom $k$-nadslova.
\end{defn}

Nad poľom pravdivostných hodnôt si zadefinujeme operáciu $rank(i)$ ako počet hodnôt $Pravda$
na pozíciách od nuly po $i$ vrátane.

\subsection{Grafové definície}

V tejto práci budeme taktiež používať orientované grafy. Pod pojmom orientovaný graf $G$ budeme
rozumieť dvojicu $(V, E)$, kde $V$ je množina vrcholov a $E$ je množina usporiadaných
dvojíc $(v_1, v_2)$, kde $v_1$ aj $v_2$ sú vrcholmi grafu. Budeme hovoriť, že hrana $e$ vedie
z vrchola $v_1$ do vrchola $v_2$, pokiaľ $e = (v_1, v_2)$. Za slučku označíme každú hranu idúcu z vrchola
do neho samého, čiže každú hranu typu $(v, v)$.

Pre graf $G$ budeme používať $V(G)$ na označenie jeho množiny vrcholov a $E(G)$ na označenie jeho
množiny hrán. Pod množinou výstupných hrán
vrchola $v$ budeme rozumieť množinu $out(v) = \{ (v, v_2) | v_2 \in V(G) \}$ a podobne,
pod množinou vstupných hrán budeme rozumieť množinu $in(v) = \{ (v_1, v) | v_1 \in V(G) \}$.
Pre vrchol $v$ určíme jeho výstupný stupeň ako $d_O(v) = |out(v)|$ a jeho vstupný stupeň ako $d_I(v) = |in(v)|$.

Za podgraf grafu $G$ označíme ľubovoľný graf $G'$ taký, že $V(G') \subseteq V(G)$ a zároveň $E(G') \subseteq E(G)$.
Za faktorový podgraf grafu $G$ označíme taký podgraf $G'$, ktorý obsahuje všetky vrcholy $G$, čiže
$V(G) = V(G')$.

V prípade, že budeme hovoriť o viacerých grafoch a z kontextu nie je jasné, na ktorý z nich
sa niektorý z pojmov vzťahuje, tento graf zadefinujeme v hornom indexe, napríklad
$d_O^{G_2}(v)$ bude označovať výstupný stupeň vrchola $v$ v grafe $G_2$.

Pod pojmom \emph{sled grafu $G$} budeme rozumieť ľubovoľnú striedavú postupnosť vrcholov
a hrán $v_1 e_1 v_2 e_2 \ldots v_{n-1} e_{n-1} v_n$, ktorá začína aj končí nejakým vrcholom
grafu $G$ a v ktorej každá hrana $e_i$ vedie z vrchola $v_i$ do vrchola $v_{i+1}$. Sled označíme
ako prázdny, pokiaľ je jeho postupnosť prázdna. Dĺžku sledu definujeme ako počet vrcholov v slede.

V orientovanom grafe je možnosť definovať rôzne typy súvislosti, v tejto práci sa stretneme iba
so súvislosťou v neorientovanom zmysle. V ďalšej časti si formálne popíšeme tento typ súvislosti.

Za orientovaný doplnok grafu $G$ označíme taký graf $G'$,
ktorý obsahuje každú hranu z grafu $G$ obojsmerne, formálne zapísané:
\begin{enumerate}
    \item $V(G) = V(G')$,
    \item $E(G) \subseteq E(G')$,
    \item $\forall v_1, v_2 \in V(G') : (v_1, v_2) \in E(G') \Rightarrow (v_2, v_1) \in E(G')$.
\end{enumerate}

Na ľubovoľnom grafe $G$ si zadefinujeme reláciu medzi vrcholmi nasledovne: vrchol $v_1$ je spojený
s vrcholom $v_2$ práve vtedy, keď existuje sled v orientovanom doplnku grafu $G$, ktorý začína vo 
vrchole $v_1$ a končí vo vrchole $v_2$. Ľahko vidíme, že táto relácia je reláciou ekvivalencie.
Za komponenty (súvislosti) grafu $G$ označíme triedy ekvivalencie tejto relácie. Nakoniec za súvislý graf
označíme taký, ktorý má jeden komponent.



%TODO: Definicia k-nadslova sa musi vysporiadat so slovami kratsimi ako k.
%TODO: Definicia k-nadslova musi zarucit, ze S obsahuje aspon jedno slovo dlzky k.
%TODO: Definicia stupnov (delt) musi zadefinovat aj, v ktorom grafe.
%TODO: rank, (select?)