This is an advanced 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 548 or equivalent) or a strong background in biology. I hope to get a mix of students from the computational and life sciences.

Course Documents

• Course syllabus
• Lecture Schedule
• Course project list
• Post or read the CS 648 bulletin board.

Lecture Notes

The following lecture notes are provided in HTML:

• Lectures 1/2: Biology for Computer Scientists, Computer Science for Biologists
• Lectures 3/4: Fragment Assembly and Suffix Arrays
• Lectures 5/6/7: Homology Search
• Lectures 8/9: Gene Prediction
• Lectures 10-12: Microarrays
• Lecture 13: Protein and Lecture 14: RNA folding Interesting related WWW pages include Fink's and Levitt's lecture notes.
• Lecture 15: Multiple sequence alignment
• Lecture 16: Protein shapes and docking
• Lecture 17-19: Phylogenic trees and evolution

Student Presentations

• Genbank and Bioperl presentations by Manpreet S. Katari and Sean McCorkle. (September 12, 2000)
• Phred, Phrap, Drosophila, and Celera's genome assembler, presentations by Johannes Jaeger, Gregorio Valdez, and Rohan Fernandes. See also Myers, et.al.'s paper on the Whole-Genome Assembly of Drosophila. A local PDF copy is also available. (September 21, 2000)
• Blast, Fasta, GCG presentation by Alexander Butler and Christine Vander Zwan (October 5, 2000)
• Genmark and Grail presentation by Lucas Carey and Prem Uppuluri (October 12, 2000)
• Stony Brook and CSHL microarray tour notes and pictures by Craig Laramee and Ingrid Koh. (October 24, 2000)
• presentation by Xiangqun Ning , Chengyu Liang , and Jinghui Zhan . (November 2, 2000)
• RNA and CASP-3, and protein folding presentation by Sumantro Ray and Brian Bowen. Vinhthuy Phan. (November 14, 2000)
• Mass Spectrometry presentation by Mark Essel, Jim Dwulit, Anthony Sommese. (November 28, 2000)
• Swiss Prot, PDB presentation by Jiang Yin and Jenny Hizver (November 30, 2000)
• Phylip and other phylogenic software presentations by Jacqueline Cantwell, Jonathan Danieley, and Song Xiang (December 14, 2000)

General Resources

• The Gene Almanac from the DNA Learning Center at Cold Spring Harbor Laboratory
• A beginner's guide to genomics from the Centre for Integrated Genomics
• A beginner's guide to the human genome project from Oak Ridge National Laboratory
• A nice codon table applet in Java gives usage frequencies for all different species.
• The early September issue of Science's Next Wave focuses on the explosion of career opportunities in bioinformatics. David Botstein (Stanford University) was their guest for a live online chat event on September 12 at 4:00pm.
• There is a very interesting art exhibit "Parardise Now: Picturing the Genetic Revolution" at Exit Art, 548 Broadway, New York through October 28th. I recommend it. Also check out the Gene Art site.
• See the following interesting site on cluster algorithms
• There are a variety of interesting activities at DIMACS special year in computational biology, including a talk by Gene Myers on whole genome assembly on October 26, 2000 as part of a workhop on Bioconsensus.

Books

There is no textbook for this course, but the following books are relevant, and the first two particular 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.
• 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 652) at Stony Brook!