gotoh (7jul17)

git-svn-id: svn://tug.org/texlive/trunk@44764 c570f23f-e606-0410-a88d-b1316a301751

1 files changed, 282 insertions, 228 deletions

diff --git a/Master/texmf-dist/source/latex/gotoh/gotoh.dtx b/Master/texmf-dist/source/latex/gotoh/gotoh.dtx
index 14395318b26..9c35e9a1a35 100644
--- a/Master/texmf-dist/source/latex/gotoh/gotoh.dtx
+++ b/Master/texmf-dist/source/latex/gotoh/gotoh.dtx
@@ -11,14 +11,14 @@
 % 
 % \fi
 %
-% \CheckSum{971}
+% \CheckSum{984}
 %
 % \changes{v1.0}{2017/05/05}{The first version}
 % 
 % \iffalse
 %<*package>
 \NeedsTeXFormat{LaTeX2e}
-\ProvidesPackage{gotoh}[2017/05/05 v1.0 Sequence alignment algorithm]
+\ProvidesPackage{gotoh}[2017/07/07 v1.1 Sequence alignment algorithm]
 %</package>
 %<*driver>
 \documentclass[draft]{ltxdoc}
@@ -105,16 +105,16 @@
 % \section{Calculating the Alignment}
 %
 % \DescribeMacro{\Gotoh}
-% The |\Gotoh| command simply takes two sequences as its arguments.
+% The syntax of |\Gotoh| is shown below.
 % \begin{quote}
-% |\Gotoh|\marg{sequence A}\marg{sequence B}
+% |\Gotoh|\oarg{key-value list}\marg{sequence A}\marg{sequence B}
 % \end{quote}
 % The command puts the optimal score of the alignment to specified control
 % sequence (default: |\GotohScore|) after executing the Gotoh algorithm, and
 % returns the alignment results to other control sequences (default:
 % |\GotohResultA| and |\GotohResultB|). Note that these assignments are done
-% globally. The control sequences to store the score and results can be changed
-% with |\GotohConfig| command.
+% globally. Using the optional argument, you can change the configuration
+% temporary with the same keys in |\GotohConfig| (see the next section).
 %
 % \section{Configuration}
 %
@@ -288,7 +288,7 @@
 % \begin{macro}{\gth@d}
 % \begin{macro}{\gth@e}
 % These are keys for setting the parameters of the algorithm. The default
-% values which are shown in equations~(\ref{eq:parameters}) are set here, and
+% values which are shown in Equations~(\ref{eq:parameters}) are set here, and
 % stored in the macros (\emph{not} count registers) respectively.
 %    \begin{macrocode}
 \define@cmdkeys[gth]{config}[gth@]{match, mismatch, d, e}
@@ -393,7 +393,7 @@
 % g(l) = -d - (l-1)e. \label{eq:gap}
 % \end{equation}
 % In this equation, $d$ and $e$ are parameters of the algorithm, which have
-% default values shown in equations~(\ref{eq:parameters}).
+% default values shown in Equations~(\ref{eq:parameters}).
 %    \begin{macrocode}
 \def\gth@gap@penalty#1{%
   \gth@calc#1\relax
@@ -403,10 +403,10 @@
 %    \end{macrocode}
 % \end{macro}
 %
-% \subsection{Printing Matrixes}
+% \subsection{Printing Matrices}
 %
 % \begin{macro}{\gth@print@matrix}
-% This command shows the matrixes $M$, $I_x$ or $I_y$ (See
+% This command shows the matrices $M$, $I^x$ or $I^y$ (See
 % section~\ref{sect:algorithm}). The argument of this macro specifies which
 % matrix to show, so you can detect |m|, |ix|, or |iy|. However, this macro is
 % currently only for the author of this package to debug.
@@ -419,7 +419,7 @@
     \mbox{\hbox to\gth@tempdima{\hss #1}}%
   \egroup}
 \def\gth@print@matrix#1{%
-  \bgroup\texttt
+  \bgroup\ttfamily
     #1:\\
     \gth@tempcnta\z@
     \@whilenum\gth@tempcnta<\gth@m\do{%
@@ -427,7 +427,7 @@
       \@whilenum\gth@tempcntb<\gth@n\do{%
         \gth@tab{%
           \gth@nameuse{\gth@sn @#1@\the\gth@tempcnta
-                    @\the\gth@tempcntb}}%
+                       @\the\gth@tempcntb}}%
       \advance\gth@tempcntb\@ne}\\
     \advance\gth@tempcnta\@ne}%
   \egroup}
@@ -437,21 +437,42 @@
 % \subsection{Executing the Gotoh Algorithm}\label{sect:algorithm}
 %
 % \begin{macro}{\Gotoh}
