CSCI 4490/6490 Algorithms for Computational Biology
Instructor : Liming Cai
Fall, 2003

This course studies discrete algorithms applied to solving computational problems in molecular biology. Topics drawn from the application include biological sequence comparison, multiple sequence alignment, phylogeny reconstruction, RNA and protein structure prediction, structural alignment, and structural homology search in databases. As most biological analyses are statistical, this course also emphasizes on probabilistic models for biological sequences and their structures upon which feasible algorithms can be derived. No prior knowledge in molecular biology is required for taking this course.

CSCI 6470/4470 Algorithms, or permission of the department

Texts:

Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Durbin, Eddy, Krogh, and Mitchison. 1998. Cambridge University Press.

• Bioinformatics: The Machine Learning Approach, 2nd Edition. Baldi and Brunak. 2001. MIT Press.
  
• Computational Molecular Biology: An Algorithmic Approach. P.A. Pevzner. 2000. MIT Press.
  
• Introduction to Computational Biology: Maps, Sequences, and Genomes. M.S. Waterman. 1995. Chapman and Hall.
  
• Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. 1997. Cambridge University Press.
  
• Computational Molecular Biology : An Introduction. Clote and Backofen. 2000. John Wiley.
  

Three written assignments + two small application projects: 30%
One research project (structure prediction: code + report + presentation): 50%
Final exam: 20%


All homework answers need to be typed or word-processed.
Late homework answers will not be accepted.

Tentative schedule:

Part I. Introduction (molecular biology and probability): Chapter 1 (1 week)
part II.Hidden Markov Model and algorithms: Chapters 2-6 (4 weeks)
pairwise sequence alignment
profile HMM
multiple sequence alignment
similarity search

Part III. Phylogenetic tree reconstruction: Chapters 7-8 (3 weeks)
Part IV. Stochastic grammar models and algorithms Chapters 9-10 (5 weeks)
RNA stem-loop prediction
RNA pseudoknot prediction
profile grammar models
multiple structural alignment
structural homology search

It is expected that the work you submit is your own. Plagiarism and other forms of academic dishonesty will be handled within the guidelines of the Student Handbook. The usual penalty for academic dishonesty is loss of credit for the assignment in question; however, stronger measures may be taken when conditions warrant.

Attendance policy:

Regular class attendance is required though class attendance may not be used in the final determination of grades. Students are required to attend class during the regularly scheduled tests and the final exam unless prior arrangements have been made.