SS_QG_ALIGN
Sequence/sequence Quasiglobal Gap Alignment


SS_QG_ALIGN is a FORTRAN90 library 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.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

SS_QG_ALIGN is available in a FORTRAN90 version.

Related Data and Programs:

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.

Reference:

  1. Kun-Mao Chao, Ross Hardison, Webb Miller,
    Recent Developments in Linear-Space Alignment Methods: A Survey,
    Journal of Computational Biology,
    Volume 1, Number 4, 1994, pages 271-291.
  2. Eugene Myers, Webb Miller,
    Optimal Alignments in Linear Space,
    CABIOS, volume 4, number 1, 1988, pages 11-17.
  3. Michael Waterman,
    Introduction to Computational Biology,
    Chapman and Hall, 1995.

Source Code:

Examples and Tests:

List of Routines:

You can go up one level to the FORTRAN90 source codes.


Last revised on 29 December 2007.