-% This is the user interface to execute the Gotoh algorithm.  If the boolean
-% switch |\if@gth@uppercase| is true, the arguments are processed by
-% |\uppercase| preamble before passing them to |\gth@gotoh| macro.
+% \changes{v1.1}{2017/07/07}{Add a new optional argument for changing
+% config temporary}
+% This is the user interface to execute the Gotoh algorithm.  First, the
+% `serial number' is incremented. The whole other process executed by this
+% macro contained in a group because a number of temporary macros are defined
+% during processing.
 %    \begin{macrocode}
-\newcommand{\Gotoh}[2]{%
+\newcommand{\Gotoh}{%
+  \gth@increment\gth@sn
+  \bgroup  % \egroup is in \gth@gotoh@pre
+  \@ifnextchar[{\gth@gotoh@setkeys}{\gth@gotoh@pre}}
+%    \end{macrocode}
+% \end{macro}
+%
+% \begin{macro}{\gth@gotoh@setkeys}
+% \begin{macro}{\gth@gotoh@pre}
+% These inner macros are for preparing: |\gth@gotoh@setkeys| process temporary
+% configuration specified with the optional argument of |\Gotoh|. In
+% |\gth@gotoh@pre|, if the boolean switch |\if@gth@uppercase| is true, the
+% arguments are processed by |\uppercase| preamble before passing them to
+% |\gth@gotoh| macro.
+%    \begin{macrocode}
+\def\gth@gotoh@setkeys[#1]{\setkeys[gth]{config}{#1}\gth@gotoh@pre}
+\def\gth@gotoh@pre#1#2{%
+  \edef\gth@tmpa{\noexpand\gth@gotoh{#1}{#2}}%
   \if@gth@uppercase
-    \uppercase{\gth@gotoh{#1}{#2}}%
+    \uppercase\expandafter{\gth@tmpa}%
   \else
-    \gth@gotoh{#1}{#2}%
-  \fi}
+    \gth@tmpa
+  \fi\egroup}
 %    \end{macrocode}
 % \end{macro}
+% \end{macro}
 %
 % \begin{macro}{\gth@gotoh}
-% This macro actually executes the Gotoh algorithm.~\cite{gotoh1982} The input
+% This macro actually executes the Gotoh algorithm~\cite{gotoh1982}. The input
 % of the algorithm is two biological sequences
 % \[
 % A \defeq a_1a_2a_3\dots a_m,\eqsep B \defeq b_1b_2b_3\dots b_n
@@ -462,39 +483,28 @@
 % calculation is done in $O(mn)$ time.} to get optimal score of the algorithm:
 % \begin{equation}
 % M_{i+1, j+1}
-%   = \max\left\{M_{ij}, {I_x}_{ij}, {I_y}_{ij}\right\} + c_{a_ib_j}
+%   = \max\left\{M_{ij}, I^x_{ij}, I^y_{ij}\right\} + c_{ij}
 % \label{eq:m}
 % \end{equation}
 % where
 % \begin{align}
-% {I_x}_{i+1, j} &= \max\left\{ M_{ij}-d, {I_x}_{ij}-e, {I_y}_{ij}-d \right\},
+% I^x_{i+1, j} &= \max\left\{ M_{ij}-d, I^x_{ij}-e, I^y_{ij}-d \right\},
 % \label{eq:ix} \\
-% {I_y}_{i, j+1} &= \max\left\{ M_{ij}-d, {I_y}_{ij}-e \right\},
+% I^y_{i, j+1} &= \max\left\{ M_{ij}-d, I^y_{ij}-e \right\},
 % \label{eq:iy}
 % \end{align}
-% and $c_{a_ib_j}$ is a score for a pair $(a_i, b_j)$, namely
+% and $c_{ij}$ is a score for a pair $(a_i, b_j)$, namely
 % \[
-% c_{a_ib_j} = \left\{
+% c_{ij} = \left\{
 %   \begin{array}{rll}
 %   1  & \text{if\enspace} a_i = b_j & \text{(match)} \\
 %   -1 & \text{otherwise} & \text{(mismatch)}. \\
 %   \end{array}
 % \right.
 % \]
-%
-%    \begin{macrocode}
-\def\gth@gotoh#1#2{%
-%    \end{macrocode}
-%
-% \subsubsection{Preparation}
-%
-% First, the `serial number' is incremented. The whole other part of this macro
-% contained in a group because a number of temporary macros are defined during
-% processing.
-%    \begin{macrocode}
-  \gth@increment\gth@sn
-  \bgroup
-%    \end{macrocode}
+% Note that the Equations (\ref{eq:ix}) and (\ref{eq:iy}) have asymmetric form
+% because the order of inserting \emph{gaps} when alternating $A$ and $B$ does
+% not affect the optimal score.
 %
 % \subsubsection{Getting sequences}
 %
@@ -504,18 +514,19 @@
 % |\gth@seqa@|$a_i$ and |\gth@seqa@|$b_j$, and the lengthes of the sequences
 % $m, n$ are stored in |\gth@m| and |\gth@n| respectively.
 %    \begin{macrocode}
