Fundamental Algorithms in Bioinformatics

Lecture 1: Introduction to bioinformatics and the course Jan 01, 2010

Introduction to the course and bioinformatics. Why we do bioinformatics, how it relates to genomics and to the changing modalities of biology.

Lecture 2: Further introduction Jan 02, 2010

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.

Lecture 3: Defining sequence similarity Jan 03, 2010

Definition of sequence similarity and string alignment, counting alignments the need for fast computation.

Lecture 4: Extending the model of sequence similarity Jan 04, 2010

Review of the definition of sequence similarity and extensions of the model for greater biological fidelity. Introduction to parametric sequence alignment.

Lecture 5: Computing sequence similarity Jan 05, 2010

Introduction to computational efficiency. Introduction to how we actually compute sequence similarity efficiently.

Lecture 6: Computing similarity using an alignment graph Jan 06, 2010

Continuation of the discussion of how to efficiently compute the similarity of two sequences. Introduction to the traceback operation to find the optimal alignment.

Lecture 7: From alignment graphs to formal dynamic programming Jan 07, 2010

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.

Lecture 8: Sequence alignment using dynamic programming — continued Jan 08, 2010

Continuation of the discussion of how to compute similarity and optimal sequence alignment using dynamic programming. Local as well as global alignment.

Lecture 9: Local sequence alignment Jan 10, 2010

In depth treatment of local alignment using dynamic programming.

Lecture 10: End-gap-free alignment and whole-genome shotgun sequencing Jan 11, 2010

End-gap-free alignment using dynamic programming. Example from whole-genome shotgun sequencing.

Lecture 11a: Expected Length of the Longest Common Subsequence Jan 11, 2010

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.

Lecture 11b: Expected Length of the Longest Common Substring Jan 11, 2010

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.

Lecture 12: Expected longest common substring II Jan 12, 2010

Completion of the analysis of the expected length of the longest common substring in two random strings

Lecture 13: Probability of a complete query match in a database Jan 13, 2010

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.

Lecture 14: BLAST I Jan 14, 2010

Introduction to the ideas behind BLAST I.

Lecture 15: BLAST II Jan 15, 2010

Discussion of hashing kmers, E-values, statistics, BLAST II

Lecture 16: BLAST statistics Jan 17, 2010

E-values, extreme value distribution, probability of a match

Lecture 17: Probability and database search Jan 18, 2010

Further discussion of probability and database search. Granin and BRCA1 story. Database search used as a filter, not an oracle.

Lecture 18: Multiple sequence alignment I Jan 19, 2010

Start of discussion on Multiple Sequence Alignment. sum-of-pairs objective function. Dynamic program solution for three sequences. Program MSA

Lecture 19: Multiple sequence alignment II Jan 20, 2010

Continuation of multiple sequence alignment; sum-of-pairs objective function; tree consistency theorem; factor-of-two approximation.

Lecture 20: Multiple sequence alignment III Jan 21, 2010

The center tree method and analysis; progressive alignment, guide trees, CLUSTAL, uses of multiple alignment

Lecture 21: Uses of multiple sequence alignment Jan 22, 2010

Use of multiple sequence alignment to build a model of a set of biologically related sequences. Profiles, log-odds ratios.

Lecture 22: From profiles to Markov models Jan 23, 2010

Finish the discussion of profiles and log-odds ratios. introduction to Markov Models and Hidden Markov Models

Lecture 23: Hidden Markov models Jan 24, 2010

Hidden Markov models to identify CpG islands. This lecture follows the discussion in Durbin and Eddy.

Lecture 24: Hidden Markov models and the Vitterbi algorithm Jan 25, 2010

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.

Lecture 25: From the Vitterbi algorithm to the forward algorithm Jan 26, 2010

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.

Lecture 26: Hidden Markov models - The Backwards algorithm Jan 27, 2010

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.

Lecture 27: Introduction to evolutionary trees - Ultrametric trees Jan 28, 2010

lntroduction to trees that represent evolution. We start with the case of perfect data: the Ultrametric tree case.

Lecture 28: Algorithms for Ultrametric trees — molecular clocks Jan 29, 2010

Algorithms for constructing an Ultrametric Tree from an Ultrametric Matrix, and the relationship of ultrametrics to the molecular clock.

Lecture 29; Additive trees and the Neighbor-Joining algorithm Jan 30, 2010

Additive trees and their construction. The Neighbor-Joining algorithm and its use with near-additive data. Bootstrap values and their misuse.

Lecture 30: Maximum Parsimony and minimum mutation methods Jan 31, 2010

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.

Postscript: Where to go next Feb 01, 2010

Some suggestions of where the student can get more exposure to algorithms for bioinformatics and computational biology.

Our TOPPODCAST Picks

Follow Us

Stay Connected

Fundamental Algorithms in Bioinformatics

Related Podcasts

Links

Stay Connected