|
NEEDLE application details page
Needleman-Wunsch global alignment
This program uses the Needleman-Wunsch global alignment algorithm tofind the optimum alignment (including gaps) of two sequences whenconsidering their entire length. The Needleman-Wunsch algorithm is a member of the class of algorithmsthat can calculate the best score and 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 Needleman and Wunsch, though similar methods wereindependently devised during the late 1960's and early 1970's for use inthe fields of speech processing and computer science. What is the optimal alignment? Dynamic programming methods ensure theoptimal global 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. Needlefinds 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.
|