\section{Hľadanie motívov}

Doteraz sme sa prevažne zaoberali problémami, kde sme v texte chceli
nájsť nejakú nami zvolenú vzorku. Dnešný problém je trochu opačný: na
základe textov sa snažíme nájsť zaujímavú vzorku, ktorá sa v nich
často vyskytuje.

\subsection{Biologická motivácia}

DNA obsahuje gény (úseky kódujúce proteíny, RNA molekuly) a sekvencie
regulujúce, kedy sa ktorý gén má transkribovať (kopírovať do RNA). Na
spustenie transkripcie sa na DNA viažu proteíny zvané transkripčné
faktory, ktoré ``prilákajú'' RNA polymerázu k začiatku génu, aby sa
mohla začať transkripcia. Chceli by sme vedieť, ktorý transkripčný
faktor sa kam viaže v genóme a ktoré gény reguluje. Každý faktor
rozpoznáva určitý motív v DNA sekvencii. Napríklad faktor E2F1 sa
viaže na reťazec TTTCGCGC, pripúšťa však určité obmeny, napr. 4. a
5. pozícia môžu byť C alebo G a jedno z prvých troch T môže byť
zmenené na iný znak.

Máme teda jeden konkrétny transkripčný faktor a chceme zistiť, na aký
motív v sekvencii sa viaže. Môžeme použiť experimentálne metódy, ktoré
vedia nájsť približne miesta, kde sa daný faktor viaže, s presnosťou
napr. asi 500 znakov. Na základe takéhoto experimentu dostaneme veľa
probližne 500-znakových úsekov genómu a chceme nájsť krátky motív,
nachádzajúci sa v každom alebo aspoň vo väčšine z nich. Dostávame teda
výpočtové problémy nasledujúceho typu:

Máme dané reťazce $S_1, S_2,\dots,S_k$ dĺžky $n$ a dĺžku motívu
$L<n$. Chceme nájsť motív dĺžky $L$, ktorý sa vyskytuje v každom,
alebo v čo najviac reťazcoch $S_i$. 

Skúma sa niekoľko formulácií tohto problému, ktoré sa líšia definíciou
motívu a jeho výskytov.

\subsection{Problém 1: presné výskyty reťazca}

V tomto prípade motív bude jednoducho reťazec dĺžky $L$ a budeme
uvažovať jeho presné výskyty v texte. Hľadáme teda také slovo dĺžky
$L$, ktoré sa vyskytuje v čo najviac zo vstupných reťazcov $S_1,
S_2,\dots,S_k$. Triviálne môžeme tento problém riešiť tak, že
zoberieme každé podslovo dĺžky $L$ zo vstupných reťazcov a spočítame
jeho výskyty v ostatných reťazcoch. Ak použijeme triviálny algoritmus
aj na hľadanie výskytov, dostaneme zložitosť $O(n^2k^2L)$. Videli sme
však, ako sa dá tento problém riešiť aj v lineárnom čase $O(nk)$, ak
použijeme sufixové stromy a štruktúry na hľadanie najnižšieho
spoločného predka.


\subsection{Problém 2: Consensus Pattern Problem, nepresné výskyty reťazca}

V tomto probléme je motív stále obyčajný reťazec, dovoľujeme však 
približné výskyty, pričom meriame Hammingovu vzdialenosť. Formálne
hľadáme reťazec $S$ dĺžky $L$ a pozície výskytu $i_1, i_2,\dots i_k$
také, že súčet vdialeností od $S$ k jednotlivým výskytom $\sum_{j=1}^k
d_H(S,S_j[i_j..i_j+L-1])$ je minimálny. 

Poznámka: Ak by sme namiesto Hammingovej použili editačnú vzdialenosť,
išlo by o lokálnu verziu viacnásobného zarovnania.

Tento problém je opäť NP-ťažký, obsahuje však dva podproblémy, ktoré
sa dajú efektívne riešiť. Ak poznáme výskyty $i_1,\dots i_k$, vieme
optimálne $S$ nájsť tak, že na každej pozícii zoberieme znak s
najväčším počtom výskytov. Naopak, ak poznáme $S$, vieme nájsť
$i_1,\dots i_k$ tak, že v každej sekvencii vyberieme podslovo dĺžky
$L$ s najmenšou Hammingovou vzdialenosťou od $S$.


Tieto dva algoritmy sa dajú spojiť do jednoduchej heuristiky: začneme
s nejakým zoznamom výskytov, pre ne nájdeme najlepší motív $S$ a pre tento
motív znova nájdeme výskyty. To opakujeme, kým dochádza k zmenám. V
každej iterácii sa cena riešenia zlepší, alebo ostane rovnaká.

