107 lines
4.7 KiB
TeX
107 lines
4.7 KiB
TeX
\documentclass{scrartcl}
|
|
\RequirePackage{algorithm}
|
|
\RequirePackage{algorithmicx}
|
|
\RequirePackage[noEnd=false]{algpseudocodex}
|
|
\newcommand{\algorithmautorefname}{Algorithm} % Allow autoref.
|
|
% Define macros to typeset boolean in pseudocode environments
|
|
\algnewcommand{\True}{\textbf{\texttt{true}}}
|
|
\algnewcommand{\False}{\textbf{\texttt{false}}}
|
|
\algnewcommand{\NIL}{\textbf{\texttt{NIL}}}
|
|
\algnewcommand{\NULL}{\textbf{\texttt{null}}}
|
|
\input{definitions.tex}
|
|
\usepackage{mathtools}
|
|
\begin{document}
|
|
|
|
\begin{algorithm}
|
|
\caption{Backtrack a single alignment in a recursive way}
|
|
\begin{algorithmic}[1]
|
|
\State $S_{1}$: Array($m$), $S_{2}$: Array($n$), $M$: Array($m+1$, $n+1$),
|
|
\Function{BacktrackRecurse}{$i$, $j$}
|
|
\If {$i > 0$ and $j > 0$}
|
|
\State $substitute = M[i-1][j-1]$
|
|
\State $delete = M[i-1][j]$
|
|
\State $insert = M[i][j-1]$
|
|
\State $min = \min \{ substitute, delete, insert \}$
|
|
\If {$substitute = min$}
|
|
\State $z = $ \Call{BacktrackRecurse}{$S_{1}$, $S_{2}$, $M$, $i-1$, $j-1$}
|
|
\State $z = \begin{pmatrix} S_{1}[i-1] \\ S_{2}[j-1] \end{pmatrix} \circ z$
|
|
\ElsIf {$delete = min$}
|
|
\State $z = $ \Call{BacktrackRecurse}{$S_{1}$, $S_{2}$, $M$, $i-1$, $j$}
|
|
\State $z = \begin{pmatrix} S_{1}[i-1] \\ \varepsilon \end{pmatrix} \circ z$
|
|
\Else
|
|
\State $z = $ \Call{BacktrackRecurse}{$S_{1}$, $S_{2}$, $M$, $i$, $j-1$}
|
|
\State $z = \begin{pmatrix} \varepsilon \\ S_{2}[j-1] \end{pmatrix} \circ z$
|
|
\EndIf
|
|
\ElsIf {$i > 0$}
|
|
\State $z = $ \Call{BacktrackRecurse}{$S_{1}$, $S_{2}$, $M$, $i-1$, $j$}
|
|
\State $z = \begin{pmatrix} S_{1}[i-1] \\ \varepsilon \end{pmatrix} \circ z$
|
|
\ElsIf {$j > 0$}
|
|
\State $z = $ \Call{BacktrackRecurse}{$S_{1}$, $S_{2}$, $M$, $i$, $j-1$}
|
|
\State $z = \begin{pmatrix} S_{1}[i-1] \\ \varepsilon \end{pmatrix} \circ z$
|
|
\Else
|
|
\State \Return []
|
|
\EndIf
|
|
\State \Return $z$
|
|
\EndFunction
|
|
\Function{Backtrack}{$S_{1}$: Array($m$), $S_{2}$: Array($n$), $M$: Array($m+1$, $n+1$)}
|
|
\State \Return \Call{BacktrackRecurse}{$S_{1}$, $S_{2}$, $M$, $m$, $n$}
|
|
\EndFunction
|
|
\end{algorithmic}
|
|
\end{algorithm}
|
|
|
|
\begin{algorithm}
|
|
\caption{Backtrack all the optimum alignments in a recursive way}
|
|
\begin{algorithmic}[1]
|
|
\Procedure{Recurse}{$S_{1}$: Array($m$), $S_{2}$: Array($n$), $M$: Array($m+1$, $n+1$), $i$, $j$}
|
|
\If {$i > 0$ and $j > 0$}
|
|
\State $substitute = M[i-1][j-1]$
|
|
\State $delete = M[i-1][j]$
|
|
\State $insert = M[i][j-1]$
|
|
\State $min = \min \{ substitute, delete, insert \}$
|
|
\If {$substitute = min$}
|
|
\State $value = \begin{pmatrix} S_{1}[i-1] \\ S_{2}[j-1] \end{pmatrix}$
|
|
\State $z' = value \circ z$
|
|
\State \Call{BacktrackRecurse}{$S_{1}$, $S_{2}$, $M$, $i-1$, $j-1$, $z'$}
|
|
\EndIf
|
|
\If {$delete = min$}
|
|
\State $value = \begin{pmatrix} S_{1}[i-1] \\ \varepsilon \end{pmatrix}$
|
|
\State $z' = value \circ z$
|
|
\State \Call{BacktrackRecurse}{$S_{1}$, $S_{2}$, $M$, $i-1$, $j$, $z'$}
|
|
\EndIf
|
|
\If {$insert = min$}
|
|
\State $value = \begin{pmatrix} \varepsilon \\ S_{2}[j-1] \end{pmatrix}$
|
|
\State $z' = value \circ z$
|
|
\State \Call{BacktrackRecurse}{$S_{1}$, $S_{2}$, $M$, $i$, $j-1$, $z'$}
|
|
\EndIf
|
|
\ElsIf {$i > 0$}
|
|
\State $value = \begin{pmatrix} S_{1}[i-1] \\ \varepsilon \end{pmatrix}$
|
|
\State $z' = value \circ z$
|
|
\State \Call{BacktrackRecurse}{$S_{1}$, $S_{2}$, $M$, $i-1$, $j$, $z'$}
|
|
\ElsIf {$j > 0$}
|
|
\State $value = \begin{pmatrix} \varepsilon \\ S_{2}[j-1] \end{pmatrix}$
|
|
\State $z' = value \circ z$
|
|
\State \Call{BacktrackRecurse}{$S_{1}$, $S_{2}$, $M$, $i$, $j-1$, $z'$}
|
|
\EndIf
|
|
\State \Call{print}{$z$}
|
|
\EndProcedure
|
|
\Procedure{Backtrack}{$S_{1}$: Array($m$), $S_{2}$: Array($n$), $M$: Array($m+1$, $n+1$)}
|
|
\State \Return \Call{BacktrackRecurse}{$S_{1}$, $S_{2}$, $M$, $m$, $n$, []}
|
|
\EndProcedure
|
|
\end{algorithmic}
|
|
\end{algorithm}
|
|
|
|
\end{document}
|
|
|
|
\end{document}
|
|
\iffalse
|
|
\Function{AppendToAll}{$value$, $set$}
|
|
\Returns {A new set with all elements from $set$ with value appended first to them }
|
|
\State $res = \{\}$
|
|
\For {$element \in set$}
|
|
\State $element = value \circ element$
|
|
\State $res = res \cup element$
|
|
\EndFor
|
|
\State \Return $res$
|
|
\EndFunction
|
|
\fi
|