As this is an advanced topics course, there are no exams or final. Grades are based on homeworks (which stress algorithm design), and programming projects (which stress algorithm implementation). Each project implements a significant algorithm studied in class. Project assignments specify an interface for a C++ class library, and are graded by checking correctness on test instances, comparing solution values of near-optima, and measuring execution times.

• Peter Clote and Rolf Backofen,
  Computational Molecular Biology: An Introduction,
  John Wiley and Sons, Chichester, England, 2000.
  (Broad coverage of recent material with an emphasis on probability and optimization.)
  
  
• Richard Durbin, Sean Eddy, Anders Krogh, and Graeme Mitchison,
  Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids,
  Cambridge University Press, New York, 1998.
  (Emphasizes hidden Markov models for sequence comparison.)
  
  
• Pavel Pevzner,
  Computational Molecular Biology: An Algorithmic Approach,
  MIT Press, Cambridge, Massachusetts, 2000.
  (In-depth treatment of genome rearrangements.)
  
  
• David Sankoff and Joseph Kruskal, editors,
  Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison,
  Addison-Wesley, Reading, Massachusetts, 1983.
  (A classic collection on sequence comparison and its applications.)
  
  
• João Setubal and João Meidanis,
  Introduction to Computational Molecular Biology,
  PWS Publishing, Boston, 1997.
  (A broad survey of computational biology for computer scientists.)
  
  
• Michael Waterman,
  Introduction to Computational Molecular Biology: Maps, Sequences and Genomes,
  Chapman and Hall, London, 1995.
  (In-depth treatment of the statistics of sequence comparison.)

I   Exact string matching

• Suffix arrays and a linear-time construction algorithm.
• Suffix trees and linear-time construction from a suffix array.
• Applications to static and dynamic string matching, longest k-common substrings, and finding all maximal repeats.

II   Approximate string matching

• Preliminaries: edit distance, reduction to string alignment, solution by dynamic programming; equivalence of minimizing distance and maximizing similarity; recurrences for database searching and local similarity.
• Fundamentals: linear gap-costs, linear-space alignment, unit-cost edits, and heaviest common-subsequences.
• Advanced techniques: convex gap costs, suboptimal alignments, the four-Russians technique, and incremental string alignment.

III   Multiple sequence alignment

• Generic multiple alignment and the five basic objective functions.
• Exact and approximation algorithms for the sum-of-pairs, fixed-tree, and maximum-trace objectives.

IV   Physical mapping

• Reconstructing order: mapping with unique, non-unique, and non-overlapping probes.
• Reconstructing distance: mapping with non-overlapping probes.

V   Sequence assembly

• Shortest common superstring: approximation with respect to compression and length; relation to computational learning theory.
• Shotgun sequencing: approximation with respect to compression; double-barreled sequencing; separating repeats.

VI   Genome rearrangement

• Inversions: signed and unsigned variations; exact and approximation algorithms.
• Translocations: centromere variations; exact and approximation algorithms.
• Putting it all together: mixed inversion, translocation, fission, and fusion.

• Suffix arrays, due April 8.

• Homework 1, due March 4.
  
• Homework 2, due May 6.
  

When you turn in solutions to homeworks write only on one side of the paper and staple your pages together. (Do not fold them!) Neatness and especially conciseness in your write-up is required to earn the highest marks. If you are tempted to ramble at length about ideas that don't quite work, please don't: points will be taken off. If you cannot solve a problem admit this up-front in your write-up, and write down only what you know to be correct.

If you'd like to learn more about algorithms applied to molecular biology, you might consider attending the department's Computational Biology Seminar.