This course studies discrete algorithms applied to solving computational biology problems. Different from theoretical algorithms, computational biology algorithms use practical means targeting at specific biological problems, which include probabilistic modeling and computationa techniques to cope with computational intractability. Topics drawn from the application include sequence comparison, multiple alignment, gene prediction, DNA (and peptide) sequencing, genomics, genome rearrangement, phylogeny reconstruction, structure prediction, and (structural) homology search in databases. In particular, The following algorithmic techniques will be discussed: dynamic programming, greedy algorithms, tree decomposition based graph algorithms, and combinatorial algorithms. No prior knowledge in molecular biology is required for taking this course.

• CSCI 4470/6470 Algorithms or permission of the department
  

Reference Materials:

• An Introduction to Bioinformatics Algorithms. Jones and Pevzner. MIT Press 2004
  
• Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Durbin et al. Cambridge University Press 1999.
  
• Introduction to Computational Biology: Maps, Sequences, and Genomes. Waterman. Chapman & Hall/CRC 1995.
• Research papers

Presentations/discussions: 25%
Programming projects/reports: 50%
Final exam/project: 25%

Tentative schedule:

1. A molecular biology primer
   (guest lectures by Dr. Russell Malmberg), (1-2 weeks).
2. Dynamic programming algorithms for sequence comparisons
   (pairwise alignment, local alignment, multiple alignment, repeat finding), (3 weeks).
3. Probabilistic model based algorithms for pattern findings
   (HMM for motifs, SCFG for RNA secondary structures, Viterbi, forward-backward, CYK, inside-outside algorithms), (3 weeks).
4. Combinatorial algorithms for structural genomics
   (divide-and-conquer, LP for protein tertiary structure prediction), (2 weeks).
5. Parameterized algorithms for various computational biology problems
   (tree decomposition based algorithms for RNA structure search, protein threading, haplotyping, peptide sequencing, pathway inference, gene duplication, and RNA folding), (4 weeks).

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.