Biostatistics & Medical Informatics 776
Computer Sciences 776
Advanced Bioinformatics (Spring 2004)

General Course Information

Instructor: Thomas Anantharaman tsa@biostat.wisc.edu Office: 6720 Medical Sciences Center Phone: 608-3470637 Office Hours: 4pm-5pm Tuesday and Thursday, or by appointment (Cancelled 3/29/05)\ TA: Lidan Wang lidan@biostat.wisc.edu Office: 6763 Medical Sciences Center Office Hours: 4pm-5pm Monday, 2-3pm Wednesday and Friday (Cancelled Feb 1-14) Meeting Time and Location: 1:00pm-2:15pm Tuesday and Thursday 3534 Engineering Hall Note: On 4/14 the class meets at 1325 Computer Science! Course Mail Archive Readings: required text: Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. R. Durbin, S. Eddy, A. Krogh, and G. Mitchison. Cambridge University Press, 1998. other readings from the primary literature Midterm Exam: 1:00 PM, March 17, In Class Final Exam: 2:45 PM, Sunday, May 8, 2005, LOCATION: AGR ENG 101

Course Overview

The biological sciences are undergoing a revolution in how they are practiced. In the last decade, a vast amount of data (DNA sequences, protein sequences, etc.) has become available, and computational methods are playing a fundamental role in transforming this data into scientific understanding.

Bioinformatics (Also called Computational Biology or Computational Molecular Biology) involves developing and applying computational methods for managing and analyzing information about the sequence, structure and function of biological molecules and systems.

The goals of this two-course series are to provide an understanding of:

• the types and sources of data available for computational biology,
• the fundamental computational problems in molecular biology and genomics,
• a core set of widely used algorithms in computational biology,
• a set of algorithms that have important applications in computational biology, but which have key applications outside of biology as well.

Course Requirements

• homework assignments (4): 40%
• midterm exam: 25%
• final exam: 35%

Syllabus, Readings and Lecture Notes

• Probabilistic Sequence Models
  • topics: Pairwise alignment using HMMs, Profile HMMs, Multiple Alignment by profile HMM training, semi Markov models, interpolated Markov models, EM for motif finding, Gibbs sampling.
  • required reading
    • Chapter 4, R. Durbin et al.
    • Chapter 5, R. Durbin et al.
    • Section 6.5, R. Durbin et al.
    • S. Salzberg, A. Delcher, S. Kasif, and O. White. Microbial Gene Identification Using Interpolated Markov Models. Nucleic Acids Research 26(2):544-548, 1998.
    • C. Burge and S. Karlin. Prediction of Complete Gene Structures in Human Genomic DNA. Journal of Molecular Biology 268(1):78-94.
    • T. Bailey and C. Elkan. The Value of Prior Knowledge in Discovering Motifs with MEME(PDF). In Proceedings of the 3rd International Conference on Intelligent Systems for Molecular Biology, pp. 21-29, 1995.
    • C. Lawrence, S. Altschul, M. Boguski, J. Liu, A. Neuwald, and J. Wootton. Detecting Subtle Sequence Signals: A Gibbs Sampling Strategy for Multiple Alignment. Science 262:208-214, 1993.
  • Optional reading
    • S. Schmidler, J. Liu and D. Brutlag. Bayesian Segmentation of Protein Secondary Structure. Journal of Computational Biology 7(1-2):233-248, 2000.
  • lecture notes
    • General Course Information (1/20)
    • Pairwise Alignment using HMMs (1/25,1/27)
    • Profile HMMs (1/27,2/1,2/3)(Updated 2/2)
    • Microbial Gene Identification using Interpolated Markov Models (2/10)
    • Gene Prediction in Human Genomic DNA (2/8,2/10)
    • Sequence Motifs using EM and Gibbs sampling (2/15,2/17)