-    \gth@tempcnta\z@
-    \@tfor\gth@member:=#1\do{%
-      \gth@name@edef{seqa@\the\gth@tempcnta}{\gth@member}%
-      \advance\gth@tempcnta\@ne}%
-    \advance\gth@tempcnta\@ne
-    \edef\gth@m{\the\gth@tempcnta}%
-    \gth@tempcntb\z@
-    \@tfor\gth@member:=#2\do{%
-      \gth@name@edef{seqb@\the\gth@tempcntb}{\gth@member}%
-      \advance\gth@tempcntb\@ne}%
-    \advance\gth@tempcntb\@ne
-    \edef\gth@n{\the\gth@tempcntb}%
+\def\gth@gotoh#1#2{%
+  \gth@tempcnta\z@
+  \@tfor\gth@member:=#1\do{%
+    \gth@name@edef{seqa@\the\gth@tempcnta}{\gth@member}%
+    \advance\gth@tempcnta\@ne}%
+  \advance\gth@tempcnta\@ne
+  \edef\gth@m{\the\gth@tempcnta}%
+  \gth@tempcntb\z@
+  \@tfor\gth@member:=#2\do{%
+    \gth@name@edef{seqb@\the\gth@tempcntb}{\gth@member}%
+    \advance\gth@tempcntb\@ne}%
+  \advance\gth@tempcntb\@ne
+  \edef\gth@n{\the\gth@tempcntb}%
 %    \end{macrocode}
 % \end{macro}
 % \end{macro}
@@ -523,127 +534,127 @@
 % \subsubsection{Initialization}
 %
 % We have to be careful with initialization because many implementations of the
-% Gotoh algorithm have problems here.~\cite{flouri2015} Specifically, the
+% Gotoh algorithm have problems here~\cite{flouri2015}. Specifically, the
 % package initialzes the matrxes with following equations:
 % \begin{align*}
 % M_{i0} &= -\infty, M_{0j} = -\infty, M_{00} = 0, \\
-% {I_x}_{i0} &= -g(i), {I_x}_{0j} = -\infty, \\
-% {I_y}_{i0} &= -\infty, {I_y}_{0j} = -g(j).
+% I^x_{i0} &= -g(i), I^x_{0j} = -\infty, \\
+% I^y_{i0} &= -\infty, I^y_{0j} = -g(j).
 % \end{align*}
-% Note that function $g(l)$ is a gap penalty (shown in equation~(\ref{eq:gap}))
+% Note that function $g(l)$ is a gap penalty (shown in Equation~(\ref{eq:gap}))
 % and can be calculated with the macro |\gth@gap@penalty|.
 %
 %    \begin{macrocode}
-    \gth@tempcnta\z@
-    \@whilenum\gth@tempcnta<\gth@m\do{%
-      \gth@gap@penalty{\gth@tempcnta}%
-      \gth@name@xdef{\gth@sn @m@\the\gth@tempcnta @0}{\gth@min}%
-      \gth@name@xdef{\gth@sn @ix@\the\gth@tempcnta @0}{\the\gth@calc}%
-      \gth@name@xdef{\gth@sn @iy@\the\gth@tempcnta @0}{\gth@min}%
-      \advance\gth@tempcnta\@ne}%
-    \gth@tempcntb\z@
-    \@whilenum\gth@tempcntb<\gth@n\do{%
-      \gth@gap@penalty{\gth@tempcntb}%
-      \gth@name@xdef{\gth@sn @m@0@\the\gth@tempcntb}{\gth@min}%
-      \gth@name@xdef{\gth@sn @ix@0@\the\gth@tempcntb}{\gth@min}%
-      \gth@name@xdef{\gth@sn @iy@0@\the\gth@tempcntb}{\the\gth@calc}%
-      \advance\gth@tempcntb\@ne}%
-    \gth@name@xdef{\gth@sn @m@0@0}{\number\z@}%
+  \gth@tempcnta\z@
+  \@whilenum\gth@tempcnta<\gth@m\do{%
+    \gth@gap@penalty{\gth@tempcnta}%
+    \gth@name@xdef{\gth@sn @m@\the\gth@tempcnta @0}{\gth@min}%
+    \gth@name@xdef{\gth@sn @ix@\the\gth@tempcnta @0}{\the\gth@calc}%
+    \gth@name@xdef{\gth@sn @iy@\the\gth@tempcnta @0}{\gth@min}%
+    \advance\gth@tempcnta\@ne}%
+  \gth@tempcntb\z@
+  \@whilenum\gth@tempcntb<\gth@n\do{%
+    \gth@gap@penalty{\gth@tempcntb}%
+    \gth@name@xdef{\gth@sn @m@0@\the\gth@tempcntb}{\gth@min}%
+    \gth@name@xdef{\gth@sn @ix@0@\the\gth@tempcntb}{\gth@min}%
+    \gth@name@xdef{\gth@sn @iy@0@\the\gth@tempcntb}{\the\gth@calc}%
+    \advance\gth@tempcntb\@ne}%
+  \gth@name@xdef{\gth@sn @m@0@0}{\number\z@}%
 %    \end{macrocode}
 %
 % \subsubsection{Memoization}
 %
 % If the switch |\if@gth@memoization| is true, memoization functions (See
-% section~\ref{sect:memofunc}) are called recursively.
+% section~\ref{sect:memofunc}) are called recursively. 
 %    \begin{macrocode}
