Episodes
Some suggestions of where the student can get more
exposure to algorithms for bioinformatics and computational biology.
Published 02/01/10
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.
Published 01/31/10
Additive trees and their construction. The Neighbor-Joining algorithm and its use with near-additive data. Bootstrap values and their misuse.
Published 01/30/10
Algorithms for constructing an Ultrametric Tree from an Ultrametric Matrix, and the relationship of ultrametrics to the molecular clock.
Published 01/29/10
lntroduction to trees that represent evolution. We start with the case of perfect data: the Ultrametric tree case.
Published 01/28/10
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.
Published 01/27/10
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.
Published 01/26/10
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.
Published 01/25/10
Hidden Markov models to identify CpG islands. This
lecture follows the discussion in Durbin and Eddy.
Published 01/24/10
Finish the discussion of profiles and log-odds ratios. introduction to Markov Models
and Hidden Markov Models
Published 01/23/10
Use of multiple sequence alignment to build a model of a set of biologically related sequences. Profiles, log-odds ratios.
Published 01/22/10
The center tree method and analysis; progressive alignment, guide trees, CLUSTAL, uses of multiple alignment
Published 01/21/10
Continuation of multiple sequence alignment; sum-of-pairs objective function; tree consistency theorem; factor-of-two approximation.
Published 01/20/10
Start of discussion on Multiple Sequence Alignment. sum-of-pairs objective function. Dynamic program solution for three sequences. Program MSA
Published 01/19/10
Further discussion of probability and database search. Granin and BRCA1 story. Database search used as a filter, not an oracle.
Published 01/18/10
E-values, extreme value distribution, probability of a match
Published 01/17/10
Discussion of hashing kmers, E-values, statistics, BLAST II
Published 01/15/10
Introduction to the ideas behind BLAST I.
Published 01/14/10
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.
Published 01/13/10
Completion of the analysis of the expected length of the longest common substring in two random strings
Published 01/12/10
End-gap-free alignment using dynamic programming. Example
from whole-genome shotgun sequencing.
Published 01/11/10
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 and the expected length of the longest common substring. But the video has been split to overcome some technical problems
that showed up in the original video.
Published 01/11/10
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 discussed in Lecture 11a.
Published 01/11/10
In depth treatment of local alignment using dynamic
programming.
Published 01/10/10
Continuation of the discussion of how to compute similarity
and optimal sequence alignment using dynamic programming.
Local as well as global alignment.
Published 01/08/10