ss_gd_align, a FORTRAN90 code which implements some of the linear space alignment algorithms described in the reference by Chao.
A global alignment is attempted between the strings, and similarity is measured by a sort of distance. These algorithms carry out the computation in linear space, and compute not just the optimal alignment score, but the corresponding optimal alignment.
It's important to be able to compute alignments using "linear space", that is, just a few vectors whose length N is equal to that of a typical string. A quadratic algorithm would require a two dimensional array of total dimension N*N. Realistic alignment problems can involve strings of N=100,000 elements or more, so a quadratic algorithm would be expensive or impossible to use.
The score for the actual best matching is determined without constructing the best matching, and in fact it is a matter of some difficulty to recover the matching, particularly if the algorithm is a linear space one, which discards a great deal of intermediate information. However, a linear space algorithm included here can also compute the optimal matching, based on the idea of a recursive subdivision of the problem.
Routines that use quadratic space are included as well, so the algorithms can be compared for storage, speed, and correctness.
The computer code and data files made available on this web page are distributed under the GNU LGPL license.
ss_gd_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_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.
SS_QG_ALIGN, a FORTRAN90 library which quasi-globally aligns two sequences using an affine gap penalty.