-    \if@gth@memoization
-      \gth@decrement\gth@m \gth@decrement\gth@n
-        \gth@memo@ix{\gth@m}{\gth@n}%
-        \gth@memo@iy{\gth@m}{\gth@n}%
-        \gth@memo@m{\gth@m}{\gth@n}%
-      \gth@increment\gth@m \gth@increment\gth@n
+  \if@gth@memoization
+    \gth@decrement\gth@m \gth@decrement\gth@n
+      \gth@memo@ix{\gth@m}{\gth@n}%
+      \gth@memo@iy{\gth@m}{\gth@n}%
+      \gth@memo@m{\gth@m}{\gth@n}%
+    \gth@increment\gth@m \gth@increment\gth@n
 %    \end{macrocode}
 %
 % \subsubsection{Dynamic Programming}
 %
-% To fill matrxes $M$, $I_x$ and $I_y$ the package use the recurrence formula
+% To fill matrxes $M$, $I^x$, and $I^y$ the package use the recurrence formula
 %
 %    \begin{macrocode}
-    \else
-      \gth@tempcnta\@ne
-      \@whilenum\gth@tempcnta<\gth@m\do{%
-        \gth@tempcntb\@ne
-        \@whilenum\gth@tempcntb<\gth@n\do{%
-%    \end{macrocode}
-% First, $I_x$ is calculated with equation (\ref{eq:ix}).
-%    \begin{macrocode}
-          \advance\gth@tempcnta\m@ne
-            \gth@max{%
-              \gth@nameuse{\gth@sn @m@\the\gth@tempcnta
-                        @\the\gth@tempcntb},%
-              \gth@nameuse{\gth@sn @iy@\the\gth@tempcnta
-                        @\the\gth@tempcntb}}%
-            \gth@tempcntc\gth@calc
-            \gth@tempcntd
-              \gth@nameuse{\gth@sn @ix@\the\gth@tempcnta
-                        @\the\gth@tempcntb}%
-            \advance\gth@tempcntc-\gth@d\advance\gth@tempcntd-\gth@e
-          \advance\gth@tempcnta\@ne
-          \gth@max{\gth@tempcntc,\gth@tempcntd}%
-          \gth@name@xdef{\gth@sn @ix@\the\gth@tempcnta
-                         @\the\gth@tempcntb}{%
-            \the\gth@calc}%
-%    \end{macrocode}
-% Secondly, $I_y$ is calculated with equation (\ref{eq:iy}).
-%    \begin{macrocode}
-          \advance\gth@tempcntb\m@ne
-            \gth@tempcntc
-              \gth@nameuse{\gth@sn @m@\the\gth@tempcnta
-                        @\the\gth@tempcntb}%
-            \gth@tempcntd
-              \gth@nameuse{\gth@sn @iy@\the\gth@tempcnta
-                        @\the\gth@tempcntb}%
-            \advance\gth@tempcntc-\gth@d\advance\gth@tempcntd-\gth@e
-          \advance\gth@tempcntb\@ne
-          \gth@max{\gth@tempcntc,\gth@tempcntd}%
-          \gth@name@xdef{\gth@sn @iy@\the\gth@tempcnta
-                         @\the\gth@tempcntb}{%
-            \the\gth@calc}%
-%    \end{macrocode}
-% Finally, $M$ is calculated with equation (\ref{eq:m}) and a loop is completed.
-%    \begin{macrocode}
-          \advance\gth@tempcnta\m@ne\advance\gth@tempcntb\m@ne
-            \gth@max{%
-              \gth@nameuse{\gth@sn @m@\the\gth@tempcnta
-                        @\the\gth@tempcntb},%
-              \gth@nameuse{\gth@sn @ix@\the\gth@tempcnta
-                        @\the\gth@tempcntb},%
-              \gth@nameuse{\gth@sn @iy@\the\gth@tempcnta
-                        @\the\gth@tempcntb}}%
-            \edef\gth@tmpa{\gth@nameuse{seqa@\the\gth@tempcnta}}%
-            \edef\gth@tmpb{\gth@nameuse{seqb@\the\gth@tempcntb}}%
-          \advance\gth@tempcnta\@ne\advance\gth@tempcntb\@ne
-          \ifx\gth@tmpa\gth@tmpb
-            \advance\gth@calc\gth@match
-          \else
-            \advance\gth@calc\gth@mismatch
-          \fi
-          \gth@name@xdef{\gth@sn @m@\the\gth@tempcnta
-                         @\the\gth@tempcntb}{%
-            \the\gth@calc}%
-          \advance\gth@tempcntb\@ne}%
-        \advance\gth@tempcnta\@ne}%
-    \fi
+  \else
+    \gth@tempcnta\@ne
+    \@whilenum\gth@tempcnta<\gth@m\do{%
+      \gth@tempcntb\@ne
+      \@whilenum\gth@tempcntb<\gth@n\do{%
+%    \end{macrocode}
+% First, $I^x$ is calculated with Equation (\ref{eq:ix}).
+%    \begin{macrocode}
+        \advance\gth@tempcnta\m@ne
+          \gth@max{%
+            \gth@nameuse{\gth@sn @m@\the\gth@tempcnta
+                         @\the\gth@tempcntb},%
+            \gth@nameuse{\gth@sn @iy@\the\gth@tempcnta
+                         @\the\gth@tempcntb}}%
+          \gth@tempcntc\gth@calc
+          \gth@tempcntd
+            \gth@nameuse{\gth@sn @ix@\the\gth@tempcnta
+                         @\the\gth@tempcntb}%
+          \advance\gth@tempcntc-\gth@d\advance\gth@tempcntd-\gth@e
+        \advance\gth@tempcnta\@ne
+        \gth@max{\gth@tempcntc,\gth@tempcntd}%
+        \gth@name@xdef{\gth@sn @ix@\the\gth@tempcnta
+                       @\the\gth@tempcntb}{%
+          \the\gth@calc}%
+%    \end{macrocode}
+% Secondly, $I^y$ is calculated with Equation (\ref{eq:iy}).
+%    \begin{macrocode}
+        \advance\gth@tempcntb\m@ne
+          \gth@tempcntc
+            \gth@nameuse{\gth@sn @m@\the\gth@tempcnta
+                         @\the\gth@tempcntb}%
+          \gth@tempcntd
+            \gth@nameuse{\gth@sn @iy@\the\gth@tempcnta
+                         @\the\gth@tempcntb}%
+          \advance\gth@tempcntc-\gth@d\advance\gth@tempcntd-\gth@e
+        \advance\gth@tempcntb\@ne
+        \gth@max{\gth@tempcntc,\gth@tempcntd}%
+        \gth@name@xdef{\gth@sn @iy@\the\gth@tempcnta
+                       @\the\gth@tempcntb}{%
+          \the\gth@calc}%
+%    \end{macrocode}
+% Finally, $M$ is calculated with Equation (\ref{eq:m}) and a loop is completed.
+%    \begin{macrocode}
+        \advance\gth@tempcnta\m@ne\advance\gth@tempcntb\m@ne
+          \gth@max{%
+            \gth@nameuse{\gth@sn @m@\the\gth@tempcnta
+                         @\the\gth@tempcntb},%
+            \gth@nameuse{\gth@sn @ix@\the\gth@tempcnta
+                         @\the\gth@tempcntb},%
+            \gth@nameuse{\gth@sn @iy@\the\gth@tempcnta
+                         @\the\gth@tempcntb}}%
+          \edef\gth@tmpa{\gth@nameuse{seqa@\the\gth@tempcnta}}%
+          \edef\gth@tmpb{\gth@nameuse{seqb@\the\gth@tempcntb}}%
+        \advance\gth@tempcnta\@ne\advance\gth@tempcntb\@ne
+        \ifx\gth@tmpa\gth@tmpb
+          \advance\gth@calc\gth@match
+        \else
+          \advance\gth@calc\gth@mismatch
+        \fi
+        \gth@name@xdef{\gth@sn @m@\the\gth@tempcnta
+                       @\the\gth@tempcntb}{%
+          \the\gth@calc}%
+        \advance\gth@tempcntb\@ne}%
+      \advance\gth@tempcnta\@ne}%
+  \fi
 %    \end{macrocode}
 %
