Smith-Waterman

Fig. 4. Alignment of two sequences using four different scoring functions. (A) From Altschul (1998) and (B-D) from Smith-Waterman alignments using SSEARCH (Pearson, 1996). Asterisks with numbers above the alignments correspond to the four HSPs indicated in Fig. 1.

Alignment scores generated from the comparison of a repeat profile with a database of randomized sequences are derived with Searchwise (Birney et al., 1996), which uses a Smith-Waterman comparison (Smith and Waterman, 1981). A number n of score distributions for the 1st (optimal), 2nd (first suboptimal), and up to the wth highest scores of the profile compared with randomized sequences are fitted to n EVDs. Parameters are obtained for each fit that allow the transformation of alignment scores for the top n (sub)optimal alignments into values. Since these E values are dependent on the repeat number, they are sensitive to the number of true-positive repeats in a sequence. 

A sequence alignment is a way of determining the similarity between two strings. This is a classical question in computer science, and has an exact solution referred to as the Smith/Waterman alignment. Unfortunately, this exact solution can be slow when analyzing large sequences, and therefore, approximate methods, such as Basic Local Alignment Search Tool (BLAST), have been developed to identify very similar sequences. 

Nevertheless Smith/Waterman alignment still has significant utility in practical applications when the need for sensitivity is paramount and the dataset to be analyzed is relatively small. Many evolutionary studies focusing on individual proteins use Smith/Waterman alignment. Several public servers providing access to Smith/Waterman alignment exist (Table 2). 

Hybrid sequence aligner Uses a Smith-Waterman variant with more tractable exact statistics bioinfo.ucsd.edu/ hybridparameters /... 

Other alignment software. While Smith/Waterman and BLAST alignment are the most popular methods of performing singlealignments a host of other software has been developed for specialized purposes that attempt to improve execution speed by making simplifying assumptions about the types of matches that can be found (Table 4). 

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,... 

Fig. 1. The CHAins Of Seeds algorithm. The rectangle represents the Smith-Waterman dynamic programming matrix, with one of the sequences along each axis. The seed shown can be chained to any seed that lies inside the search box. All seeds located less then distance basepair from the current location are stored in a skip list, in which we do a range query for seeds located within a gap cutoff from the diagonal on which the current seed is located. The seeds located in the gray areas are not available for chaining to make the algorithm independent of sequence order. (Figure reprinted with permission from ref. 14).

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... 

---