For catalog copy and pre-requisites, see the main page for BME205.

Who, When, and Where:

Lectures: MWF 11-12:10 Crown 105PSB 305
We may have a weekly lab session, to help people with programming assignments, if a time can be found to schedule it (my schedule is looking pretty tight this quarter).

Texts

Programming Perl
Larry Wall, Tom Christiansen & Jon Orwant
latest edition
O'Reilly and Associates

Considered the best single book on PERL—this is the main reference work on the language, and every PERL programmer should have a copy of it handy. You may use other PERL tutorials or references, but I expect you to have easy access to this one. We will be covering just the basics of PERL, not open-source packages like BioPerl, which you may wish to learn on your own.

Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids from Cambridge University Press by R. Durbin, S. Eddy, A. Krogh, and G. Mitchison.

This book is a tutorial introduction to the use of hidden Markov models and other probabilistic models for sequence analysis problems in computational molecular biology, but is aimed mainly at a gradauate-student audience. We've been using it for years in this class, and have not yet found as detailed a text.

This is a text and reference book that every bioinformatics programmer should have. I don't follow the book very closely, so you will have to figure out for yourself when it is appropriate to read various sections.

Get the second edition, if you can, which has made corrections as indicated on the errata page.

Darling models

I added some assignments in 2003 to build physical models of peptides (and DNA base pairs) using the Darling model kits. These kits are available over the web at http://www.darlingmodels.com/ I recommend getting the "Biochemistry" kit, though the cheaper "protein alpha helix--pleated sheet" kit may suffice. I have found these kits to give me a much better insight into protein flexibility and rigidity than the standard ball-and-stick models used in organic chemistry classes, and they are fun to play with. To reduce costs, it is quite reasonable for students to share a kit.

Note: the science library now has Darling model kits that you can check out! Also, several of the more advanced graduate students may be willing to lend their model kits.

Some initial instructions for building a protein backbone with this model kit are available.

An Introduction to Bioinformatics Algorithms
Neil Jones and Pavel Pevzner
MIT Press

This is book came out in summer 2004. It looks like it may be a valuable supplementary text, as it seems to be easier to read and at a slightly less advanced level than the Durbin et al. book.

Reading assignments

Date	Have read these sections
3 Oct 2007	1.1–1.4
10 Oct 2007	11.1–11.6
19 Oct 2007	2.1–2.9
24 Oct 2007	3.1–3.6
31 Oct 2007	5.1–5.8
7 Nov 2007	6.1–6.5
14 Nov 2007	7.1–7.6

Homework