-% \subsubsection{Printing Matrixes}
+% \subsubsection{Printing Matrices}
 %
 % This is piece of code for debugging the package (so usually commented out).
 %
 %    \begin{macrocode}
-    %\gth@print@matrix{m}%
-    %\gth@print@matrix{ix}%
-    %\gth@print@matrix{iy}%
+  %\gth@print@matrix{m}%
+  %\gth@print@matrix{ix}%
+  %\gth@print@matrix{iy}%
 %    \end{macrocode}
 %
 % \subsubsection{Returning the Optimal Score}
@@ -651,20 +662,90 @@
 % The calculated optimal score of the alignment stored here to the control
 % sequences which stored in |\gth@score|.
 %    \begin{macrocode}
-    \bgroup
-      \gth@decrement\gth@m \gth@decrement\gth@n
-      \expandafter\xdef\gth@score{%
-        \gth@nameuse{\gth@sn @m@\gth@m @\gth@n}}%
-    \egroup
+  \bgroup
+    \gth@decrement\gth@m \gth@decrement\gth@n
+    \expandafter\xdef\gth@score{%
+      \gth@nameuse{\gth@sn @m@\gth@m @\gth@n}}%
+  \egroup
 %    \end{macrocode}
 %
 % \subsubsection{Trace Back}
 %