Druhá heuristika zvolí za $S$ nejaké podslovo reťazca $S_i$ dĺžky $L$,
potom nájde výskyty. Ak toto spravíme pre všetky podslová všetkých
vstupných reťazcov a zvolíme najlepšie, dostávame 2-aproximačný algoritmus. 

Dôkaz: Nech $\alpha_i$ je optimálny výskyt optimálneho motívu $S$ v
reťazci $S_i$, nech $d_i=D_H(\alpha_i,S)$ a nech $p$ je index
najmenšieho $d_i$. Potom keď skúšame v našom algoritme motív
$\alpha_p$, dostávame podľa trojuholníkovej nerovnosti, ktorá pre
Hammingovu vzdialenosť platí, nasledujúci vzťah:
$$d_H(\alpha_p,\alpha_i)
\le d_H(\alpha_p,S)+d_H(S,\alpha_i)\le 2d_H(\alpha_i,S).$$
Teda cena motívu $\alpha_p$ je najviac dvojnásobok ceny $S$.
Náš algoritmus nájde riešenie aspoň tak dobré ako  $\alpha_p$
(môže zvoliť iné výskyty alebo iný motív, ale iba ak sú aspoň tak dobré).

Tento algoritmus môžeme ďalej zovšeobecniť tak, že nebudeme začínať z
jedného podslova, ale z $r$ podslov, kde $r$ je konštanta zvolená
užívateľom. Budeme skúšať všetky $r$-tice podslov dĺžky $L$ zo
vstupných reťazcov s opakovaním (t.j. to isté podslovo môžeme použiť
aj viackrát v tej istej $r$-tici).  Pre každú $r$-ticu nájdeme jej
konsenzus $S$ (najpočetnejšie písmeno v každom stĺpci) a pre $S$ potom
nájdeme najlepší výskyt v každom reťazci. Celkovo zvolíme $S$, ktoré
malo najlepšiu cenu. 

Príklad: Uvažujme reťazce abaab, baaba, aabab, bbaaa, aabba a $L=5$,
t.j. celý reťazec bude výskytom.  Optimálny motív je aaaaa s cenou 10
(od každého reťazca sa líši o 2). Pre $r=1$ zvolíme vždy za motív
jeden reťazec. Zhodou okolností nám pre každý výjde cena 12,
t.j. aproximačný faktor 1,2. Pre $r=3$ napr. pre trojicu abaab, baaba
a aabab dostaneme konsenzus aaaab, ktorý má cenu 11, t.j.  aproximačný
faktor 1,1. 


Li, Ma and Wang (1999) dokázali, že tento algoritmus má aproximačný
faktor najviac $1+\frac{4\sigma-4}{\sqrt{e}(\sqrt{4r+1}-3)}$ v čase
$O((nk)^{r+1}L)$. Ide teda o polynomiálnu aproximačnú schému (PTAS):
pre ľubovoľné $\epsilon$ si vieme zvoliť $r$ tak, aby chyba bola
menšia ako $1+\epsilon$. Avšak čas rastie exponenciálne s $r$ a
nedostávame tak veľmi praktický algoritmus.


\subsection{Problém 3: Closest substring, nepresné výskyty reťazca}

Tento probléme sa líši od predchádzajúceho iba definíciou ceny
riešenia. Namiesto súčtu vzdialeností výskytov od motívu budeme
uvažovať maximum: $\max d_H(S,S_j[i_j..i_j+L-1])$. Ak tento problém
preformulujeme ako rozhodovací, pýtame sa, či pre existuje motív,
ktorý má v každom vstupnom reťazci výskyt s Hammingovou vzdialenosťou
najviac $k$.

Tento problém je ešte o niečo ťažší ako predchádzajúci, lebo aj keby
sme poznali výskyty, nevieme ľahko nájsť motív.  Nasledujúci problém
je totiž tiež NP-úplný. Closest string problem: pre dané reťazce $S_1,
S_2,\dots,S_k$ rovnakej dĺžky $n$ nájdi reťazec, ktoré je od každého z
nich vo vzdialenosti najviac $k$. 

Rovnako ako predtým však aj tu môžeme dostať 2-aproximačný algoritmus,
ak budeme ako $S$ skúšať všetky podslová. Takisto sa v praxi používa
prehľadávanie s orezávaním, ktoré často vie nájsť optimálne riešenie
na realistických inštanciách.

\subsection{Problém 4: motív ako regulárny výraz}

Motív tentokrát bude jednoduchý regulárny výraz, v ktorom okrem
normálnych znakov, dovolíme aj žolíky, ktoré reprezentujú jeden z
danej množiny znakov. Napríklad motív pre transkripčný faktor E2F1 sa
dá zapísať ako \verb"TTT[CG][CG]CGC", kde na štvrtej a piatej pozícii
dovoľujeme C alebo G. Niekedy sa skúmajú aj motívy s flexibilnými
medzerami, napr. \verb"TTT-N(2,3)-CGC" reprezentuje motív, ktorý
začína TTT, potom obsahuje ľubovoľné 2 alebo 3 písmená (N zvykne v DNA
označovať ľubovoľný alebo neznámy znak) a potom CGC. Pri regulárnych
výrazoch zvyčajne za výskyt považujeme podslovo, ktoré spĺňa tento
výraz, t.j. už nepovoľujeme ďalšie substitúcie.

