ps_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 PS_QG_FSQ uses the forward algorithm to compute the score, with quadratic space requirements.
The information on this web page is distributed under the MIT license.
ps_qg_align is available in a Fortran90 version.
ps_gg_align, a Fortran90 code which implements a profile/sequence global alignment using an affine gap penalty.
ps_lg_align, a Fortran90 code which implements a profile/sequence local alignment using an affine gap penalty.
ss_gd_align, a Fortran90 code which globally aligns two sequences using a distance matrix.
ss_gg_align, a Fortran90 code which globally aligns two sequences using an affine gap penalty.
ss_lg_align, a Fortran90 code which locally aligns two sequences using an affine gap penalty.
ss_qg_align, a Fortran90 code which quasi-globally aligns two sequences using an affine gap penalty.