ss_qg_align, a FORTRAN90 code which implements some of the string matching algorithms described in the reference [Chao].
These algorithms carry out the computation in linear space, and compute not just the optimal alignment score, but also the corresponding optimal alignment.
The quasiglobal matching considered here is similar to the global matching scheme, except that no penalty is applied for the very first gap (a deletion or insertion, but not both), and the very last one. This simple alteration in the global alignment scheme facilitates the search for repeated patterns.
Routines that use quadratic space are included as well, so the algorithms can be compared for storage, speed, and correctness.
The names of the scoring and path routines include information about whether they use a forward, backward, or recursive algorithm, whether they compute the score or the path, and whether they use linear or quadratic space. Thus, the routine SS_QG_FSQ uses the forward algorithm to compute the score, with quadratic space requirements.
The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.
ss_qg_align is available in a FORTRAN90 version.
PS_GG_ALIGN, a FORTRAN90 library which implements a profile/sequence global alignment using an affine gap penalty.
PS_LG_ALIGN, a FORTRAN90 library which implements a profile/sequence local alignment using an affine gap penalty.
PS_QG_ALIGN, a FORTRAN90 library which implements a profile/sequence quasiglobal alignment using an affine gap penalty.
SS_GD_ALIGN, a FORTRAN90 library which globally aligns two sequences using a distance matrix.
SS_GG_ALIGN, a FORTRAN90 library which globally aligns two sequences using an affine gap penalty.
SS_LG_ALIGN, a FORTRAN90 library which locally aligns two sequences using an affine gap penalty.