Pre daný motív chceme uvažovať počet jeho výskytov, ale aj jeho
špecifickosť (motív s veľa žolíkmi sa bude často vyskytovat aj čisto
náhodou). V tejto oblasti existuje zaujímavá kombinaorická teória,
ktorá definuje akúsi lineárne veľkú bázu motívov, z ktorej sa dajú
odvodiť všetky ostatné motívy s aspoň dvoma výskytmi v daných
reťazcoch bez toho, aby sme sa pozerali na tieto reťazce.

\subsection{Problém 5: motív ako pravdepodobnostný profil}

Regulárny výraz môže dovoľovať na určitej pozícii výber z viacerých
alternatív, nevie však zašpecifikovať, že niektoré z týchto alternatív
sa vyskytujú menej často a niektoré častejšie. Toto sa dá dosiahnuť
pravdepodobnostným profilom. Ten je určený maticou $A$ rozmerov
$\sigma \times L$, kde $A[x,i]$ je pravdepodobnosť, že na $i$-tej
pozícii v motíve bude znak $x$. Súčet každého stĺpca matice je 1.  V
príklade na obrázku \ref{fig:profil} tretia, šiesta, siedma a ôsma
pozícia obsahujú vždy jedno fixné písmeno s pravdepdobnosťou 1, kým na
ostatných pozíciách sú možné vždy dve rôzne písmená potenciálne s
rôznou pravdepodobnosťou.

\begin{figure}
\centerline{
\begin{tabular}{c*{8}{r}}
  & 1  & 2  & 3  & 4  & 5  & 6  & 7  & 8  \\
A &0.1 & 0  & 0  & 0  & 0  & 0  & 0  & 0  \\
C &0   & 0.1& 0  & 0.5& 0.4& 1  & 0  & 1  \\
G &0   & 0  & 0  & 0.5& 0.6& 0  & 1  & 0  \\
T &0.9 & 0.9& 1  & 0  & 0  & 0  & 0  & 0  \\
\end{tabular}}
\caption{Príklad pravdepodobnostného profilu.}
\label{fig:profil}
\end{figure}

Aby sme určili, či nejaký reťazec $\alpha$ dĺžky $L$ je výskytom
motívu, spočítame jeho pravdepodobnosť ako súčin $p_\alpha =
\prod_{i=1}^L A[i,\alpha[i]]$ (predpokladáme teda, že jednotlivé
pozície motívu sú nezávislé). Môžeme potom obmedziť výskyty ako
reťazce s pravdepodbnosťou nad určitou hranicou.

Ak však hľadáme nový motív, zvyčajne neurčujeme jednoznačný prah
pravdepodobnosti, ale hľadáme tabuľku $A$ a výskyt v každej sekvencii
$\alpha_1,\dots,\alpha_k$, ktoré maximalizujú súčin pravdepdobností
jednotlivých výskytov $\prod_{j=1}^k p_{\alpha_j}$. Ak už poznáme sadu
výskytov a chceme zostaviť motív, ktorý by maximalizoval tento súčin,
spočítame na každej pozícii relatívne frekvencie jednotlivých znakov
medzi výskytmi a tie dáme do tabuľky. Všimnite si, že toto je podobné
na Consensus pattern problem, kde sme do motívu dali vždy najčastejší
znak.

Jedným z možných heuristických prístupov na riešenie tohto problému je
stochastický algoritmus Gibbs Sampling. Tento na začiatku zvolí
náhodné výskyty $\alpha_1,\dots,\alpha_k$ a z nich zostaví
profil. Potom v každej iterácii vyberie jeden zo vstupných reťazcov
$S_i$ a v ňom zvolí náhodne jednu pozíciu ako nový výskyt $\alpha_i$
pričom každú pozíciu v sekvencii zvolí s pravdepodobnosťou úmernou
$p_{\alpha_i}$ pre túto pozíciu. Po zvolení nového výskytu prepočítame
profil a celý postup veľa krát opakujeme.

Tento iteratívny algoritmus sa podobá na jednoduchú heuristiku, ktorú
sme videli pre Consensus pattern problem, ale líši sa v dvoch
aspektoch: v každej iterácii meníme polohu len jedného výskytu, nie
všetkých a ako nový výskyt neberieme ten najlepší, ale náhodne, pričom
lepšie výskyty majú väčšiu pravdepodobnosť.

