The ``All local alignment'' algorithm has been implemented in C. This language allows the C, M, S and E arrays to be grouped into a single data structure array of length m. The resulting code is faster than when C, M, S and E are coded separately, since sequentially accessed values are adjacent in memory. The results list is also of length m where each element points to a dynamically allocated ``ragged'' list of structures containing values for M, S and E.
As a check of the relative efficiency of the ``all local alignment'' algorithm, the protein sequence of human -- haemoglobin (141-residues, PIR code HAHU) was compared to a small sequence databank (PIR 14.0: 6,858 sequences, 2,080,148 amino acids) using the Dayhoff MDM250 matrix [Dayhoff et al., 1978] and gap-penalty of 8 (). When run on a Sun SPARCstation 2, the efficient ``best score only'' algorithm determined one optimal local alignment for each databank sequence, and required 270 seconds to complete the scan. Another implementation of the Smith-Waterman algorithm SSEARCH  which also only returns the top scoring alignment for each sequence pair, required 1,100 seconds for the same scan. In contrast, the ``all local alignment'' algorithm described here with examined 30,690 local alignments in only 1,000 seconds.
The value of has little effect on the execution time, except when set very small such that large numbers of local alignments must be stored and sorted for each sequence comparison. For example, comparison of HAHU (141 residues) to one of the longest protein sequences known, Twitchin from Caenorhabditis elegans (PIR code S07571 - 6048 residues), finds 32,299 alternative local alignments when and requires 16 sec CPU time. Setting reduces the number of alignments to 58 and takes only 2 sec. The algorithms described here have also been implemented to work with pscan [Barton, 1991] to allow distributed processing on a network of workstations. pscan permits an approximately linear decrease in elapsed scan time with increasing numbers of processors.