|
WATER application details page
Smith-Waterman local alignment
water uses the Smith-Waterman algorithm (modified for speedenhancments) to calculate the local alignment. The Smith-Waterman algorithm is a member of the class of algorithmsthat can calculate the best score and local alignment in the order of mnsteps, (where 'n' and 'm' are the lengths of the two sequences). Thesedynamic programming algorithms were first developed for protein sequencecomparison by Smith and Waterman, though similar methods wereindependently devised during the late 1960's and early 1970's for use inthe fields of speech processing and computer science. A local alignment searches for regions of local similarity between twosequences and need not include the entire length of the sequences. Local alignment methods are very useful for scanning databases or othercircumsatnces when you wish to find matches between small regions ofsequences, for example between protein domains. Dynamic programming methods ensurethe optimal local alignment by exploring all possible alignments andchoosing the best. It does this by reading in a scoring matrix thatcontains values for every possible residue or nucleotide match. waterfinds an alignment with the maximum possible score where the score of analignment is equal to the sum of the matches taken from the scoringmatrix. An important problem is the treatment of gaps, i.e., spaces inserted tooptimise the alignment score. A penalty is subtracted from the scorefor each gap opened (the 'gap open' penalty) and a penalty is subtractedfrom the score for the total number of gap spaces multiplied by a cost(the 'gap extension' penalty). Typically, the cost of extending a gap is set to be 5-10 times lowerthan the cost for opening a gap. matcher is a local alignment program that gives as good analignment as water but it uses far less memory. However,water runs twice as fast as matcher. supermatcher is designed for local alignments of very largesequences. It gives good results as long as there is not significantamounts of insertion or deletion in the alignment. supermatcher Finds a match of a large sequence against one or more sequences matcher Finds the best local alignments between two sequences
|