Debian Codegraph @

texmf-dist/source/latex/gotoh/gotoh.dtx

raw
1 % ^^A -*- latex -*-
2 % \iffalse meta-comment
3 %
4 % This is file `gotoh.dtx'.
5 %
6 % Copyright (c) 2017 Takuto ASAKURA (wtsnjp)
7 % GitHub: https://github.com/wtsnjp
8 % Twitter: @wtsnjp
9 %
10 % This package is distributed under the MIT License.
11 %
12 % \fi
13 %
14 % \CheckSum{984}
15 %
16 % \changes{v1.0}{2017/05/05}{The first version}
17 %
18 % \iffalse
19 %<*package>
20 \NeedsTeXFormat{LaTeX2e}
21 \ProvidesPackage{gotoh}[2017/07/07 v1.1 Sequence alignment algorithm]
22 %</package>
23 %<*driver>
24 \documentclass[draft]{ltxdoc}
25 \usepackage{amsmath}
26 \usepackage{enumitem}
27 \usepackage{gotoh}
28 \EnableCrossrefs
29 \CodelineIndex
30 \RecordChanges
31 \setlength\hfuzz{15pt}
32 \hbadness=7000
33 \newcommand{\pkgName}[1]{\textsf{#1}}
34 \newcommand{\pkgGotoh}{\pkgName{Gotoh}}
35 \newcommand{\synKey}[1]{\texttt{#1}}
36 \newcommand{\synOr}{\quad or\quad}
37 \newcommand{\synBool}{\meta{\normalfont\texttt{true\textbar false}}}
38 \newcommand{\defeq}{\equiv}
39 \newcommand{\eqsep}{\;}
40 \setlist[description]{font={\normalfont}}
41 \begin{document}
42 \DocInput{gotoh.dtx}
43 \end{document}
44 %</driver>
45 % \fi
46 %
47 % \CharacterTable
48 % {Upper-case \A\B\C\D\E\F\G\H\I\J\K\L\M\N\O\P\Q\R\S\T\U\V\W\X\Y\Z
49 % Lower-case \a\b\c\d\e\f\g\h\i\j\k\l\m\n\o\p\q\r\s\t\u\v\w\x\y\z
50 % Digits \0\1\2\3\4\5\6\7\8\9
51 % Exclamation \! Double quote \" Hash (number) \#
52 % Dollar \$ Percent \% Ampersand \&
53 % Acute accent \' Left paren \( Right paren \)
54 % Asterisk \* Plus \+ Comma \,
55 % Minus \- Point \. Solidus \/
56 % Colon \: Semicolon \; Less than \<
57 % Equals \= Greater than \> Question mark \?
58 % Commercial at \@ Left bracket \[ Backslash \\
59 % Right bracket \] Circumflex \^ Underscore \_
60 % Grave accent \` Left brace \{ Vertical bar \|
61 % Right brace \} Tilde \~}
62 %
63 % \GetFileInfo{gotoh.sty}
64 %
65 % \DoNotIndex{%
66 % \@empty,\@ne,\\,\advance,\bgroup,\csname,\def,\do,\edef,\egroup,\else,%
67 % \endcsname,\expandafter,\fi,\global,\hbox,\hss,\ht,\let,\m@ne,\mbox,%
68 % \multiply,\newcommand,\newcount,\newdimen,\newif,\number,\PackageError,%
69 % \PackageWarningNoLine,\relax,\RequirePackage,\sbox,\texttt,\the,\xdef,\z@}
70 %
71 % \title{The {\pkgGotoh} package}
72 % \author{Takuto ASAKURA (wtsnjp)}
73 % \date{{\fileversion} [\filedate]}
74 % \maketitle
75 %
76 % \MakeShortVerb{\|}
77 %
78 % \begin{abstract}
79 % This package is an implementation in {\TeX} of the Gotoh algorithm, which
80 % calculates biological sequence alignments. The package provides only two user
81 % commands: |\Gotoh| for executing the algorithm and |\GotohConfig| for setting
82 % various parameters with a key-value list.
83 % \end{abstract}
84 %
85 % ^^A\tableofcontents
86 %
87 % \section{System Requirements}
88 %
89 % System requirements of {\pkgGotoh} are shown bellow.
90 % \begin{itemize}
91 % \item {\TeX} engine: any engine
92 % \item {\TeX} format: {\LaTeXe}
93 % \item Document class: any class
94 % \item Required package: \pkgName{xkeyval}
95 % \end{itemize}
96 %
97 % \section{Loading the {\pkgGotoh} Package}
98 %
99 % To use the {\pkgGotoh} package, load |gotoh.sty| with |\usepackage| command
100 % in preamble. No package option is available.
101 % \begin{quote}
102 % |\usepackage{gotoh}|
103 % \end{quote}
104 %
105 % \section{Calculating the Alignment}
106 %
107 % \DescribeMacro{\Gotoh}
108 % The syntax of |\Gotoh| is shown below.
109 % \begin{quote}
110 % |\Gotoh|\oarg{key-value list}\marg{sequence A}\marg{sequence B}
111 % \end{quote}
112 % The command puts the optimal score of the alignment to specified control
113 % sequence (default: |\GotohScore|) after executing the Gotoh algorithm, and
114 % returns the alignment results to other control sequences (default:
115 % |\GotohResultA| and |\GotohResultB|). Note that these assignments are done
116 % globally. Using the optional argument, you can change the configuration
117 % temporary with the same keys in |\GotohConfig| (see the next section).
118 %
119 % \section{Configuration}
120 %
121 % \DescribeMacro{\GotohConfig}
122 % You can change various settings and parameters related to this package with
123 % |\GotohConfig| command. The command takes a key-value list of the settings as
124 % its argument and changes the values locally.
125 % \begin{quote}
126 % |\GotohConfig|\marg{key-value list}
127 % \end{quote}
128 %
129 % \subsection{Control Sequences to Store Results}
130 %
131 % \DescribeMacro{\GotohScore}
132 % \DescribeMacro{\GotohResultA}
133 % \DescribeMacro{\GotohResultB}
134 % Control sequences which |\Gotoh| command return results can be specified with
135 % following keys:
136 %
137 % \begin{description}
138 % \item[\synKey{score} |=| \meta{control sequence}]\hfill |\GotohScore| \\
139 % sets the control sequence to store optimal score of the last alignment
140 % which calculated by |\Gotoh| command.
141 % \item[\synKey{result A} |=| \meta{control sequence}]\hfill |\GotohResultA|
142 % \item[\synKey{result B} |=| \meta{control sequence}]\hfill |\GotohResultB| \\
143 % specify the control sequences to store alignment results respectively
144 % corresponding to \meta{sequence A} and \meta{sequence B} of the arguments
145 % of |\Gotoh|.
146 % \end{description}
147 %
148 % \subsection{Algorithm Parameters}
149 %
150 % The default value of algorithm parameters which define the scoring are
151 % \begin{equation}
152 % \mathrm{match} = 1,\eqsep \mathrm{mismatch} = -1,\eqsep d = 7,\eqsep e= 1.
153 % \label{eq:parameters}
154 % \end{equation}
155 % Parameters $\mathrm{match}, \mathrm{mismatch}$ define the penalties of a
156 % \emph{match} and \emph{mismatch} respectively, and $d, e$ are used in a gap
157 % penalty (see section \ref{sect:calc}). The parameters appeared in the above
158 % equations are able to be changed with following keys:
159 %
160 % \begin{description}
161 % \item[\synKey{match} |=| \meta{number}]\hfill |1|
162 % \item[\synKey{mismatch} |=| \meta{number}]\hfill |-1|
163 % \item[\synKey{d} |=| \meta{number}]\hfill |7|
164 % \item[\synKey{e} |=| \meta{number}]\hfill |1| \\
165 % set the parameters appear in the above equations.
166 % \end{description}
167 %
168 % Though the |\Gotoh| command calculates sequence alignment with standard
169 % dynamic programming as default, you can use memoization functions instead.
170 % Note that both of the methods produce exactly the same results.
171 %
172 % \begin{description}
173 % \item[\synKey{memoization} |=| \synBool \synOr \synKey{memoization}]\hfill |false| \\
174 % If true, use memoization functions to execute the Gotoh algorithm.
175 % \end{description}
176 %
177 % \subsection{Others}
178 %
179 % \begin{description}
180 % \item[\synKey{gap char} |=| \meta{character}]\hfill |.| (period) \\
181 % is inserted to the alignment results where gaps appear. Note that you have
182 % to be careful if using |-| (hyphen) as gap characters because successive
183 % hyphens automatically converted to dashes by {\TeX}. In this case, you can
184 % specify |\mbox{-}| instead.
185 % \item[\synKey{uppercase} |=| \synBool \synOr \synKey{uppercase}]\hfill |false| \\
186 % If true, uppercase both \meta{sequence A} and \meta{sequence B} before
187 % executing the algorithm.
188 % \end{description}
189 %
190 % \StopEventually{\PrintIndex\PrintChanges}
191 %
192 % \section{Algorithm and Implementation}
193 %
194 % \subsection{Required package}
195 %
196 % Package \pkgName{xkeyval} is required to process key-value lists.
197 % \begin{macrocode}
198 \RequirePackage{xkeyval}
199 % \end{macrocode}
200 %
201 % \subsection{Messages}
202 %
203 % \begin{macro}{\gth@warn}
204 % \begin{macro}{\gth@error}
205 % Commands for warning and error messages.
206 % \begin{macrocode}
207 \def\gth@pkgname{gotoh}
208 \def\gth@warn{\PackageWarningNoLine\gth@pkgname}
209 \def\gth@error{\PackageError\gth@pkgname}
210 % \end{macrocode}
211 % \end{macro}
212 % \end{macro}
213 %
214 % \subsection{Switches, Registers and Constants}
215 %
216 % All boolean switches, count registers and dimen registers used by this
217 % package are declared here.
218 %
219 % \begin{macro}{\if@gth@first@}
220 % \begin{macro}{\if@gth@renain@}
221 % \begin{macro}{\if@gth@gap@}
222 % \begin{macro}{\if@gth@gapx@}
223 % \begin{macro}{\if@gth@gapy@}
224 % A switch |\if@gth@first@| is for a calculation command |\gth@max|, and the
225 % other switches are for trace back (in macro |\gth@gotoh|).
226 % \begin{macrocode}
227 \newif\if@gth@first@
228 \newif\if@gth@remain@
229 \newif\if@gth@gap@
230 \newif\if@gth@gapx@
231 \newif\if@gth@gapy@
232 % \end{macrocode}
233 % \end{macro}
234 % \end{macro}
235 % \end{macro}
236 % \end{macro}
237 % \end{macro}
238 %
239 % \begin{macro}{\gth@tempcnta}
240 % \begin{macro}{\gth@tempcntb}
241 % \begin{macro}{\gth@tempcntc}
242 % \begin{macro}{\gth@tempcntd}
243 % \begin{macro}{\gth@calc}
244 % Scratch four count registers for general use and one for some calculation
245 % routines.
246 % \begin{macrocode}
247 \newcount\gth@tempcnta
248 \newcount\gth@tempcntb
249 \newcount\gth@tempcntc
250 \newcount\gth@tempcntd
251 \newcount\gth@calc
252 % \end{macrocode}
253 % \end{macro}
254 % \end{macro}
255 % \end{macro}
256 % \end{macro}
257 % \end{macro}
258 %
259 % \begin{macro}{\gth@sn}
260 % This is \emph{not} a counter register but a macro to store \meta{number}
261 % which is used as `serial number'.
262 % \begin{macrocode}
263 \edef\gth@sn{\number\z@}
264 % \end{macrocode}
265 % \end{macro}
266 %
267 % \begin{macro}{\gth@min}
268 % This macro stores a large negative \meta{number} which is used instead of
269 % $-\infty$. Here |\gth@M| is a largest constant which can be defined by
270 % |\mathchardef| primitive (in traditional {\TeX} engine).
271 % \begin{macrocode}
272 \mathchardef\gth@M="7FFF
273 \edef\gth@min{-\number\gth@M}
274 % \end{macrocode}
275 % \end{macro}
276 %
277 % \begin{macro}{\gth@tempdima}
278 % Scratch a dimen register for general use.
279 % \begin{macrocode}
280 \newdimen\gth@tempdima
281 % \end{macrocode}
282 % \end{macro}
283 %
284 % \subsection{Defining and Setting Keys}
285 %
286 % \begin{macro}{\gth@match}
287 % \begin{macro}{\gth@mismatch}
288 % \begin{macro}{\gth@d}
289 % \begin{macro}{\gth@e}
290 % These are keys for setting the parameters of the algorithm. The default
291 % values which are shown in Equations~(\ref{eq:parameters}) are set here, and
292 % stored in the macros (\emph{not} count registers) respectively.
293 % \begin{macrocode}
294 \define@cmdkeys[gth]{config}[gth@]{match, mismatch, d, e}
295 \setkeys[gth]{config}{match=1, mismatch=-1, d=7, e=1}
296 % \end{macrocode}
297 % \end{macro}
298 % \end{macro}
299 % \end{macro}
300 % \end{macro}
301 %
302 % \begin{macro}{\gth@score}
303 % \begin{macro}{\gth@resulta}
304 % \begin{macro}{\gth@resultb}
305 % The macros to store the result of the algorithms are also stored in internal
306 % macros.
307 % \begin{macrocode}
308 \define@key[gth]{config}{score}{\def\gth@score{#1}}
309 \define@key[gth]{config}{result A}{\def\gth@resulta{#1}}
310 \define@key[gth]{config}{result B}{\def\gth@resultb{#1}}
311 \setkeys[gth]{config}{
312 score=\GotohScore, result A=\GotohResultA, result B=\GotohResultB}
313 % \end{macrocode}
314 % \end{macro}
315 % \end{macro}
316 % \end{macro}
317 %
318 % \begin{macro}{\if@gth@memoization}
319 % \begin{macro}{\if@gth@uppercase}
320 % \begin{macro}{\gth@gap@char}
321 % Both boolean keys |\if@gth@memoization| and |\if@gth@uppercase| are set false
322 % as default. The gap char is stored in |\gth@gap@char|.
323 % \begin{macrocode}
324 \define@boolkeys[gth]{config}[@gth@]{memoization, uppercase}[true]
325 \define@key[gth]{config}{gap char}{\def\gth@gap@char{#1}}
326 \setkeys[gth]{config}{memoization=false, uppercase=false, gap char={.}}
327 % \end{macrocode}
328 % \end{macro}
329 % \end{macro}
330 % \end{macro}
331 %
332 % \subsection{Utility Commands}
333 %
334 % \begin{macro}{\gth@nameuse}
335 % \begin{macro}{\gth@name@edef}
336 % \begin{macro}{\gth@name@xdef}
337 % \begin{macro}{\gth@glet}
338 % Some primitives to use, define or copy control sequences are wrapped.
339 % \begin{macrocode}
340 \def\gth@nameuse#1{\csname gth@#1\endcsname}
341 \def\gth@name@edef#1{\expandafter\edef\csname gth@#1\endcsname}
342 \def\gth@name@xdef#1{\expandafter\xdef\csname gth@#1\endcsname}
343 \def\gth@glet{\global\let}
344 % \end{macrocode}
345 % \end{macro}
346 % \end{macro}
347 % \end{macro}
348 % \end{macro}
349 %
350 % \begin{macro}{\gth@advance}
351 % \begin{macro}{\gth@increment}
352 % \begin{macro}{\gth@decrement}
353 % Commands to treate macros which store \meta{number} like count registers.
354 % \begin{macrocode}
355 \def\gth@advance#1#2{%
356 \gth@calc#1\advance\gth@calc#2\edef#1{\the\gth@calc}}
357 \def\gth@increment#1{\gth@advance#1\@ne}
358 \def\gth@decrement#1{\gth@advance#1\m@ne}
359 % \end{macrocode}
360 % \end{macro}
361 % \end{macro}
362 % \end{macro}
363 %
364 % \subsection{Calculation Routines}\label{sect:calc}
365 %
366 % Since these calculation routines (macros) are \emph{not} full expandable, all
367 % commands defined here return the results by storing the value in the counter
368 % register |\gth@calc|. This assignments are done locally.
369 %
370 % \begin{macro}{\gth@max}
371 % This command take comma-separated list of \meta{number} and returns the max
372 % value of them.
373 % \begin{macrocode}
374 \def\gth@max#1{%
375 \@gth@first@true
376 \@for\gth@member:=#1\do{%
377 \if@gth@first@
378 \gth@calc\gth@member
379 \@gth@first@false
380 \else
381 \ifnum\gth@member>\gth@calc
382 \gth@calc\gth@member
383 \fi
384 \fi}}
385 % \end{macrocode}
386 % \end{macro}
387 %
388 % \begin{macro}{\gth@gap@penalty}
389 % This command takes $l$, the length of a \emph{gap}, as its argument and
390 % calculates its penalty which defined by following function\footnote{This form
391 % of gap penalty is called `Affine gaps'.}:
392 % \begin{equation}
393 % g(l) = -d - (l-1)e. \label{eq:gap}
394 % \end{equation}
395 % In this equation, $d$ and $e$ are parameters of the algorithm, which have
396 % default values shown in Equations~(\ref{eq:parameters}).
397 % \begin{macrocode}
398 \def\gth@gap@penalty#1{%
399 \gth@calc#1\relax
400 \advance\gth@calc\m@ne
401 \multiply\gth@calc-\gth@e
402 \advance\gth@calc-\gth@d}
403 % \end{macrocode}
404 % \end{macro}
405 %
406 % \subsection{Printing Matrices}
407 %
408 % \begin{macro}{\gth@print@matrix}
409 % This command shows the matrices $M$, $I^x$ or $I^y$ (See
410 % section~\ref{sect:algorithm}). The argument of this macro specifies which
411 % matrix to show, so you can detect |m|, |ix|, or |iy|. However, this macro is
412 % currently only for the author of this package to debug.
413 % \begin{macrocode}
414 \def\gth@tab#1{%
415 \bgroup
416 \sbox\z@ 0%
417 \expandafter\gth@tempdima\ht\z@
418 \multiply\gth@tempdima 8%
419 \mbox{\hbox to\gth@tempdima{\hss #1}}%
420 \egroup}
421 \def\gth@print@matrix#1{%
422 \bgroup\ttfamily
423 #1:\\
424 \gth@tempcnta\z@
425 \@whilenum\gth@tempcnta<\gth@m\do{%
426 \gth@tempcntb\z@
427 \@whilenum\gth@tempcntb<\gth@n\do{%
428 \gth@tab{%
429 \gth@nameuse{\gth@sn @#1@\the\gth@tempcnta
430 @\the\gth@tempcntb}}%
431 \advance\gth@tempcntb\@ne}\\
432 \advance\gth@tempcnta\@ne}%
433 \egroup}
434 % \end{macrocode}
435 % \end{macro}
436 %
437 % \subsection{Executing the Gotoh Algorithm}\label{sect:algorithm}
438 %
439 % \begin{macro}{\Gotoh}
440 % \changes{v1.1}{2017/07/07}{Add a new optional argument for changing
441 % config temporary}
442 % This is the user interface to execute the Gotoh algorithm. First, the
443 % `serial number' is incremented. The whole other process executed by this
444 % macro contained in a group because a number of temporary macros are defined
445 % during processing.
446 % \begin{macrocode}
447 \newcommand{\Gotoh}{%
448 \gth@increment\gth@sn
449 \bgroup % \egroup is in \gth@gotoh@pre
450 \@ifnextchar[{\gth@gotoh@setkeys}{\gth@gotoh@pre}}
451 % \end{macrocode}
452 % \end{macro}
453 %
454 % \begin{macro}{\gth@gotoh@setkeys}
455 % \begin{macro}{\gth@gotoh@pre}
456 % These inner macros are for preparing: |\gth@gotoh@setkeys| process temporary
457 % configuration specified with the optional argument of |\Gotoh|. In
458 % |\gth@gotoh@pre|, if the boolean switch |\if@gth@uppercase| is true, the
459 % arguments are processed by |\uppercase| preamble before passing them to
460 % |\gth@gotoh| macro.
461 % \begin{macrocode}
462 \def\gth@gotoh@setkeys[#1]{\setkeys[gth]{config}{#1}\gth@gotoh@pre}
463 \def\gth@gotoh@pre#1#2{%
464 \edef\gth@tmpa{\noexpand\gth@gotoh{#1}{#2}}%
465 \if@gth@uppercase
466 \uppercase\expandafter{\gth@tmpa}%
467 \else
468 \gth@tmpa
469 \fi\egroup}
470 % \end{macrocode}
471 % \end{macro}
472 % \end{macro}
473 %
474 % \begin{macro}{\gth@gotoh}
475 % This macro actually executes the Gotoh algorithm~\cite{gotoh1982}. The input
476 % of the algorithm is two biological sequences
477 % \[
478 % A \defeq a_1a_2a_3\dots a_m,\eqsep B \defeq b_1b_2b_3\dots b_n
479 % \]
480 % where $a_i$ and $b_j$ are chosen from a finite alphabet, e.g.~$\{\mathrm{A},
481 % \mathrm{T}, \mathrm{G}, \mathrm{C}\}$. The command takes these sequences as
482 % its arguments, and calculate following recurrence formula\footnote{This
483 % calculation is done in $O(mn)$ time.} to get optimal score of the algorithm:
484 % \begin{equation}
485 % M_{i+1, j+1}
486 % = \max\left\{M_{ij}, I^x_{ij}, I^y_{ij}\right\} + c_{ij}
487 % \label{eq:m}
488 % \end{equation}
489 % where
490 % \begin{align}
491 % I^x_{i+1, j} &= \max\left\{ M_{ij}-d, I^x_{ij}-e, I^y_{ij}-d \right\},
492 % \label{eq:ix} \\
493 % I^y_{i, j+1} &= \max\left\{ M_{ij}-d, I^y_{ij}-e \right\},
494 % \label{eq:iy}
495 % \end{align}
496 % and $c_{ij}$ is a score for a pair $(a_i, b_j)$, namely
497 % \[
498 % c_{ij} = \left\{
499 % \begin{array}{rll}
500 % 1 & \text{if\enspace} a_i = b_j & \text{(match)} \\
501 % -1 & \text{otherwise} & \text{(mismatch)}. \\
502 % \end{array}
503 % \right.
504 % \]
505 % Note that the Equations (\ref{eq:ix}) and (\ref{eq:iy}) have asymmetric form
506 % because the order of inserting \emph{gaps} when alternating $A$ and $B$ does
507 % not affect the optimal score.
508 %
509 % \subsubsection{Getting sequences}
510 %
511 % \begin{macro}{\gth@m}
512 % \begin{macro}{\gth@n}
513 % Here each calacters $a_i, b_j$ in the input sequences are stored in
514 % |\gth@seqa@|$a_i$ and |\gth@seqa@|$b_j$, and the lengthes of the sequences
515 % $m, n$ are stored in |\gth@m| and |\gth@n| respectively.
516 % \begin{macrocode}
517 \def\gth@gotoh#1#2{%
518 \gth@tempcnta\z@
519 \@tfor\gth@member:=#1\do{%
520 \gth@name@edef{seqa@\the\gth@tempcnta}{\gth@member}%
521 \advance\gth@tempcnta\@ne}%
522 \advance\gth@tempcnta\@ne
523 \edef\gth@m{\the\gth@tempcnta}%
524 \gth@tempcntb\z@
525 \@tfor\gth@member:=#2\do{%
526 \gth@name@edef{seqb@\the\gth@tempcntb}{\gth@member}%
527 \advance\gth@tempcntb\@ne}%
528 \advance\gth@tempcntb\@ne
529 \edef\gth@n{\the\gth@tempcntb}%
530 % \end{macrocode}
531 % \end{macro}
532 % \end{macro}
533 %
534 % \subsubsection{Initialization}
535 %
536 % We have to be careful with initialization because many implementations of the
537 % Gotoh algorithm have problems here~\cite{flouri2015}. Specifically, the
538 % package initialzes the matrxes with following equations:
539 % \begin{align*}
540 % M_{i0} &= -\infty, M_{0j} = -\infty, M_{00} = 0, \\
541 % I^x_{i0} &= -g(i), I^x_{0j} = -\infty, \\
542 % I^y_{i0} &= -\infty, I^y_{0j} = -g(j).
543 % \end{align*}
544 % Note that function $g(l)$ is a gap penalty (shown in Equation~(\ref{eq:gap}))
545 % and can be calculated with the macro |\gth@gap@penalty|.
546 %
547 % \begin{macrocode}
548 \gth@tempcnta\z@
549 \@whilenum\gth@tempcnta<\gth@m\do{%
550 \gth@gap@penalty{\gth@tempcnta}%
551 \gth@name@xdef{\gth@sn @m@\the\gth@tempcnta @0}{\gth@min}%
552 \gth@name@xdef{\gth@sn @ix@\the\gth@tempcnta @0}{\the\gth@calc}%
553 \gth@name@xdef{\gth@sn @iy@\the\gth@tempcnta @0}{\gth@min}%
554 \advance\gth@tempcnta\@ne}%
555 \gth@tempcntb\z@
556 \@whilenum\gth@tempcntb<\gth@n\do{%
557 \gth@gap@penalty{\gth@tempcntb}%
558 \gth@name@xdef{\gth@sn @m@0@\the\gth@tempcntb}{\gth@min}%
559 \gth@name@xdef{\gth@sn @ix@0@\the\gth@tempcntb}{\gth@min}%
560 \gth@name@xdef{\gth@sn @iy@0@\the\gth@tempcntb}{\the\gth@calc}%
561 \advance\gth@tempcntb\@ne}%
562 \gth@name@xdef{\gth@sn @m@0@0}{\number\z@}%
563 % \end{macrocode}
564 %
565 % \subsubsection{Memoization}
566 %
567 % If the switch |\if@gth@memoization| is true, memoization functions (See
568 % section~\ref{sect:memofunc}) are called recursively.
569 % \begin{macrocode}
570 \if@gth@memoization
571 \gth@decrement\gth@m \gth@decrement\gth@n
572 \gth@memo@ix{\gth@m}{\gth@n}%
573 \gth@memo@iy{\gth@m}{\gth@n}%
574 \gth@memo@m{\gth@m}{\gth@n}%
575 \gth@increment\gth@m \gth@increment\gth@n
576 % \end{macrocode}
577 %
578 % \subsubsection{Dynamic Programming}
579 %
580 % To fill matrxes $M$, $I^x$, and $I^y$ the package use the recurrence formula
581 %
582 % \begin{macrocode}
583 \else
584 \gth@tempcnta\@ne
585 \@whilenum\gth@tempcnta<\gth@m\do{%
586 \gth@tempcntb\@ne
587 \@whilenum\gth@tempcntb<\gth@n\do{%
588 % \end{macrocode}
589 % First, $I^x$ is calculated with Equation (\ref{eq:ix}).
590 % \begin{macrocode}
591 \advance\gth@tempcnta\m@ne
592 \gth@max{%
593 \gth@nameuse{\gth@sn @m@\the\gth@tempcnta
594 @\the\gth@tempcntb},%
595 \gth@nameuse{\gth@sn @iy@\the\gth@tempcnta
596 @\the\gth@tempcntb}}%
597 \gth@tempcntc\gth@calc
598 \gth@tempcntd
599 \gth@nameuse{\gth@sn @ix@\the\gth@tempcnta
600 @\the\gth@tempcntb}%
601 \advance\gth@tempcntc-\gth@d\advance\gth@tempcntd-\gth@e
602 \advance\gth@tempcnta\@ne
603 \gth@max{\gth@tempcntc,\gth@tempcntd}%
604 \gth@name@xdef{\gth@sn @ix@\the\gth@tempcnta
605 @\the\gth@tempcntb}{%
606 \the\gth@calc}%
607 % \end{macrocode}
608 % Secondly, $I^y$ is calculated with Equation (\ref{eq:iy}).
609 % \begin{macrocode}
610 \advance\gth@tempcntb\m@ne
611 \gth@tempcntc
612 \gth@nameuse{\gth@sn @m@\the\gth@tempcnta
613 @\the\gth@tempcntb}%
614 \gth@tempcntd
615 \gth@nameuse{\gth@sn @iy@\the\gth@tempcnta
616 @\the\gth@tempcntb}%
617 \advance\gth@tempcntc-\gth@d\advance\gth@tempcntd-\gth@e
618 \advance\gth@tempcntb\@ne
619 \gth@max{\gth@tempcntc,\gth@tempcntd}%
620 \gth@name@xdef{\gth@sn @iy@\the\gth@tempcnta
621 @\the\gth@tempcntb}{%
622 \the\gth@calc}%
623 % \end{macrocode}
624 % Finally, $M$ is calculated with Equation (\ref{eq:m}) and a loop is completed.
625 % \begin{macrocode}
626 \advance\gth@tempcnta\m@ne\advance\gth@tempcntb\m@ne
627 \gth@max{%
628 \gth@nameuse{\gth@sn @m@\the\gth@tempcnta
629 @\the\gth@tempcntb},%
630 \gth@nameuse{\gth@sn @ix@\the\gth@tempcnta
631 @\the\gth@tempcntb},%
632 \gth@nameuse{\gth@sn @iy@\the\gth@tempcnta
633 @\the\gth@tempcntb}}%
634 \edef\gth@tmpa{\gth@nameuse{seqa@\the\gth@tempcnta}}%
635 \edef\gth@tmpb{\gth@nameuse{seqb@\the\gth@tempcntb}}%
636 \advance\gth@tempcnta\@ne\advance\gth@tempcntb\@ne
637 \ifx\gth@tmpa\gth@tmpb
638 \advance\gth@calc\gth@match
639 \else
640 \advance\gth@calc\gth@mismatch
641 \fi
642 \gth@name@xdef{\gth@sn @m@\the\gth@tempcnta
643 @\the\gth@tempcntb}{%
644 \the\gth@calc}%
645 \advance\gth@tempcntb\@ne}%
646 \advance\gth@tempcnta\@ne}%
647 \fi
648 % \end{macrocode}
649 %
650 % \subsubsection{Printing Matrices}
651 %
652 % This is piece of code for debugging the package (so usually commented out).
653 %
654 % \begin{macrocode}
655 %\gth@print@matrix{m}%
656 %\gth@print@matrix{ix}%
657 %\gth@print@matrix{iy}%
658 % \end{macrocode}
659 %
660 % \subsubsection{Returning the Optimal Score}
661 %
662 % The calculated optimal score of the alignment stored here to the control
663 % sequences which stored in |\gth@score|.
664 % \begin{macrocode}
665 \bgroup
666 \gth@decrement\gth@m \gth@decrement\gth@n
667 \expandafter\xdef\gth@score{%
668 \gth@nameuse{\gth@sn @m@\gth@m @\gth@n}}%
669 \egroup
670 % \end{macrocode}
671 %
672 % \subsubsection{Trace Back}
673 %
674 % After processing dynamic programming (or memoization functions), matrices
675 % $M$, $I^x$, and $I^y$ are all filled. Using these matrices, we can determine
676 % the `trace' from the optimal score $M_{m,n}$ to the start $M_{0,0}$ and get
677 % the result of alignment $(x, y)$.
678 %
679 % Considering the form of Equation (\ref{eq:m})--(\ref{eq:iy}), the calculation
680 % formulae of the former values depend on which matrix the `current position'
681 % exists. In order to take into account these differences, trace back process
682 % is calculated while switching three modes: default, gap x, and gap y.
683 %
684 % First, make sure to empty |\gth@rseq@x| and |\gth@rseq@y| which is going to
685 % store result alignment sequences $x$ and $y$ respectively. Note that this is
686 % the trace \emph{back} process, so new characters are prepended to the
687 % existing sequences in each loop. In the next line, the switches
688 % |\if@gth@gapx@| and |\if@gth@gapy@| are both turned off (which means
689 % processing starts from the default mode).
690 % \begin{macrocode}
691 \let\gth@rseq@x\@empty\let\gth@rseq@y\@empty
692 \@gth@remain@true\@gth@gapx@false\@gth@gapy@false
693 % \end{macrocode}
694 % In the main loop of trace back, process the condition either $x$ or $y$ is
695 % already completed first. In this situation, the other sequence should be
696 % filled all the remaining with \emph{gaps}.
697 % \begin{macrocode}
698 \@whilesw\if@gth@remain@\fi{%
699 \ifnum\gth@m=\z@
700 \gth@decrement\gth@n
701 \expandafter\expandafter\expandafter
702 \ifx\gth@nameuse{seqb@\gth@n}\relax\else
703 \edef\gth@rseq@x{\gth@gap@char\gth@rseq@x}%
704 \edef\gth@rseq@y{\gth@nameuse{seqb@\gth@n}%
705 \gth@rseq@y}%
706 \fi
707 \else\ifnum\gth@n=\z@
708 \gth@decrement\gth@m
709 \expandafter\expandafter\expandafter
710 \ifx\gth@nameuse{seqa@\gth@m}\relax\else
711 \edef\gth@rseq@x{\gth@nameuse{seqa@\gth@m}%
712 \gth@rseq@x}%
713 \edef\gth@rseq@y{\gth@gap@char\gth@rseq@y}%
714 \fi
715 \else
716 % \end{macrocode}
717 % \paragraph{mode: gap x}
718 % Prepend former base to $x$ and a \emph{gap} to $y$. If
719 % $M_{m-1,n}-d>I^x_{m-1,n}-e$ back to default mode. Else if
720 % $I^x_{m-1,n}-e<I^y_{m-1,n}-d$ switch to mode gap y and otherwise stay in mode
721 % gap x.
722 % \begin{macrocode}
723 \if@gth@gapx@
724 \gth@decrement\gth@m
725 \expandafter\expandafter\expandafter
726 \ifx\gth@nameuse{seqa@\gth@m}\relax\else
727 \edef\gth@rseq@x{\gth@nameuse{seqa@\gth@m}%
728 \gth@rseq@x}%
729 \edef\gth@rseq@y{\gth@gap@char\gth@rseq@y}%
730 \fi
731 \gth@tempcnta\gth@nameuse{\gth@sn @m@\gth@m @\gth@n}%
732 \gth@tempcntb\gth@nameuse{\gth@sn @ix@\gth@m @\gth@n}%
733 \gth@tempcntc\gth@nameuse{\gth@sn @iy@\gth@m @\gth@n}%
734 \advance\gth@tempcnta-\gth@d
735 \advance\gth@tempcntb-\gth@e
736 \advance\gth@tempcntc-\gth@d
737 \ifnum\gth@tempcnta>\gth@tempcntb
738 \@gth@gapx@false
739 \else\ifnum\gth@tempcntb<\gth@tempcntc
740 \@gth@gapx@false\@gth@gapy@true
741 \fi\fi
742 % \end{macrocode}
743 % \paragraph{mode: gap y}
744 % Prepend a \emph{gap} to $x$ and former base to $y$. If
745 % $M_{m,n-1}-d>I^y_{m,n-1}-e$ back to default mode and otherwise stay in mode
746 % gap y.
747 % \begin{macrocode}
748 \else\if@gth@gapy@
749 \gth@decrement\gth@n
750 \expandafter\expandafter\expandafter
751 \ifx\gth@nameuse{seqb@\gth@n}\relax\else
752 \edef\gth@rseq@x{\gth@gap@char\gth@rseq@x}%
753 \edef\gth@rseq@y{\gth@nameuse{seqb@\gth@n}%
754 \gth@rseq@y}%
755 \fi
756 \gth@tempcnta\gth@nameuse{\gth@sn @m@\gth@m @\gth@n}%
757 \gth@tempcntb\gth@nameuse{\gth@sn @iy@\gth@m @\gth@n}%
758 \advance\gth@tempcnta-\gth@d\advance\gth@tempcntb-\gth@e
759 \ifnum\gth@tempcnta>\gth@tempcntb
760 \@gth@gapy@false
761 \fi
762 % \end{macrocode}
763 % \paragraph{mode: default}
764 % Prepend former base to $x$ and $y$ respectively. Only if
765 % $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
766 % mode, and else if $I^x_{m-1,n-1}>I^y_{n-1,m-1}$ go to gap x otherwise go to
767 % gap y.
768 % \begin{macrocode}
769 \else
770 \gth@decrement\gth@m
771 \gth@decrement\gth@n
772 \expandafter\expandafter\expandafter
773 \ifx\gth@nameuse{seqa@\gth@m}\relax\else
774 \expandafter\expandafter\expandafter
775 \ifx\gth@nameuse{seqb@\gth@n}\relax\else
776 \edef\gth@rseq@x{\gth@nameuse{seqa@\gth@m}%
777 \gth@rseq@x}%
778 \edef\gth@rseq@y{\gth@nameuse{seqb@\gth@n}%
779 \gth@rseq@y}%
780 \fi
781 \fi
782 \gth@tempcnta\gth@nameuse{\gth@sn @m@\gth@m @\gth@n}%
783 \gth@tempcntb\gth@nameuse{\gth@sn @ix@\gth@m @\gth@n}%
784 \gth@tempcntc\gth@nameuse{\gth@sn @iy@\gth@m @\gth@n}%
785 \@gth@gap@false
786 \ifnum\gth@tempcnta<\gth@tempcntb\@gth@gap@true\fi
787 \ifnum\gth@tempcnta<\gth@tempcntc\@gth@gap@true\fi
788 \if@gth@gap@
789 \ifnum\gth@tempcntb>\gth@tempcntc
790 \@gth@gapx@true
791 \else
792 \@gth@gapy@true
793 \fi
794 \fi
795 \fi\fi
796 \fi\fi
797 % \end{macrocode}
798 % Finally, if we achieve to $M_{0,0}$, exit from the main loop.
799 % \begin{macrocode}
800 \ifnum\gth@m<\@ne\ifnum\gth@n<\@ne
801 \@gth@remain@false
802 \fi\fi}%
803 % \end{macrocode}
804 %
805 % \subsubsection{Returning Results}
806 %
807 % Finally, the results of alignments which stored in |\gth@resq@x| and
808 % |\gth@resq@y| are copied globally to the control sequences which stored in
809 % |\gth@resulta| and |\gth@resultb|.
810 % \begin{macrocode}
811 \expandafter\gth@glet\gth@resulta\gth@rseq@x
812 \expandafter\gth@glet\gth@resultb\gth@rseq@y}
813 % \end{macrocode}
814 % \end{macro}
815 %
816 % \subsection{Memoization Functions}\label{sect:memofunc}
817 %
818 % \begin{macro}{\gth@memo@ix}
819 % \begin{macro}{\gth@memo@iy}
820 % \begin{macro}{\gth@memo@m}
821 % These are memoization functions for calculating $I^x, I^y, M$ respectively.
822 % Since these functions change many `temporary' values, all of the processes
823 % are wrapped in a group and only the return values and components of matrices
824 % are assigned globally.
825 % \begin{macrocode}
826 \def\gth@memo@ix#1#2{%
827 \bgroup
828 \gth@tempcnta#1\gth@tempcntb#2\relax
829 \expandafter\expandafter\expandafter
830 \ifx\gth@nameuse{\gth@sn @ix@\the\gth@tempcnta
831 @\the\gth@tempcntb}\relax
832 \advance\gth@tempcnta\m@ne
833 \gth@memo@ix{\gth@tempcnta}{\gth@tempcntb}%
834 \edef\gth@tmp@ix@return{\gth@ix@return}%
835 \gth@memo@iy{\gth@tempcnta}{\gth@tempcntb}%
836 \edef\gth@tmp@iy@return{\gth@iy@return}%
837 \gth@memo@m{\gth@tempcnta}{\gth@tempcntb}%
838 \advance\gth@tempcnta\@ne
839 \gth@advance{\gth@m@return}{-\gth@d}%
840 \gth@advance{\gth@tmp@ix@return}{-\gth@e}%
841 \gth@advance{\gth@tmp@iy@return}{-\gth@d}%
842 \gth@max{\gth@m@return,\gth@tmp@ix@return,\gth@tmp@iy@return}%
843 \gth@name@xdef{\gth@sn @ix@\the\gth@tempcnta
844 @\the\gth@tempcntb}{%
845 \the\gth@calc}%
846 \xdef\gth@ix@return{\the\gth@calc}
847 \else
848 \xdef\gth@ix@return{%
849 \gth@nameuse{\gth@sn @ix@\the\gth@tempcnta @\the\gth@tempcntb}}
850 \fi
851 \egroup}
852 \def\gth@memo@iy#1#2{%
853 \bgroup
854 \gth@tempcnta#1\gth@tempcntb#2\relax
855 \expandafter\expandafter\expandafter
856 \ifx\gth@nameuse{\gth@sn @iy@\the\gth@tempcnta
857 @\the\gth@tempcntb}\relax
858 \advance\gth@tempcntb\m@ne
859 \gth@memo@iy{\gth@tempcnta}{\gth@tempcntb}%
860 \edef\gth@tmp@iy@return{\gth@iy@return}%
861 \gth@memo@m{\gth@tempcnta}{\gth@tempcntb}%
862 \advance\gth@tempcntb\@ne
863 \gth@advance{\gth@m@return}{-\gth@d}%
864 \gth@advance{\gth@tmp@iy@return}{-\gth@e}%
865 \gth@max{\gth@m@return,\gth@tmp@iy@return}%
866 \gth@name@xdef{\gth@sn @iy@\the\gth@tempcnta
867 @\the\gth@tempcntb}{%
868 \the\gth@calc}%
869 \xdef\gth@iy@return{\the\gth@calc}%
870 \else
871 \xdef\gth@iy@return{%
872 \gth@nameuse{\gth@sn @iy@\the\gth@tempcnta @\the\gth@tempcntb}}
873 \fi
874 \egroup}
875 \def\gth@memo@m#1#2{%
876 \bgroup
877 \gth@tempcnta#1\gth@tempcntb#2\relax
878 \expandafter\expandafter\expandafter
879 \ifx\gth@nameuse{\gth@sn @m@\the\gth@tempcnta
880 @\the\gth@tempcntb}\relax
881 \advance\gth@tempcnta\m@ne\advance\gth@tempcntb\m@ne
882 \gth@memo@ix{\gth@tempcnta}{\gth@tempcntb}%
883 \edef\gth@tmp@ix@return{\gth@ix@return}%
884 \gth@memo@iy{\gth@tempcnta}{\gth@tempcntb}%
885 \edef\gth@tmp@iy@return{\gth@iy@return}%
886 \gth@memo@m{\gth@tempcnta}{\gth@tempcntb}%
887 \edef\gth@tmpa{\gth@nameuse{seqa@\the\gth@tempcnta}}%
888 \edef\gth@tmpb{\gth@nameuse{seqb@\the\gth@tempcntb}}%
889 \advance\gth@tempcnta\@ne\advance\gth@tempcntb\@ne
890 \gth@max{\gth@m@return,\gth@tmp@ix@return,\gth@tmp@iy@return}%
891 \ifx\gth@tmpa\gth@tmpb
892 \advance\gth@calc\gth@match
893 \else
894 \advance\gth@calc\gth@mismatch
895 \fi
896 \gth@name@xdef{\gth@sn @m@\the\gth@tempcnta
897 @\the\gth@tempcntb}{%
898 \the\gth@calc}%
899 \xdef\gth@m@return{\the\gth@calc}%
900 \else
901 \xdef\gth@m@return{%
902 \gth@nameuse{\gth@sn @m@\the\gth@tempcnta @\the\gth@tempcntb}}%
903 \fi
904 \egroup}
905 % \end{macrocode}
906 % \end{macro}
907 % \end{macro}
908 % \end{macro}
909 %
910 % \subsection{Configuration Command}
911 %
912 % \begin{macro}{\GotohConfig}
913 % This is just a wrap command of |\setkeys|.
914 % \begin{macrocode}
915 \newcommand{\GotohConfig}[1]{\setkeys[gth]{config}{#1}}
916 % \end{macrocode}
917 % \end{macro}
918 %
919 % \begin{thebibliography}{9}
920 % \bibitem{flouri2015}
921 % Flouri, Tom\'a\v s \textit{et al}., ``Are all global alignment
922 % algorithms and implementations correct?''. \textit{bioRxiv}, 031500, 2015.
923 % \bibitem{gotoh1982}
924 % Gotoh, Osamu, ``An improved algorithm for matching biological sequences''.
925 % \textit{Journal of Molecular Biology} \textbf{162}(3), 705-708, 1982.
926 % \end{thebibliography}
927 %
928 % \Finale
929 %
930 \endinput
931 % EOF