| 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 |