User:Jarle Pahr/Algorithms
Notes on algorithms with use in bioinformatics and computational biology:
See also:
http://bix.ucsd.edu/bioalgorithms/
http://en.wikipedia.org/wiki/Category:Bioinformatics_algorithms
https://www.coursera.org/course/bioinformatics
Simplex algorithm:
Needleman–Wunsch algorithm:
Dynamic programming algorithm to perform global sequence alignment. Also referred to as the "optimal matching algorithm". Introduced in 1970.
http://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm
In general parlance, a Needleman-Wunsch type algorithm refers to a global alignment algorithm that takes quadratic time for a linear or affine gap penalty.
Smith Waterman algorithm:
http://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorithm
Dynamic programming algorithm for local sequence alignment. Introduced in 1981. Can be considered a variation of the Needleman-Wunsch algorithm. Guaranteed to find the optimal local alignment with respect to the scoring system used.
See also http://seqanswers.com/forums/showthread.php?t=25305 for a discussion on implementing SW.
Burrows-Wheeler transform:
Misc:
http://www.cse.sc.edu/~maxal/csce590b/Lect01-02.pdf
Books:
http://www.amazon.com/Bioinformatics-Algorithms-Techniques-Applications-Wiley/dp/0470097736
