Smith and Waterman algorithm

The constant is empirically set such that the expected score per position in a random alignment is less than zero. This is done to ensure that the local pairwise dynamic programming algorithm (Smith and Waterman, 1981 Karlin and Altschul, 1990) alignments will nearly always exceed those generated between random sequences. 

Pearson, W. R. (1991). Searching protein sequence libraries comparison of the sensitivity and the selectivity of the Smith-Waterman and FASTA algorithms. Genomics 11,635-50. 

Several implementations of this procedure are available, most prominently the SSEARCH program from the FASTA package [53], There exist implementations of the Smith-Waterman algorithm that are tuned for speed like one using special processor instructions [54] and, among others, one by Barton [55], Depending on implementation, computer, and database size, a search with such a program will take on the order of one minute. 

The Phrap program takes as input full-length reads and their base quality values. The program works in three phases. In the overlap computation phase, a banded Smith-Waterman algorithm is used to compute overlaps between reads. In the contig construction phase, the overlaps are considered in decreasing order of scores. For the current overlap between reads / and g,... 

GeneWise [44] allows a nucleic acid sequence to be aligned with a sequence or sequence profile (HMM) associated with a potentially homologous protein or protein family. The protein/protein family information is used to infer a putative intron-exon structure in the nucleic acid sequence. The core of the model is a state model of matches, insertions, and deletions, similar to those used in HMMER and Smith-Waterman algorithms. Two key additions are made to the core. The first addresses frame-shifts. The second is a five-region model for introns. The five regions are... 

Fig. 10.17 Finding the irptimal local sequence alignment using the Smith-Waterman algorithm with a scoring scheme in which a match scores 1, a mismatch scores -1 and the gap penalty is —2. The algorithm identifies the conserved RCK motif.

---