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

http://bioinformaticsonline.com/pages/view/920/bioinformatics-algorithms

WABI 2013: http://algo2013.inria.fr/wabi.shtml

Concepts and categories

Big O notation: http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

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

Identifying K-mer clumps:

Numerical optimization

Simplex algorithm:

Sequence alignment

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.

Other

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."

Baum-Welch algorithm (Baum-Welch expectation maximization):

http://en.wikipedia.org/wiki/Baum%E2%80%93Welch_algorithm

Invented by Leonard E. Baum and Lloyd R. Welch, the Baum-Welch algorithm is used to estimate the unknown parameters of a Hidden Markov Model (HMM).

L. E. Baum, T. Petrie, G. Soules, and N. Weiss, "A maximization technique occurring in the statistical analysis of probabilistic functions of Markov chains", Ann. Math. Statist., vol. 41, no. 1, pp. 164–171, 1970.

Mathematics

Fast Fourier Transform: http://en.wikipedia.org/wiki/Fast_Fourier_transform

Misc:

http://www.cse.sc.edu/~maxal/csce590b/Lect01-02.pdf

http://en.wikipedia.org/wiki/Kahan_summation_algorithm

Books/bibliography:

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

An introduction to bioinformatics algorithms: http://bix.ucsd.edu/bioalgorithms/

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

Commentary and reviews

http://ivory.idyll.org/blog/2013-pycon-awesome-big-data-algorithms-talk.html

http://www.nature.com/nrg/journal/v14/n5/full/nrg3433.html

Natural algorithms

http://egtheory.wordpress.com/2013/05/29/cells-and-dna/

http://egtheory.wordpress.com/2013/05/19/natural-algorithms-and-the-sciences/

Genetic algorithms

http://www.talkorigins.org/faqs/genalg/genalg.html#examples

Chess

http://www.theregister.co.uk/2012/06/26/kasparov_v_turing/

http://stackoverflow.com/questions/297577/is-there-a-perfect-algorithm-for-chess

http://en.wikipedia.org/wiki/Computer_chess

http://stackoverflow.com/questions/2026262/currently-known-best-algorithms-for-computer-chess

http://cs.stackexchange.com/questions/7313/can-there-be-a-perfect-chess-algorithm

http://cstheory.stackexchange.com/questions/6563/what-is-the-computational-complexity-of-solving-chess

http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf

http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf

http://www.frayn.net/beowulf/theory.html

http://www.uio.no/studier/emner/matnat/ifi/INF4130/h12/undervisningsmateriale/chess-algorithms-theory-and-practice-ver2012.pdf

http://en.wikibooks.org/wiki/Chess_Opening_Theory

http://en.wikibooks.org/wiki/Chess_Strategy/The_center

http://en.wikibooks.org/wiki/Chess/Basic_Openings

Journals

http://www.mdpi.com/journal/algorithms

Bibliography

Algorithms in bioinformatics: http://www.springer.com/computer/bioinformatics/book/978-3-642-40452-8