+% After processing dynamic programming (or memoization functions), matrices
+% $M$, $I^x$, and $I^y$ are all filled. Using these matrices, we can determine
+% the `trace' from the optimal score $M_{m,n}$ to the start $M_{0,0}$ and get
+% the result of alignment $(x, y)$.
+%
+% Considering the form of Equation (\ref{eq:m})--(\ref{eq:iy}), the calculation
+% formulae of the former values depend on which matrix the `current position'
+% exists. In order to take into account these differences, trace back process
+% is calculated while switching three modes: default, gap x, and gap y.
+%
+% First, make sure to empty |\gth@rseq@x| and |\gth@rseq@y| which is going to
+% store result alignment sequences $x$ and $y$ respectively. Note that this is
+% the trace \emph{back} process, so new characters are prepended to the
+% existing sequences in each loop. In the next line, the switches
+% |\if@gth@gapx@| and |\if@gth@gapy@| are both turned off (which means
+% processing starts from the default mode).
 %    \begin{macrocode}
-    \let\gth@rseq@x\@empty\let\gth@rseq@y\@empty\let\gth@mode@seq\@empty
-    \@gth@remain@true\@gth@gapx@false\@gth@gapy@false
-    \@whilesw\if@gth@remain@\fi{%
-      \ifnum\gth@m=\z@
+  \let\gth@rseq@x\@empty\let\gth@rseq@y\@empty
+  \@gth@remain@true\@gth@gapx@false\@gth@gapy@false
+%    \end{macrocode}
+% In the main loop of trace back, process the condition either $x$ or $y$ is
+% already completed first. In this situation, the other sequence should be
+% filled all the remaining with \emph{gaps}.
+%    \begin{macrocode}
+  \@whilesw\if@gth@remain@\fi{%
+    \ifnum\gth@m=\z@
+      \gth@decrement\gth@n
+      \expandafter\expandafter\expandafter
+      \ifx\gth@nameuse{seqb@\gth@n}\relax\else
+        \edef\gth@rseq@x{\gth@gap@char\gth@rseq@x}%
+        \edef\gth@rseq@y{\gth@nameuse{seqb@\gth@n}%
+                         \gth@rseq@y}%
+      \fi
+    \else\ifnum\gth@n=\z@
+      \gth@decrement\gth@m
+      \expandafter\expandafter\expandafter
+      \ifx\gth@nameuse{seqa@\gth@m}\relax\else
+        \edef\gth@rseq@x{\gth@nameuse{seqa@\gth@m}%
+                         \gth@rseq@x}%
+        \edef\gth@rseq@y{\gth@gap@char\gth@rseq@y}%
+      \fi
+    \else
+%    \end{macrocode}
+% \paragraph{mode: gap x}
+% Prepend former base to $x$ and a \emph{gap} to $y$. If
+% $M_{m-1,n}-d>I^x_{m-1,n}-e$ back to default mode. Else if
+% $I^x_{m-1,n}-e<I^y_{m-1,n}-d$ switch to mode gap y and otherwise stay in mode
+% gap x.
+%    \begin{macrocode}
+      \if@gth@gapx@
+        \gth@decrement\gth@m
+        \expandafter\expandafter\expandafter
+        \ifx\gth@nameuse{seqa@\gth@m}\relax\else
+          \edef\gth@rseq@x{\gth@nameuse{seqa@\gth@m}%
+                           \gth@rseq@x}%
+          \edef\gth@rseq@y{\gth@gap@char\gth@rseq@y}%
+        \fi
+        \gth@tempcnta\gth@nameuse{\gth@sn @m@\gth@m @\gth@n}%
+        \gth@tempcntb\gth@nameuse{\gth@sn @ix@\gth@m @\gth@n}%
+        \gth@tempcntc\gth@nameuse{\gth@sn @iy@\gth@m @\gth@n}%
+        \advance\gth@tempcnta-\gth@d
+        \advance\gth@tempcntb-\gth@e
+        \advance\gth@tempcntc-\gth@d
+        \ifnum\gth@tempcnta>\gth@tempcntb
+          \@gth@gapx@false
+        \else\ifnum\gth@tempcntb<\gth@tempcntc
+          \@gth@gapx@false\@gth@gapy@true
+        \fi\fi
+%    \end{macrocode}
+% \paragraph{mode: gap y}
+% Prepend a \emph{gap} to $x$ and former base to $y$. If
+% $M_{m,n-1}-d>I^y_{m,n-1}-e$ back to default mode and otherwise stay in mode
+% gap y.
+%    \begin{macrocode}
+      \else\if@gth@gapy@
         \gth@decrement\gth@n
         \expandafter\expandafter\expandafter
         \ifx\gth@nameuse{seqb@\gth@n}\relax\else
@@ -672,82 +753,53 @@
           \edef\gth@rseq@y{\gth@nameuse{seqb@\gth@n}%
                            \gth@rseq@y}%
         \fi
-      \else\ifnum\gth@n=\z@
+        \gth@tempcnta\gth@nameuse{\gth@sn @m@\gth@m @\gth@n}%
+        \gth@tempcntb\gth@nameuse{\gth@sn @iy@\gth@m @\gth@n}%
+        \advance\gth@tempcnta-\gth@d\advance\gth@tempcntb-\gth@e
+        \ifnum\gth@tempcnta>\gth@tempcntb
+          \@gth@gapy@false
+        \fi
+%    \end{macrocode}
+% \paragraph{mode: default}
+% Prepend former base to $x$ and $y$ respectively. Only if
+% $M_{m-1,n-1}>I^x_{m-1,n-1}$ and $M_{m-1,n-1}>I^y_{m-1,n-1}$ stay on default
+% mode, and else if $I^x_{m-1,n-1}>I^y_{n-1,m-1}$ go to gap x otherwise go to
+% gap y.
+%    \begin{macrocode}
+      \else
         \gth@decrement\gth@m
+        \gth@decrement\gth@n
         \expandafter\expandafter\expandafter
         \ifx\gth@nameuse{seqa@\gth@m}\relax\else
-          \edef\gth@rseq@x{\gth@nameuse{seqa@\gth@m}%
-                           \gth@rseq@x}%
-          \edef\gth@rseq@y{\gth@gap@char\gth@rseq@y}%
-        \fi
-      \else
-        \if@gth@gapx@
-          % mode: gap x
-          \gth@decrement\gth@m
           \expandafter\expandafter\expandafter
-          \ifx\gth@nameuse{seqa@\gth@m}\relax\else
+          \ifx\gth@nameuse{seqb@\gth@n}\relax\else
             \edef\gth@rseq@x{\gth@nameuse{seqa@\gth@m}%
                              \gth@rseq@x}%
-            \edef\gth@rseq@y{\gth@gap@char\gth@rseq@y}%
-          \fi
-          \gth@tempcnta\gth@nameuse{\gth@sn @m@\gth@m @\gth@n}%
-          \gth@tempcntb\gth@nameuse{\gth@sn @ix@\gth@m @\gth@n}%
-          \gth@tempcntc\gth@nameuse{\gth@sn @iy@\gth@m @\gth@n}%
-          \advance\gth@tempcnta-\gth@d
-          \advance\gth@tempcntb-\gth@e
-          \advance\gth@tempcntc-\gth@d
-          \ifnum\gth@tempcnta>\gth@tempcntb
-            \@gth@gapx@false
-          \else\ifnum\gth@tempcntb<\gth@tempcntc
-            \@gth@gapx@false\@gth@gapy@true
-          \fi\fi
-        \else\if@gth@gapy@
-          % mode: gap y
-          \gth@decrement\gth@n
-          \expandafter\expandafter\expandafter
-          \ifx\gth@nameuse{seqb@\gth@n}\relax\else
-            \edef\gth@rseq@x{\gth@gap@char\gth@rseq@x}%
             \edef\gth@rseq@y{\gth@nameuse{seqb@\gth@n}%
                              \gth@rseq@y}%
           \fi
-          \gth@tempcnta\gth@nameuse{\gth@sn @m@\gth@m @\gth@n}%
-          \gth@tempcntb\gth@nameuse{\gth@sn @iy@\gth@m @\gth@n}%
-          \advance\gth@tempcnta-\gth@d\advance\gth@tempcntb-\gth@e
-          \ifnum\gth@tempcnta>\gth@tempcntb
-            \@gth@gapy@false
-          \fi
-        \else
-          % mode: default
-          \gth@decrement\gth@m
-          \gth@decrement\gth@n
-          \expandafter\expandafter\expandafter
-          \ifx\gth@nameuse{seqa@\gth@m}\relax\else
-            \expandafter\expandafter\expandafter
-            \ifx\gth@nameuse{seqb@\gth@n}\relax\else
-              \edef\gth@rseq@x{\gth@nameuse{seqa@\gth@m}%
-                               \gth@rseq@x}%
-              \edef\gth@rseq@y{\gth@nameuse{seqb@\gth@n}%
-                               \gth@rseq@y}%
-            \fi
-          \fi
-          \gth@tempcnta\gth@nameuse{\gth@sn @m@\gth@m @\gth@n}%
-          \gth@tempcntb\gth@nameuse{\gth@sn @ix@\gth@m @\gth@n}%
-          \gth@tempcntc\gth@nameuse{\gth@sn @iy@\gth@m @\gth@n}%
-          \@gth@gap@false
-          \ifnum\gth@tempcnta<\gth@tempcntb\@gth@gap@true\fi
-          \ifnum\gth@tempcnta<\gth@tempcntc\@gth@gap@true\fi
-          \if@gth@gap@
-            \ifnum\gth@tempcntb>\gth@tempcntc
-              \@gth@gapx@true
-            \else
-              \@gth@gapy@true
-            \fi
+        \fi
+        \gth@tempcnta\gth@nameuse{\gth@sn @m@\gth@m @\gth@n}%
+        \gth@tempcntb\gth@nameuse{\gth@sn @ix@\gth@m @\gth@n}%
+        \gth@tempcntc\gth@nameuse{\gth@sn @iy@\gth@m @\gth@n}%
+        \@gth@gap@false
+        \ifnum\gth@tempcnta<\gth@tempcntb\@gth@gap@true\fi
+        \ifnum\gth@tempcnta<\gth@tempcntc\@gth@gap@true\fi
+        \if@gth@gap@
+          \ifnum\gth@tempcntb>\gth@tempcntc
+            \@gth@gapx@true
+          \else
+            \@gth@gapy@true
           \fi
-        \fi\fi
+        \fi
       \fi\fi
-      \ifnum\gth@m<\@ne\ifnum\gth@n<\@ne
-        \@gth@remain@false
-      \fi\fi}%
+    \fi\fi
+%    \end{macrocode}
+% Finally, if we achieve to $M_{0,0}$, exit from the main loop.
+%    \begin{macrocode}
+    \ifnum\gth@m<\@ne\ifnum\gth@n<\@ne
+      \@gth@remain@false
+    \fi\fi}%
 %    \end{macrocode}
 %
 % \subsubsection{Returning Results}
