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.

Course Notes

• Prof. Ken Dill will present a seminar entitles "Exploring the Physical Principles of Protein Folding" next Tuesday, November 3, 2009. This seminar will be held in the Chemistry Building, Room 412, at 4PM.
• Olivia Judson writes a terrific blog on evolutionary biology at the New York Times, which I strongly recommend to all. Particularly relevant for our class is The Fantasy Genome Project.
• 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.
• The final exam will be held December 18, 2009 between 11:15AM-1:45PM.

Course Documents

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

Lecture Notes

We will be using the ``new'' lecture notes in class, but the older notes provided in html with audio accompaniment.

• Lectures 1/2/3: Biology for Computer Scientists, Computer Science for Biologists (new and old versions) Audio for Lectures 1 (9/3/02) and 2 (9/5/02).
• Guest lectures by Michael Hadjiargyrou on proteomics (9/15/09) and David Green on systems biology (9/17/09).
• Lectures 4/5/6/7: Fragment Assembly and Suffix Arrays (new and old versions) Audio for Lectures 3 (9/12/02) 4 (9/19/02), and 5 (9/24/02)
• Lectures 8/9/10/11: Homology Search (new and old versions) Audio for Lectures 6 (9/26/02) 7 (10/1/02), 8 (10/3/02), and 9 (10/8/02) Sample Blast output.
• Lectures 12/13/14: Gene Prediction (new and old versions) Audio for lectures 10 (10/10/02) 11 (10/15/02), and 12 (10/17/02). Sample Genemark output.
• Lectures 15/16/17/18: Microarrays (new and old versions) 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 2009. 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!