CSE 549 - Introduction to Computational Biology

This is a course in algorithmic issues in biology, focusing current problems in genomics. Our emphasis will be algorithmic, on discovering appropriate combinatorial algorithm problems and the techniques to solve these problems. Primary topics will include DNA sequence assembly, DNA/protein sequence comparison, hybridization array analysis, RNA and protein folding, and phylogenic trees.

The prerequisites for this course will be a course in combinatorial algorithms (CSE 373/548 or equivalent) or a strong background in biology. I hope to get a mix of students from the computational and life sciences.

There is a symposium on Biomedical technology for a global age being held at Stony Brook on Wednesday September 26, 2007. Check out the program.

To study for the midterm I recommend you look at an old example midterm and the problems on the old Homeworks 1 and 2 given below.

Another course of interest being taught in Fall 2007 is AMS 535, "Introduction to Computational Structural Biology and Drug Design", taught by Robert Rizzo. He will be teaching a companion course (AMS-536, "Molecular Modeling of Biological Molecules") in Spring 2008. AMS-536 is designed for students who wish to gain hands-on experience modeling biological molecules at the atomic level. In conjunction with the participants' interest, Molecular Mechanics, molecular dynamics, Monte Carlo, Docking (virtual screening), or Quantum Mechanics software packages will be used. Projects will include setup, execution, and analysis. Students will work on individual projects outside of class.

Finally, another course of possible interest for Spring 2008 is AMS 691, Foundations of Algorithms and Numerical Methods in Computational Biology, taught by David Green. This class will survey many of the key techniques used in diverse aspects of computational biology. We will focus on how to successfully formulate a statement of the problem to be solved, and how that formulation can guide in selecting the most suitable computational approach. A set of problems from a diverse range of problems in biology will be used as examples.

The final exam will be held December 20, 2007 between 2PM-4:30PM.

Course Documents

• Course syllabus (also in pdf )
• Lecture Schedule
• Course project list (also in pdf )

Lecture Notes

The following lecture notes are provided in HTML and pdf, with audio:

• Lectures 1/2: Biology for Computer Scientists, Computer Science for Biologists (also in pdf ) Audio for Lectures 1 (9/3/02) and 2 (9/5/02).
• Lectures 3/4/5: Fragment Assembly and Suffix Arrays (also in pdf ) Audio for Lectures 3 (9/12/02) 4 (9/19/02), and 5 (9/24/02)
• Lectures 6/7/8/9: Homology Search (also in pdf ) Audio for Lectures 6 (9/26/02) 7 (10/1/02), 8 (10/3/02), and 9 (10/8/02) Sample Blast output.
• Lectures 10/11/12: Gene Prediction (also in pdf ) Audio for lectures 10 (10/10/02) 11 (10/15/02), and 12 (10/17/02). Sample Genemark output.
• Lectures 13/14/15/16: Microarrays (also in pdf ) Audio for lectures 13 (10/22/02), 14 (10/24/02), 15 (10/29/02), and 16 (10/31/02).

  Thanks to Paul Fodor for photos for our class tour of Bruce Futcher's microarray laboratory on November 4, 2004.

• Lecture 17/18/19: RNA and protein folding (also in pdf ) Audio for lectures 17 (11/5/02), 18 (11/12/02), and 19 (11/14/02).

  Lecture notes from a guest lecture on proteins by Rob Rizzo, AMS (11/9/06) are available. Interesting related WWW pages include Fink's and Levitt's lecture notes.

• Lecture 20: Motif finding and multiple sequence alignment (also in pdf ) Audio for lecture 20 (11/19/02).
• Lecture 21: Protein shapes and docking (also in pdf ) Audio for lecture 21 (11/21/02).
• Lecture 22-25: Phylogenic trees and evolution (also in pdf ) Audio for lectures 22 (12/3/02), 23 (12/10/02), and 24 (12/12/02),

Homework Assignments

Note: homework assignments will not be collected in Fall 2006. I do encourage all to review the assignments as preparation for the midterm and final.

• Homework 1: Assembly and Data Bases (also in pdf ). Source code for the Contig Assembler Program (CAP) is available here, read the inline comments for documation. The answer key is now available.
• Homework 2: Sequence Comparison and Gene Prediction (also in pdf ). Source code for a C language dynamic programming program for edit distance computation is is available here.
• Homework 3: Clustering (also in pdf ). Supplemental material includes a brief introduction to R by Dimitris Papamichail, which focuses on clustering commands, as well as a codon distribution dataset on a collection of bacteria.

Student Presentations

• Genbank and Perl presentations by Andriy Tovkach and Alex Smirnov. (September 10, 2002)
• Protein Folding Program presentation by Asim Okur with audio (the last 35 minutes of the file) (November 14, 2002)
• Photos from course field trip. (November 7, 2002). Thanks to Alexey Smirnov for the pictures.
• Guest lecture by Ilya Vaksar on protein docking, with audio (the first 40 minutes of the file) (November 26, 2002)
• Swiss-Prot, protein docking, Weblab Viewer, PDB presentations by Wei Liu, Wang Yuanpeng, and Fang Xu with audio (the last 35 minutes of the file) (November 26, 2002)

General Resources

• The Bioinformatics Education Resource contains powerpoint presentations, practical bioinformatics problems, implementation problems, sample implementations, and problem solutions.
• The Genetic Science Learning Center at the University of Utah has a lot of information about biotechnologies and genetic diseases.

Books

• Jones and Pevzner, An Introduction to Bioinformatics Algorithms MIT Press, 2004.

The following books are recommended:

• Gusfield, Algorithms on Strings, Trees, and Sequences : Computer Science and Computational Biology, , Cambridge University Press, 1997.
• Durbin, Eddy, Krogh, and Mitchison, Biological Sequence Analysis : Probabilistic Models of Proteins and Nucleic Acids , Cambridge University Press, 1998.

• Setabal and Meidanis Introduction to Computational Biology , PWS, 1997.
• Claverie and Notredame, Bioinfomatics for Dummies, For Dummies Press, 2003.
• Pevzner, Computational Molecular Biology: An Algorithmic Approach, MIT Press, 2000.
• Dwyer, Genomic Perl Cambridge Univ. Press, 2003
• Mount, Bioinformatics: Sequence and Genome Analysis, Cold Spring Harbor Laboratory, 2001
• Bishop and Rawlins DNA and Protein Sequence Analysis : A Practical Approach , Oxford University Press, 1997.
• Baxevanis and Ouellette, Bioinformatics , Wiley, 1998
• Sankoff and Kruskal, Time Warps, String Edits, and Macromolecules , CSLI Publications 1999 (reprint).
• Watson, Gilman, Witkowski, and Zoller, Recombinant DNA , Scientific American Press, 1992.
• Skiena, The Algorithm Design Manual Springer Verlag, 1998.

Related courses at other Universities

• Computational Biology, CSE 527, University of Washington, Winter 2000. Taught by Martin Tompa.
• Algorithms for Computational Biology, (236606) Technion, Israel, Spring 1998. Taught by Benny Chor.
• Computational Molecular Biology, Bio 5495/BME 537 Washington University, Spring 2000.
• Algorithms for Computational Biology, Tel-Aviv University, Fall 1999, Taught by Ron Shamir.
• Topics in Computational Molecular Biology, Dartmouth University, Computer Science 88/188 Spring, 2000 Taught by Bruce Donald.

Join the Algorithm Reading Group (CSE 642) at Stony Brook!