|
STRETCHER application details page
Finds the best global alignment between two sequences
stretcher calculates a global alignment of two sequences using amodification of the classic dynamic programming algorithm which useslinear space. A global pairwise alignment is one where it is assumed that thetwo sequences have diverged from a common ancestor and that the programshould try to stretch the two sequences, introducing gaps wherenecessary, in order to show the alignment over the whole length of thetwo sequences that best illustrates their similarities. In contrast, a local alignment program like matcher simplyfinds local, small parts of the two sequences where there is somesimilarity and makes no assumption about the whole length of thesequence needing to be similar. The standard sequence global alignment program using the Needleman &Wunsch; algorithm, as implemented in the program needle, requiresO(MN) space and O(N) time. This is standard computer-science languagefor it needing an amount of computer memory that is proportional to theproduct of the two sequences being aligned and taking an amount of timethat is proportional to the shorter of the two sequences. So if a 1 kband a 10 kb sequence take 10 Mega-words of memory and 10 minutes toalign, you should expect that in order to align a 10 kb sequence and a 1Mb sequence you will need appoximately 10 Giga-words of memory and 100minutes. Computer memory will rapidly be exhausted as the size of thealigned sequences increases. This program implements the Myers and Miller algorithm for finding anoptimal global alignment in an amount of computer memory that is onlyproportional to the size of the smaller sequence - O(N). In computing, a benefit is seldom gained without a cost elsewhere. Thecost of gaining a memory-efficient alignment is that it takes abouttwice the amount of time to do the alignment as the Needleman & Wunschalgorithm. In computer-science language the time is approximately O(2N).
|