As this is an advanced topics course, there are no exams or final. Grades are based on homeworks (which stress algorithm design and analysis) and projects (which stress algorithm implementation and independent research). In an implementation project, a significant algorithm studied in class we will be programmed and evaluated. In a research project, an independent topic chosen by the student and instructor will be researched, written up, and presented. Programming project assignments specify an interface for a C++ class library, and are graded by checking correctness on test instances and measuring execution times.

• Hans-Joachim Böckenhauer and Dirk Bongartz,
  Algorithmic Aspects of Bioinformatics,
  Springer-Verlag, Berlin, 2007.
  (Surveys combinatorial algorithms in computational biology.)
  
  
• 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.
• Burroughs-Wheeler transform and its use in compression and exact string matching.
• 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, incremental string alignment, and genome 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   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.
• Next generation sequencing: assembling genomes from very short reads, and mapping reads to a reference genome.

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

VI   Evolutionary trees

• Tree construction: compatibility, maximum parsimony, maximum likelihood, and distance-based methods.
• Tree comparison: measuring similarity of differing trees, finding consensus trees.

VII   Structure prediction

• RNA secondary structure prediction: inferring structural base-pairing of RNA sequences.
• Protein secondary structure prediction: predicting alpha-helices and beta-strands in protein sequences.

• Homework 1, due February 16.
  
• Homework 2, due March 9.
  
• Homework 3, due April 13.
  

• Programming project, due May 9.

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.

Note that the due date for the programming project has been moved to May 9. The assignment for the project is been posted above.

To learn more about algorithms for bioinformatics, you are welcome to attend the Department's Computational Biology Seminar. This is a weekly journal club and research group meeting for students working with John Kececioglu.