SALSA: improved protein database searching by a new algorithm for assemblyof sequence fragments into gapped alignments

Motivation: Optimal sequence alignment based on the Smith-Waterman algorith m is usually too computationally demanding to be practical for searching la rge sequence databases. Heuristic programs like FASTA and BLAST have been d eveloped which run much faster, but at the expense of sensitivity. Results: In an effort to approximate the sensitivity of an optimal alignmen t algorithm, a new algorithm has been devised for the computation of a gapp ed alignment of two sequences. After scanning for high-scoring words and ex tensions of these to form fragments of similarity, the algorithm uses dynam ic programming to build an accurate alignment based on the fragments initia lly identified. The algorithm has been implemented in a program called SALS A and the performance has been evaluated on a set of test sequences. The se nsitivity was found to be close to the Smith-Waterman algorithm, while the speed was similar to FASTA (ktup = 2).