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:

• ss_qg_align.f90, the source code;
• ss_qg_align.sh, commands to compile the source code;

Examples and Tests:

• ss_qg_align_test.f90, test routines;
• ss_qg_align_test.sh, commands to compile,link and run the test routines;
• ss_qg_align_test.txt, the test output.

List of Routines:

• A_INDEX sets up a reverse index for the amino acid codes.
• A_TO_I4 returns the index of an alphabetic character.
• CH_CAP capitalizes a single character.
• CHVEC2_PRINT prints two vectors of characters.
• CHVEC_PRINT prints a vector of characters.
• GET_SEED returns a seed for the random number generator.
• I4_RANDOM returns a random integer in a given range.
• I4_SWAP switches two integer values.
• I4_TO_A returns the I-th alphabetic character.
• I4_TO_AMINO_CODE converts an integer to an amino code.
• I4VEC2_COMPARE compares pairs of integers stored in two vectors.
• I4VEC2_PRINT prints a pair of integer vectors, with an optional title.
• I4VEC2_SORT_A ascending sorts a vector of pairs of integers.
• I4VEC_REVERSE reverses the elements of an integer vector.
• MUTATE applies a few mutations to a sequence.
• PAM120 returns the PAM 120 substitution matrix.
• PAM120_SCORE computes a single entry sequence/sequence matching score.
• PAM200 returns the PAM 200 substitution matrix.
• PAM200_SCORE computes a single entry sequence/sequence matching score.
• R4VEC2_SUM_IMAX returns the index of the maximum sum of two real vectors.
• S_EQI is a case insensitive comparison of two strings for equality.
• S_TO_CHVEC converts a string to a character vector.
• S_TO_I4 reads an integer value from a string.
• SIMPLE_SCORE computes a single entry sequence/sequence matching score.
• SORT_HEAP_EXTERNAL externally sorts a list of items into linear order.
• SS_GG_BSL determines a global gap backward alignment score in linear space.
• SS_GG_FSL determines a global gap forward alignment score in linear space.
• SS_QG_BOQ determines the backward endpoint of a quasiglobal optimal local alignment.
• SS_QG_BPQ determines a quasiglobal gap backward alignment path in quadratic space.
• SS_QG_BSL determines a quasiglobal gap backward alignment score in linear space.
• SS_QG_BSQ determines a quasiglobal gap backward alignment score in quadratic space.
• SS_QG_FOQ determines the forward endpoint of a quasiglobal optimal local alignment.
• SS_QG_FPQ determines a quasiglobal gap forward alignment path in quadratic space.
• SS_QG_FSL determines a quasiglobal gap forward alignment score in linear space.
• SS_QG_FSQ determines a quasiglobal gap forward alignment score in quadratic space.
• SS_QG_MATCH_PRINT prints a quasiglobal gap alignment.
• SS_QG_MATCH_SCORE scores a quasiglobal gap alignment.
• SS_QG_RPL determines a quasiglobal gap recursive alignment path in linear space.
• SS_QG_RPL_POP pops the data describing a subproblem off of the stack.
• SS_QG_RPL_PUSH pushes the data describing a subproblem onto the stack.
• TIMESTAMP prints the current YMDHMS date as a time stamp.
• UNIFORM_01_SAMPLE is a portable random number generator.
• WORD_LAST_READ returns the last word from a string.
• WORD_NEXT_READ "reads" words from a string, one at a time.

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