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.
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.
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.
Finish the discussion of HMMs for CpG islands. Introductionto the Vitterbi algorithm (really dynamic programming)to find the most likely Markov Chain generating a givensequence.
Continuation of the topic of probability of matching.Here we look at the probability that a query stringmatches completely, at least once, in a much largerdatabase of strings.
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 c
We discuss the expected length of the longest common subsequencebetween two random strings of lengths n each, and show that it grows linearlywith n. This lecture originally contained a discussion both of the expected length of the longestco