Smith/Waterman algorithm

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.

---