Fundamental Algorithms in Bioinformatics Dan Gusfield
-
- Technology
This course covers fundamental algorithms for efficient analysis of biological sequences and for building evolutionary trees. This is an undergraduate course focusing on the ideas and concepts behind the most central algorithms in biological sequence analysis. Dynamic Programming, Alignment, Hidden Markov Models, Statistical Analysis are emphasized.
-
- video
Postscript: Where to go next
Some suggestions of where the student can get more
exposure to algorithms for bioinformatics and computational biology. -
- video
Lecture 30: Maximum Parsimony and minimum mutation methods
Building evolutionary trees from sequence data. The Maximum Parsimony criteria, the special case of Perfect Phylogeny, and the Fitch-Hartigon dynamic program to minimize mutations when the tree and a sequence alignment are known.
-
- video
Lecture 29; Additive trees and the Neighbor-Joining algorithm
Additive trees and their construction. The Neighbor-Joining algorithm and its use with near-additive data. Bootstrap values and their misuse.
-
- video
Lecture 28: Algorithms for Ultrametric trees — molecular clocks
Algorithms for constructing an Ultrametric Tree from an Ultrametric Matrix, and the relationship of ultrametrics to the molecular clock.
-
- video
Lecture 27: Introduction to evolutionary trees - Ultrametric trees
lntroduction to trees that represent evolution. We start with the case of perfect data: the Ultrametric tree case.
-
- video
Lecture 26: Hidden Markov models - The Backwards algorithm
What the Backwards algorithm computes and why we want it.
Profile HMMs and their use. Cleaning up some topics in sequence analysis (running out of time); PSI-BLAST and its dangers.