User:Jarle Pahr/Algorithms: Difference between revisions
Jarle Pahr (talk | contribs) No edit summary |
Jarle Pahr (talk | contribs) No edit summary |
||
(15 intermediate revisions by the same user not shown) | |||
Line 8: | Line 8: | ||
https://www.coursera.org/course/bioinformatics | 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= | =Concepts and categories= | ||
Big O notation: http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/ | |||
==Dynamic programming== | ==Dynamic programming== | ||
Line 24: | Line 30: | ||
=Algorithms= | =Algorithms= | ||
Identifying K-mer clumps: | |||
==Numerical optimization== | |||
Simplex algorithm: | Simplex algorithm: | ||
==Sequence alignment== | |||
Line 45: | Line 60: | ||
See also http://seqanswers.com/forums/showthread.php?t=25305 for a discussion on implementing SW. | See also http://seqanswers.com/forums/showthread.php?t=25305 for a discussion on implementing SW. | ||
==Other== | |||
Burrows-Wheeler transform: | Burrows-Wheeler transform: | ||
Line 65: | Line 83: | ||
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. | 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: | Misc: | ||
http://www.cse.sc.edu/~maxal/csce590b/Lect01-02.pdf | http://www.cse.sc.edu/~maxal/csce590b/Lect01-02.pdf | ||
http://en.wikipedia.org/wiki/Kahan_summation_algorithm | |||
'''Books/bibliography:''' | '''Books/bibliography:''' | ||
Line 74: | Line 100: | ||
http://www.amazon.com/Bioinformatics-Algorithms-Techniques-Applications-Wiley/dp/0470097736 | 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 | 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 |
Latest revision as of 10:40, 2 October 2013
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/
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://www.frayn.net/beowulf/theory.html
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