PS_QG_ALIGN - Profile/sequence Quasiglobal Gap Alignment

PS_QG_ALIGN is a draft implementation of 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.

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.

Reference 2:

Eugene Myers and Webb Miller,
Optimal Alignments in Linear Space,
CABIOS, volume 4, number 1, 1988, pages 11-17.

Reference 3:

Michael Waterman,
Introduction to Computational Biology,
Chapman and Hall, 1995.

Files you may copy include:

• ps_qg_align.f90, the source code
• ps_qg_align_prb.f90, test routines;
• ps_qg_align_prb.out, the test output.
• profile.txt, a sample profile definition file.

The list of routines includes:

• A_INDEX sets up a reverse index for the amino acid codes.
• A_TO_I returns the index of an alphabetic character.
• C_CAP capitalizes a single character.
• I_SWAP switches two integer values.
• I_TO_A returns the I-th alphabetic character.
• IVEC_REVERSE reverses the elements of an integer vector.
• IVEC2_COMPARE compares pairs of integers stored in two vectors.
• IVEC2_SORT_A ascending sorts a vector of pairs of integers.
• PROFILE_SCORE_PRINT prints profile scoring data.
• PROFILE_SCORE_READ reads profile scoring data from a file.
• PROFILE_SCORE_READ2 returns a small amount of information from a profile.
• PS_GG_BSL determines a global gap backward alignment score in linear space.
• PS_GG_FSL determines a global gap forward alignment score in linear space.
• PS_QG_BOQ determines the backward endpoint of a quasiglobal optimal local alignment.
• PS_QG_BPQ determines a quasiglobal gap backward alignment path in quadratic space.
• PS_QG_BSL determines a quasiglobal gap backward alignment score in linear space.
• PS_QG_BSQ determines a quasiglobal gap backward alignment score in quadratic space.
• PS_QG_FOQ determines the forward endpoint of a quasiglobal optimal local alignment.
• PS_QG_FPQ determines a quasiglobal gap forward alignment path in quadratic space.
• PS_QG_FSL determines a quasiglobal gap forward alignment score in linear space.
• PS_QG_FSQ determines a quasiglobal gap forward alignment score in quadratic space.
• PS_QG_MATCH_PRINT prints a quasiglobal gap alignment.
• PS_QG_RPL determines a quasiglobal gap recursive alignment path in linear space.
• PS_QG_RPL_POP pops the data describing a subproblem off of the stack.
• PS_QG_RPL_PUSH pushes the data describing a subproblem onto the stack.
• RVEC2_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_CVEC converts a string to a character vector.
• S_TO_I reads an integer value from a string.
• SORT_HEAP_EXTERNAL externally sorts a list of items into linear order.
• WORD_LAST_READ returns the last word from a string.
• WORD_NEXT_READ "reads" words from a string, one at a time.

Return to the bioimedical software page.