CSE 549 - Introduction to Computational Biology

Fall 2013
Course Time: 4-5:20PM Tuesday-Thursday
Place: W4330 Melville Library
Instructor: Steven Skiena

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.

The course TA will be Rukhsana Yeasmin. Her office hours are Monday 3-4:30PM and Wednesday 4-5:30PM in the Laufer Center room 100 (the big room). Contact her by email at ryeasmin@cs.stonybrook.edu.

The CS 549 Final Exam will Be Monday 12/16 from 2:15-5:00 pm in the normal classroom.

Course Notes

• The permanent site for 549 videos is https://www3.cs.stonybrook.edu/~skiena/549/finallectures. Check them out! They are also available on YouTube with my other courses.
• See this excellent writeup on Hidden Markov Models
• Watch the excellent videos on transcription and translation of DNA.
• Michael Schatz's lecture notes from his lecture on the Burroughs-Wheeler transform are available here and here.
• The lab tour will be held Tuesday November 26 at 4PM. Meet in the lobby of the Life Science building and wait for Prof. Futcher to escort you.
• To study for the midterm I recommend you look at an old example midterm and the problems on the Homeworks 1 and 2 given below.
• I encourage students to take advantage of the CSHL's SBU-friendly meeting policy to attend conferences/meetings at Cold Spring Harbor Laboratory.
• 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.
• This ridiculous, CS-centric view of DNA might be helpful to some.

Course Documents

• Course syllabus
• Lecture Schedule
• Course project list (updated: now the Fall 2013 projects!)

Homework Assignments

• Homework 1: Assembly and Data Bases

  The answer key is now available.

• Homework 2: Sequence Comparison and Gene Prediction . Source code for a C language dynamic programming program for edit distance computation is is available here. Check out the dynamic programming problems as practice for the midterm.

  The answer key is now available.

  General Resources

  • Rosalind is a platform for learning bioinformatics algorithms through problem solving.
  • 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

  The textbook for this course will be:
  • 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.
  Additional books of possible interest are:
  • 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

  • Stanford
  • University of Washington
  • Johns Hopkins
  • UC Riverside
  • MIT
  • Tufts
  • RPI
  • Brown
  • Univ. of Texas
  • Univ. of Bristol
  • Cornell
  • Columbia