Fundamental Algorithms in Bioinformatics

Some suggestions of where the student can get more

exposure to algorithms for bioinformatics and computational biology.

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.

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

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

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

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. Introduction

to the Vitterbi algorithm (really dynamic programming)

to find the most likely Markov Chain generating a given

sequence.

Hidden Markov models to identify CpG islands. This

lecture follows the discussion in Durbin and Eddy.

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

and Hidden Markov Models