Date released	Assignment	Date Due
28 Sept 2007	prereq survey	28 Sept 2007
30 Sept 2007	perl1 (FASTA parsing)	12 Oct 2007
7 Oct 2007	fellowship application	2619 Oct 2007
7 Oct 2007	Darling models	1926 Oct 2007
25 Oct 2007	perl2 (Markov chains)	2 Nov 2007
1 Nov 2007	perl3 (hashes and modules)	9 Nov 2007
5 Nov 2007	web and literature search	16 Nov 2007
16 Nov 2007	perl4 (null models) (post-assignment: see perl4.gnuplot	21 Nov 2007
16 Nov 2007	perl5 (affine-gap alignment)	30 Nov 2007
16 Nov 2007	perl6 (finding palindromes)	7 Dec 2007

Evaluation

• reading assignments,
• pencil-and-paper exercises,
• programming exercises to learn PERL, and
• bioinformatics exercises using real data.

Based on the first running of the course in Fall 2001, there will be no exams, and we will not meet during the final exam period (Wed 12 Dec 2007, 4-7 p.m.) It turns out to be very difficult to make up small enough problems for examination—almost all the homework exercises are much larger problems than could reasonably be given on a timed exam.

The assignments will be distributed on the web.

The relative weights of the different types of assignment in the evaluation has not been determined yet—it should be roughly proportional to how much time the different assignments take to do well. I will try to assign points to each assignment as it is given, but the total number of points won't be known until I've created all the assignments.

Academic Integrity

Collaboration without explicit written acknowledgement will be considered cheating. Collaboration on lab assignments with explicit written acknowledgement is encouraged—guidelines for the extent of reasonable collaboration will be given in class.

Classroom Accomodations for Disabilities

Rough list of topics we'll probably cover (not necessarily in order)

MONDAY 8 Oct 07

Not an official class meeting, but there is an NSF fellowship proposal-writing workshop at 4:00-6:00pm in the Muwekma Ohlone Conference Room C, Bay Tree Conference Center. Since you will have to write a fellowship or grant proposal of some sort this quarter, the workshop may well be worth your time.

1. Quick review of the fundamental dogma of biology: DNA->RNA->protein, bases, codons, amino acids
   (3-4 hours)
2. Stochastic models, Bayes Rule, 0-order Markov chain, first-order Markov chain, length model versus stop character for finite strings, use of log-probability for computations, adding probabilities in log-prob representation (efficient computation of log(exp(x)+exp(y)) ). (1.5 hour)
3. Constructing a model from data. Training, cross-training, and testing. Maximum-likelihood estimate. Pseudocounts to get mean posterior estimate. (1.5 hours)
4. Converting abitrary scores to stochastic models: P-value and E-value. Brief discussion of Z-scores (Gaussian dist.) and fat tails of extreme-value (Gumbel dist.) (1.5 hour)
5. Entropy, relative entropy, Mutual information, sequence logos. (1.5 hour)
6. What fellowship reviewers look for. Relationship between relative entropy and difference in encoding cost in a train/test framework (clarification for homework exercise). Interpreting classification results: true/false positives, specificity, sensitivity, ROC curves, ROC_n numbers What is a substitution matrix? (1.5 hour)
7. Substitution matrices and sequence alignment scores. Aligning sequences to sequences, dynamic programming We'll do the the simple, but inefficient algorithm (for aribtrary gap costs) first. (1 hour: Blosum substitution matrices and gapless scoring) (1 hour: the alignment problem and global dynamic programming with arbitrary gap costs) (1 hour: global dynamic programming with linear gap costs, traceback) (1 hour: affine gap costs. Global and local dynamic programming)
8. Introduction to Hidden Markov models (1.5 hour on HMMs and profiles) (1.5 hours on profile HMMs giving Viterbi algorithm and forward-backward)
   See powerpoint slides by Rachel Karchin (not used in class this year).
9. Dirichlet Mixtures (1.5 hours) See http://www.soe.ucsc.edu/research/compbio/dirichlets/dirichlet-papers.html for papers and http://www.soe.ucsc.edu/research/compbio/dirichlets/ for general information about Dirichlet mixtures.
10. Halloween, Oct 31.Guest Lecture in the Science Library. Science librarians will give a presentation on bioinformatics resources available through the library, as well as talking about some of the challenges that face the UCSC library in building an adequate collection in new fields like bioinformatics.
11. Protein secondary structure (DSSP and STRIDE), in order to explain second track of 2-track HMM. Discuss secondary structure prediction using neural nets. (1.5 hours)
12. Sequence weighting (Henikoff's technique for relative weighting and target bit savings for total weight) (1 hour) Multiple alignment techniques Overview and progressive alignment (0.5 hour)
13. Multiple alignment techniques Muscle and Probcons (I may choose other modern multiple aligners this year)
    

    documentation on MUSCLE:
    http://www.drive5.com/muscle/docs.htm Referreed paper: Edgar, Robert C. (2004), MUSCLE: multiple sequence alignment with high accuracy and high throughput, Nucleic Acids Research 32(5), 1792-97.

    PROBCONS web site (including overview of algorithm): http://probcons.stanford.edu

    Oher multiple alignment programs:
    paper on T-coffee:
    T-Coffee: A novel method for fast and accurate multiple sequence alignment.
    Notredame C, Higgins DG, Heringa J.
    J Mol Biol 2000 Sep 8;302(1):205-17

    paper on MAFFT:
    Kazutaka Katoh, Kazuharu Misawa1, Kei-ichi Kuma and Takashi Miyata. MAFFT: a novel method for rapid multiple sequence alignment based on fast Fourier transform. Nucleic Acids Research 30(14):3059-3066, 2002.

14. Phylogeny: brief mention of maximum-likelihood and parsimony. Additivity assumption. UPGMA algorithm presented, ultrametric assumption and molecular clocks, intro to neighbor-joining (no proofs) (1.5 hour)
15. RNA structure and Stochastic Context-Free Grammars (1.5 hour)
16. A protocol for evaluating local structure alphabets. This talk ( http://www.soe.ucsc.edu/~karplus/papers/local-structure-germany02.pdf) presented some of the main results from Rachel Karchin's PhD thesis.

Rough list of topics we didn't have enough time to do more than briefly mention last year:

• Contact order and folding rate. In 2001, I handed out paper on contact order:
  Contact order, transition state placement and the refolding rates of single domain proteins.
  Plaxco KW, Simons KT, Baker D.
  J Mol Biol 1998 Apr 10;277(4):985-94
• Phylogenetic analysis
• DNA microarrays and expression data
• Gene finding
• Proteomics
• RNA structure
• DNA assembly
• Fast methods for searching (BLAST and BLAT). (In 2001, Jim Kent gave an excellent lecture on these.)
• RNA genes, DNA microarrays, computational and functional genomics Look at the BME 210 course, the BME 230 course, and the lab pages for Todd Lowe and Josh Stuart.
• Combining secondary structure, fold-recognition, and new-fold methods for protein structure prediction. Using the transparencies given at Schloss Dagstuhl. I could have handed out book chapter on SAM-T2K, but didn't.

Other resources on the web

http://genome.ucsc.edu/

UCSC Genome Browser - gateway to over 27 complete genome sequences

http://archaea.ucsc.edu/

UCSC Archaea Browser - gateway to all archeal and many prokaryotic genome sequences

http://genome-test.cse.ucsc.edu/eng/

Getting Started on the UCSC Genome Project Team

User's Guide to the Human Genome (in Nature Genetics).

SoE home

Kevin Karplus's home page

BS, MS, and PhD programs

BME 205 home page

Karplus's lab page

UCSC Bioinformatics research

Questions about page content should be directed to