\section{Viacnásobné zarovnanie}

\paragraph{Základný problém:} dané sú reťazce: $ S_1, S_2, ..., S_k $, $ n = \sum_{i=1}^{k} |S_i| $. Nájdite zarovnanie s optimálnou cenou.

\paragraph{Príklad:} Zarovnanie troch reťazcov

\[
\left(
\begin{array}{ccccccc}
A&C&A&G&T&-&A\\
A & - & A & C & T & - & C\\
G & C & A & C & T & G & A\\
\end{array}
\right)
\]

\paragraph{Motivácia:} bioinformatika 
\begin{itemize}
 \item hypotéza o evolúcií: rovnaké znaky v jednom stĺpci pravdepodobne pochádzajú od spoločného predka
 \item zistiť, či ide o inzerciu alebo deléciu
 \item nájsť pozície, ktoré sa málo menia (takéto pozície majú často dôležitú biologickú funkciu a mutácia znamená vyhynutie organizmu, teda prírodný výber ich udržuje viac-menej nemenné)
\end{itemize}

\paragraph{Cena zarovnania:} Cenu $w(A)$ viacnásobného zarovnania $A$, môžme určiť rôznymi spôsobmi, my si uvedieme tieto tri:
	\begin{enumerate}
	 \item Sum-of-pairs(SP) - cenu určíme ako súčet cien všetkých dvojíc riadkov viacnásobného zarovnania. Presnejšie 
		 	\[ w(A) = \sum_{i<j} d_A(S_i,S_j) \] kde $d_A$ je cena zarovnania\footnote{$d_A$ je editačná vzdialenosť a cena substitúcie, inzercie, delécie je 1, v prípade dvoch pomlčiek cenu dodefinujeme ako 0} indukovaného viacnásobným zarovnaním A. Cena príkladu $w(A) = d_A(S_1,S_2) + d_A(S_1,S_3) + d_A(S_2,S_3) = 3+3+4=10 $.
			
	 \item Porovnanie s konsenzom. Konsenzus $C_A$ viacnásobného zarovnania $A$ je reťazec, s dĺžkou rovnakou ako zarovnania, ktorého znaky sú najčastejšie sa vyskytujúce znaky v danom stĺpci zarovnania. Potom cenu definujeme ako:
			\[ w(A) = \sum_{i=1}^{k} d_A(S_c,S_i) \]
	Konsenzus príkladu je $C_A = $ACACT-A a cena zarovnania $w(A) = d_A(C_A,S_1) + d_A(C_A,S_2) + d_A(C_A,S_3) = 1+2+2=5$
	 \item Využitie fylogenetického stromu - predpokladajme, že máme strom $T$ o vývoji organizmov. Ku každej vstupnej sekvencii je priradený list stromu $T$. V každom vnútornom vrchole $u$ chceme zostrojiť reťazce $S_u$, také že cena
	\[ w(A) = \sum_{(u,v)\in T} d_E(S_u,S_v) \]
	je minimálna.

       Túto sumu budeme nazývať fylogenetická vzdialenosť - minimálny
       počet operácií, ktoré sú nutné aby sme upravili reťazec z nejakého 
       neznámeho koreňa na listy.

	\end{enumerate}

Všimnime si, že v poslednej definícii sme zadefinovali cenu pre určitú množinu reťazcov, ale nie samotné zarovnanie. Ak chceme zostrojiť aj zarovnanie, použijeme nasledovný pomocný pojem.

\paragraph{Definícia:} Nech $T$ je strom. Vrcholu $u$ priradíme reťazec $S_u$. Hovoríme, že zarovnanie $A$ reťazcov $S_u$ je konzistentné s $T$ ak pre všetky hrany $(u,v)\in T$ platí 
	$ d_E(S_u,S_v) = d_A(S_u,S_v) $

\paragraph{Lema:} Pre každý strom existuje konzistentné zarovnanie.

\begin{figure}[h]
     \centerline{
             \includegraphics[scale=0.5]{figures/l19-strom.eps}
             }
	\caption{Príklad stromu s editačnými vzdialenosťami susedných vrcholov}
	\label{fig-eg}
\end{figure}


Ak teda poznáme strom a reťazce vo vnútroných vrcholoch z definície fylogenetickej vzdialenosti, podľa lemy zostrojíme zarovnanie reťazcov pre všetky vrcholy (vnútorné aj listy) a zmažeme reťazce pre vnútorne vrcholy, čím dostávame zarovnanie pre vstupné reťazce.

\paragraph{Dôkaz lemy:} indukciou vzhľadom na počet vrcholov (reťazcov v zarovnaní)
\begin{enumerate}
 \item báza: $k=2$ 2 vrcholy - zoberieme optimálne zarovnanie dvoch reťazcov vzhľadom na editačnú vzdialenosť
 \item $k>2$ Máme strom $T$. Odoberme mu list $u$. $T' = T - {u}$. Z IP vyplýva, že existuje konzistentné zarovnanie pre $T'$, nazvime ho $A'$. Označme $v$ suseda $u$ v $T$ a $A_p$ optimálne zarovnanie $S_u$ a $S_v$. Teraz po stĺpcoch spojíme $A'$ a $A_p$ do $A$. 