• Advanced Sequence Alignment
  • topics: banded alignments, PSI-BLAST, whole genome alignment, multiple whole genome alignment, Motif Finding.
  • required reading
    • S. Altshul, T. Madden, A. Schaffer, J. Zhang, Z. Zhang, W. Miller and D. Lipman. Gapped BLAST and PSI-BLAST: A New Generation of Protein Database Search Programs. Nucleic Acids Research 25(17):3389-3402, 1997.
    • A. Delcher, S. Kasif, R. Fleischmann, J. Peterson, O. White and S. Salzberg. Alignment of Whole Genomes. Nucleic Acids Research 27(11):2369-2376, 1999.
    • M. Höhl, S. Kurtz and E. Ohlebusch. Efficient Multiple Genome Alignment. Bioinformatics 18:S312-S320, 2002.
    • J. Buhler and M. Tompa. Finding Motifs Using Random Projections. Journal of Computational Biology 9(2):225-242, 2001.
  • lecture notes
    • Gapped BLAST and PSI-BLAST (2/17,2/22)(Updated 3/16/05)
    • Whole Genome Comparison (2/24)
    • Suffix Trees (3/1,3/3)(Updated 3/16/05)
    • Motifs by Random Projections(3/3)
• Probabilistic Approaches to Phylogeny
  • required reading
    • Chapter 8 in Durbin et al.
  • lecture notes
    • Probabilistic Phylogeny-I+II (3/8,3/10,3/15,3/29)
• RNA Structure Modeling
  • topics: RNA secondary structure prediction, Covariance Model
  • required reading
    • Chapter 10 (sections 3 and up) of Durbin et al.
  • lecture notes
    • RNA structure prediction (3/31,4/5,4/7)
• Probabilistic Gene Expression Analysis
  • required reading
    • N. Friedman, Linial, I. Nachman, and D. Pe'er. Using Bayesian Networks to Analyze Expression Data. Journal of Computational Biology, 7:601-620, 2000.
    • E. Segal, R. Yelensky and D. Koller. Genome-wide discovery of transcriptional modules from DNA sequence and gene expression. In Proceedings of the Seventh Annual International Conference on Computational Molecular Biology (RECOMB), 2003.
  • lecture notes
    • Probabilistic Gene Expression analysis (4/12,4/14,4/19)
• Biomedical Text Analysis
  • required reading
    • H. Shatkay, S. Edwards, W. J. Wilbur and M. Boguski. Genes, Themes and Microarrays: Using Information Retrieval for Large-Scale Gene Analysis. In Proceedings of the 8th International Conference on Intelligent Systems for Molecular Biology, pp. 317-328, 2000.
    • SM. Skounakis, M. Craven, S. Ray Hierarchical Hidden Markov Models for Information Extraction In Proceedings of the 19th International Joint Conference on Artificial Intelligence
  • lecture notes
    • Biomedical Text Analysis - I (4/21,4/26)
    • Biomedical Text Analysis - II (4/26,4/28)

Homework Assignments

• Assignment #1 Due 2/23 (Originally 2/16)
• Assignment #2 Due 3/15 (Originally 3/12)
• Assignment #3 Due 4/11
• Assignment #4 Due 5/6

• Homeworks are due by 11:59pm. Use electronic handin as described with each homework.
• Each student has five free late days to use during the semester (Also Sat-Sun and UW-Holidays will not count as late days). Once these are exhausted, late homeworks will be penalized 10% per day.
• No homeworks will be accepted more than one week late (excepting UW-Holidays).
• If you submit the 4th homework late, your initial grade will be an incomplete and your final grade will be submitted late.

Sample Exams

• Sample Midterm With Answers (Updated 3/16/05)
• Sample Final Notes with Answers

Academic Misconduct:
All examinations, programming assignments, and written homeworks must be done individually. Cheating and plagiarism will be dealt with in accordance with University procedures (see the Academic Misconduct Guide for Students). Hence, for example, code for programming assignments must not be developed in groups, nor should code be shared. You are encouraged to discuss with your peers, the TAs or the instructor ideas, approaches and techniques broadly, but not at a level of detail where specific implementation issues are described by anyone. If you have any questions on this, please ask the instructor before you act.