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
Concepts and categories
Dynamic programming
See http://en.wikipedia.org/wiki/Dynamic_programming
Examples of dynamic programming algorithms:
- Needleman-Wunschm algorithm
- Smith-Waterman algorithm
- Sankoff algorithm
- Viterbi algorithm
Algorithms
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:
Also called "block-sorting compression". String transformation algorithm used in data compression. Transforms a character string by permuting the order of the character, to increase the number of character repeats.
Used by the sequence alignment program BWA.
Viterbi algorithm:
From Wikipedia: "The Viterbi algorithm is a dynamic programming algorithm for finding the most likely sequence of hidden states – called the Viterbi path – that results in a sequence of observed events, especially in the context of Markov information sources and hidden Markov models."
Misc:
http://www.cse.sc.edu/~maxal/csce590b/Lect01-02.pdf
Books:
http://www.amazon.com/Bioinformatics-Algorithms-Techniques-Applications-Wiley/dp/0470097736