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 11a: Expected Length of the Longest Common Subsequence

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.

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

Postscript: Where to go next

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.

Lecture 30: Maximum Parsimony and minimum mutation methods

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

Lecture 29; Additive trees and the Neighbor-Joining algorithm

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

Lecture 28: Algorithms for Ultrametric trees — molecular clocks

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

Lecture 11a: Expected Length of the Longest Common Subsequence

Download our free app to listen on your phone