@@ -756,9 +808,8 @@
 % |\gth@resq@y| are copied globally to the control sequences which stored in
 % |\gth@resulta| and |\gth@resultb|.
 %    \begin{macrocode}
-    \expandafter\gth@glet\gth@resulta\gth@rseq@x
-    \expandafter\gth@glet\gth@resultb\gth@rseq@y
-  \egroup}
+  \expandafter\gth@glet\gth@resulta\gth@rseq@x
+  \expandafter\gth@glet\gth@resultb\gth@rseq@y}
 %    \end{macrocode}
 % \end{macro}
 %
@@ -767,14 +818,17 @@
 % \begin{macro}{\gth@memo@ix}
 % \begin{macro}{\gth@memo@iy}
 % \begin{macro}{\gth@memo@m}
-% These are memoization functions for calculating $I_x, I_y, M$ respectively.
+% These are memoization functions for calculating $I^x, I^y, M$ respectively.
+% Since these functions change many `temporary' values, all of the processes
+% are wrapped in a group and only the return values and components of matrices
+% are assigned globally.
 %    \begin{macrocode}
 \def\gth@memo@ix#1#2{%
   \bgroup
     \gth@tempcnta#1\gth@tempcntb#2\relax
     \expandafter\expandafter\expandafter
     \ifx\gth@nameuse{\gth@sn @ix@\the\gth@tempcnta
-                  @\the\gth@tempcntb}\relax
+                     @\the\gth@tempcntb}\relax
       \advance\gth@tempcnta\m@ne
         \gth@memo@ix{\gth@tempcnta}{\gth@tempcntb}%
         \edef\gth@tmp@ix@return{\gth@ix@return}%
@@ -800,7 +854,7 @@
     \gth@tempcnta#1\gth@tempcntb#2\relax
     \expandafter\expandafter\expandafter
     \ifx\gth@nameuse{\gth@sn @iy@\the\gth@tempcnta
-                  @\the\gth@tempcntb}\relax
+                     @\the\gth@tempcntb}\relax
       \advance\gth@tempcntb\m@ne
         \gth@memo@iy{\gth@tempcnta}{\gth@tempcntb}%
         \edef\gth@tmp@iy@return{\gth@iy@return}%
@@ -823,7 +877,7 @@
     \gth@tempcnta#1\gth@tempcntb#2\relax
     \expandafter\expandafter\expandafter
     \ifx\gth@nameuse{\gth@sn @m@\the\gth@tempcnta
-                  @\the\gth@tempcntb}\relax
+                     @\the\gth@tempcntb}\relax
       \advance\gth@tempcnta\m@ne\advance\gth@tempcntb\m@ne
         \gth@memo@ix{\gth@tempcnta}{\gth@tempcntb}%
         \edef\gth@tmp@ix@return{\gth@ix@return}%