Loading...
Please wait, while we are loading the content...
Similar Documents
An Analysis of Pairwise Sequence Alignment Algorithm Complexities: Needleman-Wunsch, Smith-Waterman, FASTA, BLAST and Gapped BLAST
| Content Provider | Semantic Scholar |
|---|---|
| Author | Needleman-Wunsch, Smith-Waterman Chan, Alexander |
| Copyright Year | 2004 |
| Abstract | Introduction As databases of protein sequences and properties increase in size, it becomes more and more reliable to depend on previously classified proteins to determine the structure and function of a novel protein. One method of determining homology between two proteins is through a pair-wise sequence alignment of their primary structures. It has been found that two proteins that are homologous, such that they were evolutionarily derived from a common protein, tend to align well with a large number of identical or highly similar residues in similar positions along the sequences. Provided a large database of protein sequences and their matching functions and structures, performing a sequence alignment between a sequence of a novel protein and the proteins in the database will find other proteins which are highly related, thus potentially revealing the function of the new protein. The challenge in performing sequence alignments has been the tradeoff between accuracy and efficiency. Older algorithms like the Needleman-Wunsch algorithm and the Smith-Waterman algorithm tend to have very high computational complexities, however manage to find the optimal alignment between a pair of proteins. Newer algorithms like FASTA and BLAST sacrifice some of this accuracy to make the alignments faster. As the database of proteins grows larger, faster algorithms become more important to be able to quickly compare a given sequence to the entire database. In this paper, we shall look at five main algorithms: the older optimal alignment algorithms by Needleman-Wunsch and Smith-Waterman, and the newer, approximate alignment algorithms FASTA, BLAST, and Gapped BLAST. We shall look at the algorithm itself and the computational and space complexity of each algorithm. From this, we can compare the efficiencies of the various algorithms and see what sacrifices the algorithms make in exchange for speed. We shall also analyze two modifications of the older dynamic programming algorithms: affine gap penalties, and the Hirschberg improvement. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://cmgm.stanford.edu/biochem218/Projects%202004/Chan.pdf |
| Alternate Webpage(s) | http://biochem218.stanford.edu/Projects%202004/Chan.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
