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

http://bioinf.me/sites/default/files/share/An%20Introduction%20to%20Bioinformatics%20Algorithms%20-%20Jones,%20Pevzner.pdf

Books:

http://www.amazon.com/Bioinformatics-Algorithms-Techniques-Applications-Wiley/dp/0470097736