\begin{figure}[h]
     \centerline{
             \includegraphics[scale=0.5]{figures/l19-lema_konzistentne.eps}
             }
	\caption{Stromy $T$ a $T'$ v druhom kroku dôkazu lemy}
	\label{fig-eg}
\end{figure}
\begin{center}
\begin{tabular}{|c|c|}
 \hline
  ${x \choose y} \in A_p$ & $y$ vložíme pod $x$ v $A$\\
\hline
 ${x \choose -}\in A_p$ & $-$ vložíme pod $x$ v $A$\\
\hline 
${- \choose y} \in A_p$ & $y$ vložíme stĺpec $-$ do $A$ a pod neho $y$ \\
\hline
\end{tabular}
\end{center}

Stĺpce v $A'$ s pomlčkou v $S_v$ majú pomlčku v $S_u$. Takto zostrojené zarovnanie má cenu $ w(A') + d_E(S_u,S_v)$

\end{enumerate}


\paragraph{Poznámka:} Konštruktívny dôkaz dáva návod na algoritmus v polynomiálnom čase.

\subsection{Algoritmus pre SP}
\paragraph{Dynamické programovanie:} Tak ako v prípade zarovnania dvoch reťazcov tak aj v tomto prípade môžeme použiť dynamické programovanie. Zadefinujme si podúlohu pre zarovnanie troch reťazcov: \[A[i,j,k] = \textrm{cena optimálneho zarovnania}\ S_1[1..i], S_2[1..j], S_3[1..k]\]

Taktiež si zadefinujme funkciu na ohodnotenie stĺpca v zarovnaní:

$v(a,b,c) = $ cena stĺpca $\left( \begin{array}{c} a\\b\\c \end{array} \right) $, $a,b,c \in \Sigma \cup \{-\}$. Napríklad $v(A,A,C) = 2$, $v(-,-,A) = 2$.

\paragraph{Rekurencia:}

\[A[i,j,k] = min \left\{ 
\begin{array}{l l}
  A[i-1,j-1,k-1] + v(S_1[i],S_2[j],S_3[k]) \\
  A[i-1,j,k-1] + v(S_1[i],-,S_3[k]) \\
  A[i-1,j-1,k] + v(S_1[i],S_2[j],-) \\
  A[i,j-1,k-1] + v(-,S_2[j],S_3[k]) \\
  A[i,j,k-1] + v(-,-,S_3[k]) \\
  A[i,j-1,k] + v(-,S_2[j],-) \\	
  A[i-1,j,k] + v(S_1[i],-,-) \\
\end{array} \right. 
\]

Vo všeobecnom prípade pre $k$ reťazcov dostávame $2^k -1$ možností. Celková zložitosť algoritmu je $O((2(n+1))^k)$. V roku 2006 Elias ukázal, že viacnásobné zarovnanie je NP-ťažké, pre všetky 3 typy cien.

V praxi sa používajú rôzne heuristiky:
\begin{itemize}
 \item orezávanie dynamického programovania
 \item progresívne algoritmy(rekurzívne rozdelím na dve časti a potom zarovnávam zarovnania\footnote{Tiež NP-ťažký problém})
 \item použitím kotvy - dostatočne dlhý spoločný reťazec - potom sa zarovnávajú reťazce samostatne pred kotvou a za ňou.
\end{itemize}

\paragraph{Aproximačný algoritmus pre SP cenu}
Určíme centrálny reťazec $S_c \in \{ S_1,S_2, \ldots S_k \}$ taký, že $ \sum_{i=1}^{k} d_E(S_c,S_i) $ je minimálna. 

\begin{figure}[h]
     \centerline{
             \includegraphics[scale=0.5]{figures/l19-centralny_retazec.eps}
             }
	\caption{Strom s centrálnym reťazcom $S_c$, z ktorého zostavíme konzistentné viacnásobné zarovnanie}
	\label{fig-eg}
\end{figure}
       

Existuje zarovnanie konzistentné so stromom. V polynomiálnom čase zostrojíme viacnásobné zarovnanie $A$.

Pre indukovanú vzdialenosť $d_A$ tiež platí trojuholníková nerovnosť
\[ d_A(S_i,S_j) \leq d_A(S_i,S_c) + d_A(S_c,S_j) \]

Označme $A^*$ optimálne zarovnanie. Potom pre aproximačný faktor platí:
\[ \frac{w(A)}{w(A^*)} = \frac{\sum_{i \neq j} d_A(S_i,S_j)} {\sum_{i \neq j} d_{A^*}(S_i,S_j)} \]

Pre čitateľ platí
\[ \sum_{i \neq j} d_A(S_i,S_j) \leq \sum_{i \neq j} (d_E(S_i,S_c) + d_E(S_c,S_j))  = 2(k-1)\sum_{i=1}^{k} d_E(S_i,S_c) \]

pre menovateľ
\[ \sum_{i \neq j} d_{A^*}(S_i,S_j) \geq \sum_{i \neq j} d_E(S_i,S_j) \geq \sum_{i,j} d_E(S_i,S_c) = k\sum_{i=1}^{k} d_E(S_i,S_c) \]

z toho 

\[ \frac{w(A)}{w(A^*)} \leq \frac{2(k-1)\sum_{i=1}^{k} d_E(S_i,S_c)} { k\sum_{i=1}^{k} d_E(S_i,S_c)} = \frac{2(k-1)}{k} < 2 \]


