Email | Report an error! | Make suggestion

Update: these slides have been revised for content as of September 1, 2005. There are still many cosmetic glitches (e.g., odd font choices, improper use of boldface) and we will correct those in a future iteration. As usual, if you notice errors, feel free to report them to us or post them on the discussion boards.

The following slides are available in Adobe PDF (viewable with Acrobat or Acrobat reader) and as Microsoft PowerPoint.

Some of the images in these powerpoint presentations are from the book (© 2004 The MIT Press) and other sources (see references and acknowledements in the book). We welcome instructors to use these powerpoints for educational purposes, but please acknowledge the source and do not redistribute these slides on a separate website.

Quick links:


Molecular Biology (Ch 3)


A comprehensive introduction to molecular biology. Note: This is an extremely large file, so please view the web version first to see if you only need a few slides. If you need the entire PowerPoint, please realize that you're downloading a 15 Megabyte file, and if you need the PDF that you're downloading a 63 Megabyte file!


DNA Mapping (Ch 4)


Describes DNA mapping from a biological perspective, then considers some computational problems like the Partial Digest Problem (PDP).

Brute Force Motif Searching (Ch 4)


Introduces motif concepts. Describes two strategies for finding them: brute force search in "starting position space" and brute force enumeration of "median strings space".


Genome Rearrangements (Ch 5)


Describes what genome rearrangements are. Considers a few brute-force algorithms for solving the rearrangements problem, and also a greedy approach.

Introduces approximation algorithms.


Edit Distance (Ch 6)


Introduces Dynamic Programming with the following problems.

  1. The Manhattan Tourist problem (navigating a grid)
  2. The Change problem (converting some amount of change into the smallest number of coins)
  3. The edit distance problem
Alignment (Ch 6)


Describes alignment. Some of the material in this presentation covers material in the LCS and Edit Distance presentations as well.

Multiple Alignment (Ch 6)


Extends 2-sequence alignment to 3-sequence alignment, and shows why k-sequence alignment is inefficient.

Describes progressive multiple alignment through CLUSTALW, and how to score multiple alignments.

RNA (Ch 6)


Statistical methods for gene prediction (Ch 6)


Describes the reasoning behind statistical methods for gene prediction.

Covers in-frame hexamer count, TestCode, and mentions two popular programs.

Similarity-based methods for gene prediction (Ch 6)


Describes and compares two methods for gene predition: exon chaining and spliced alignment (of proteins (or mRNAs) to DNA).

Overviews five other popular tools: GenScan, GenomeScan, TwinScan, GenMark, Glimmer


Linear Space Alignment (Ch 7)


Describes the reduction of the quadratic-space requirement for naive DP algorithm into linear-space (by doubling computation time).


Graphs and DNA Sequencing (Ch 8)


Introduces the notion of a graph, and how it applies to the most important problem in biological data collection: DNA sequencing.

Mass Spectrometry and Proteomics (Ch 8)


Describes the background to mass spectrometry.

Introduces the spectral convolution algorithm and the spectral alignment algorithm.


Combinatorial Pattern Matching (Ch 9)




Clustering (Ch 10)



Molecular evolution (Ch 10)


Principles of molecular evolution.


Hidden Markov Models (Ch 11)




Randomized Algorithms (Ch 12)




About Us | ©2004 Neil Jones