Fundamental Algorithms in Bioinformatics

By Dan Gusfield

What's Fundamental Algorithms in Bioinformatics about?

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.

Download our free app to listen on your phone

Fundamental Algorithms in Bioinformatics episodes:

02.01.2010
Postscript: Where to go next
Some suggestions of where the student can get more exposure to algorithms for bioinformatics and computational biology.
01.31.2010
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.
01.30.2010
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.
01.29.2010
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.
01.28.2010
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.
01.27.2010
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.
01.26.2010
Lecture 25: From the Vitterbi algorithm to the forward algorithm
This class finishes the discussion of the Vitterbi algorithm, its time analysis and the traceback algorithm. Introduction to the Forward algorithm to compute the probability that a given sequence is generate by the HMM.
01.25.2010
Lecture 24: Hidden Markov models and the Vitterbi algorithm
Finish the discussion of HMMs for CpG islands. Introduction to the Vitterbi algorithm (really dynamic programming) to find the most likely Markov Chain generating a given sequence.
01.24.2010
Lecture 23: Hidden Markov models
Hidden Markov models to identify CpG islands. This lecture follows the discussion in Durbin and Eddy.
01.23.2010
Lecture 22: From profiles to Markov models
Finish the discussion of profiles and log-odds ratios. introduction to Markov Models and Hidden Markov Models
01.22.2010
Lecture 21: Uses of multiple sequence alignment
Use of multiple sequence alignment to build a model of a set of biologically related sequences. Profiles, log-odds ratios.
01.21.2010
Lecture 20: Multiple sequence alignment III
The center tree method and analysis; progressive alignment, guide trees, CLUSTAL, uses of multiple alignment
01.20.2010
Lecture 19: Multiple sequence alignment II
Continuation of multiple sequence alignment; sum-of-pairs objective function; tree consistency theorem; factor-of-two approximation.
01.19.2010
Lecture 18: Multiple sequence alignment I
Start of discussion on Multiple Sequence Alignment. sum-of-pairs objective function. Dynamic program solution for three sequences. Program MSA
01.18.2010
Lecture 17: Probability and database search
Further discussion of probability and database search. Granin and BRCA1 story. Database search used as a filter, not an oracle.
01.17.2010
Lecture 16: BLAST statistics
E-values, extreme value distribution, probability of a match
01.15.2010
Lecture 15: BLAST II
Discussion of hashing kmers, E-values, statistics, BLAST II
01.14.2010
Lecture 14: BLAST I
Introduction to the ideas behind BLAST I.
01.13.2010
Lecture 13: Probability of a complete query match in a database
Continuation of the topic of probability of matching. Here we look at the probability that a query string matches completely, at least once, in a much larger database of strings.
01.12.2010
Lecture 12: Expected longest common substring II
Completion of the analysis of the expected length of the longest common substring in two random strings
01.11.2010
Lecture 11b: Expected Length of the Longest Common Substring
We discuss the expected length of the longest common substring (not subsequence) between two random strings of length n each, and show that it grows only logarithmically as a function of n - much slower than the growth of the expected longest common subsequence...
01.11.2010
Lecture 11a: Expected Length of the Longest Common Subsequence
We discuss the expected length of the longest common subsequence between two random strings of lengths n each, and show that it grows linearly with n. This lecture originally contained a discussion both of the expected length of the longest common subsequence...
01.11.2010
Lecture 10: End-gap-free alignment and whole-genome shotgun sequencing
End-gap-free alignment using dynamic programming. Example from whole-genome shotgun sequencing.
01.10.2010
Lecture 9: Local sequence alignment
In depth treatment of local alignment using dynamic programming.
01.08.2010
Lecture 8: Sequence alignment using dynamic programming — continued
Continuation of the discussion of how to compute similarity and optimal sequence alignment using dynamic programming. Local as well as global alignment.
01.07.2010
Lecture 7: From alignment graphs to formal dynamic programming
In this class, we move from the visual alignment graph to a purely symbolic treatment of how to compute sequence similarity and optimal alignment using dynamic programming.
01.06.2010
Lecture 6: Computing similarity using an alignment graph
Continuation of the discussion of how to efficiently compute the similarity of two sequences. Introduction to the traceback operation to find the optimal alignment.
01.05.2010
Lecture 5: Computing sequence similarity
Introduction to computational efficiency. Introduction to how we actually compute sequence similarity efficiently.
01.04.2010
Lecture 4: Extending the model of sequence similarity
Review of the definition of sequence similarity and extensions of the model for greater biological fidelity. Introduction to parametric sequence alignment.
01.03.2010
Lecture 3: Defining sequence similarity
Definition of sequence similarity and string alignment, counting alignments the need for fast computation.
01.02.2010
Lecture 2: Further introduction
Continuation of the introduction to the course and to bioinformatics. The biological utility of the similarity of sequences. The first fact of bio-sequence analysis.
01.01.2010
Lecture 1: Introduction to bioinformatics and the course
Introduction to the course and bioinformatics. Why we do bioinformatics, how it relates to genomics and to the changing modalities of biology.

What's Fundamental Algorithms in Bioinformatics about?

Download our free app to listen on your phone

Fundamental Algorithms in Bioinformatics episodes:

Postscript: Where to go next

Lecture 30: Maximum Parsimony and minimum mutation methods

Lecture 29; Additive trees and the Neighbor-Joining algorithm

Lecture 28: Algorithms for Ultrametric trees — molecular clocks

Lecture 27: Introduction to evolutionary trees - Ultrametric trees

Lecture 26: Hidden Markov models - The Backwards algorithm

Lecture 25: From the Vitterbi algorithm to the forward algorithm

Lecture 24: Hidden Markov models and the Vitterbi algorithm

Lecture 23: Hidden Markov models

Lecture 22: From profiles to Markov models

Lecture 21: Uses of multiple sequence alignment

Lecture 20: Multiple sequence alignment III

Lecture 19: Multiple sequence alignment II

Lecture 18: Multiple sequence alignment I

Lecture 17: Probability and database search

Lecture 16: BLAST statistics

Lecture 15: BLAST II

Lecture 14: BLAST I

Lecture 13: Probability of a complete query match in a database

Lecture 12: Expected longest common substring II

Lecture 11b: Expected Length of the Longest Common Substring

Lecture 11a: Expected Length of the Longest Common Subsequence

Lecture 10: End-gap-free alignment and whole-genome shotgun sequencing

Lecture 9: Local sequence alignment

Lecture 8: Sequence alignment using dynamic programming — continued

Lecture 7: From alignment graphs to formal dynamic programming

Lecture 6: Computing similarity using an alignment graph

Lecture 5: Computing sequence similarity

Lecture 4: Extending the model of sequence similarity

Lecture 3: Defining sequence similarity

Lecture 2: Further introduction

Lecture 1: Introduction to bioinformatics and the course