UCSC BME 205 Fall 2015

Bioinformatics: models and algorithms

(Last Update: 23:06 PST 23 November 2015 )
link to homework
link to schedule
This is a required course for bioinformatics students—both undergraduate and graduate students (also prerequisite to BME 230). Those who need permission codes to register can get them on the first day of class.

For catalog copy and prerequisites, see the main page for BME205.

Who, When, and Where:

Instructor: Kevin Karplus ( karplus@soe.ucsc.edu) http://www.soe.ucsc.edu/~karplus
Office hours: PSB 318, W 4–5
TA: None this year

Lectures: MWF 12:30–1:40 PSB 305

On-line discussion: We have no forum set up for the class this year, but you can subscribe to a Google Groups mailing list bme205@soe.ucsc.edu or view on the web at https://groups.google.com/a/soe.ucsc.edu/d/forum/bme205


There will be no required texts, two optional texts, plus additional readings that will be distributed via the Web:
Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids from Cambridge University Press by R. Durbin, S. Eddy, A. Krogh, and G. Mitchison.
strongly recommended In past years I've required this textbook, and many students have found it to be an invaluable reference, both during the course and afterward.

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 graduate-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 (I have given suggestions below).

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

Python in a Nutshell, Second Edition By Alex Martelli July 2006 ISBN 10: 0-596-10046-9 | ISBN 13: 9780596100469

BME 205 will be using Python. You can use whatever book or online resource you need to learn the language. I recommend not buying Learning Python nor Programming Python by Mark Lutz, as both are really terrible for this class. It takes Lutz forever to get to the point of anything, and material is scattered in random order. I read over a hundred pages of Learning Python, was still not prepared to write even a short Python program, and was heartily sick of the Python boosterism. Python in a Nutshell is much better organized and gets to the point immediately, but is short on examples.

The best source I've found is the online documentation at http://docs.python.org/tutorial/, http://docs.python.org/reference/, and http://docs.python.org/library/. One Python user highly recommends the index http://docs.python.org/genindex.html, but I've done better using Google with "python" followed by the subject I'm interested in.

If you need a more tutorial introduction, I see that the undergrad course CMPS 5P has used Python for Software Design: How to think like a computer scientist by Allen Downey (Green Tea Press) as a text. An earlier manuscript of the book is available for free.

One of the Fall 2009 students recommended Dive into Python, a free on-line book for experienced programmers.

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. The description of sequence-sequence alignment and HMMs does not seem quite detailed enough for this class though.

Reading assignments

The following reading assignments in Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids by R. Durbin, S. Eddy, A. Krogh, and G. Mitchison are recommended, rather than required, but most students have found them helpful.

Date Have read these sections
28 Sept 2015 1.1–1.4
12 Oct 2015 11.1–11.6
19 Oct 2015 2.1–2.9
26 Oct 2015 3.1–3.6
8 Nov 2015 5.1–5.8
9 Nov 2015 4.1–4.5
16 Nov 2015 6.1–6.5
23 Nov 2015 7.1–7.6


Date (to be) releasedAssignmentDate Due
2015 Sept 14 prereq survey Mon 28 Sept 2015, 12:30p.m.
2015 Sept 14 Python scaffold Fri 2 Oct 2015, 12:30p.m.
2015 Sept 27 parsing FASTA and FASTQ Fri 9 Oct 2015, 12:30p.m.
2015 Sept 28 fellowship application Fri 16 Oct 2015, 12:30p.m.
2015 Oct 15 Markov chains Fri 23 Oct 2015 12:30p.m.
2015 Oct 22 null models Fri 30 Oct 2015, 12:30p.m.
2015 Oct 29 gene annotation Fri 6 Nov 2015, 12:30p.m.
2015 Nov 5 finding under/over-represented palindromes Fri 13 Nov 2015, 12:30p.m.
2015 Nov 12 affine-gap alignment Mon 30 Nov 2015, 12:30p.m.
2015 Nov 23 peptide libraries from degenerate codons Tues 8 Dec 2015 7:30pm

Every student in the class will need a School of Engineering computer account. I will want assignments turned in by providing me with a publicly readable file (PDF for written assignments) or directory (for multi-file assignments) containing the assignment on the SoE machines. All Python programs must execute correctly on the SoE machines, without needing to install additional Python modules. I will run the programs using python2.7 or python3.4, which is not the default python on most SoE machines (some of which have archaic versions like 2.4.3 as the default). Programs that fail to run (because they are Windows-formatted files or because permissions have been set wrong) will be returned ungraded, and will need to be redone.

I want paper copies of assignments in addition to the electronic ones (to save me the time and hassle of printing them), but I will accept electronic-only submissions from those who are too ill to attend class.

To get an SoE computer account see http://support.soe.ucsc.edu/new-accounts


There will be three types of assignments for the class:

As has been my practice since Fall 2001, there will be no exams, and we will probably not meet during the final exam period (Tues 8 Dec 2015, 7:30–10:30 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. In the past this has meant roughly equal weights for assignments, with the first programming assignment having somewhat less weight and the alignment assignment having somewhat more weight.

I expect that most of the assignments will be similar to ones given in previous years, with a few parts tweaked to update them, but I may replace one or more assignments with new ones, if I can think of new problems at the appropriate level of difficulty.

Academic Integrity

Anyone caught cheating in the class will be reported to their college provost (see UCSC policy on academic integrity) and may fail the class. Cheating includes any attempt to claim someone else's work as your own. Plagiarism in any form (including close paraphrasing) will be considered cheating. Use of any source without proper citation will be considered cheating. If you are not certain about citation standards, please ask, as I hate having to fail students because they were improperly taught how to cite sources.

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

Classroom Accommodations for Disabilities

If you qualify for classroom accommodations because of a disability, please submit your Accommodation Authorization from the Disability Resource Center (DRC) to me during my office hours in a timely manner, preferably within the first two weeks of the quarter. Contact DRC at 459-2089 (voice), 459-4806 (TTY).

Guest lectures

30 October 2015
Christy Caldwell, Finding information using the library resources. Meets in Science and Engineering Library 215
2 December 2015
Christy Caldwell, Practical Data Management. Module 1: Where to Start -- Data Planning, and Module 2: Description, Storing & Archiving. Meets in PSB 305.

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

Note: The schedule will be updated throughout the quarter to reflect what really happens.
  1. Quick review of the fundamental dogma of biology: DNA->RNA->protein, bases, codons, amino acids, ...
    (2 hours)
  2. Introduction to Python. Read the material at http://users.soe.ucsc.edu/~auzilov/BME205/Fall2011/ over the weekend and try to understand the code in the tarballs.
  3. 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)
  4. Constructing a model from data. Training, cross-training, and testing. Maximum-likelihood estimate. Pseudocounts to get mean posterior estimate. (1.5 hours)
  5. Converting arbitrary 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)
  6. Entropy, relative entropy, Mutual information, sequence logos. (1.5 hour)
  7. 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)
  8. Substitution matrices and sequence alignment scores. Aligning sequences to sequences, dynamic programming We'll do the the simple, but inefficient algorithm (for arbitrary 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)
  9. Introduction to Hidden Markov models (1.5 hour on HMMs and profiles) (1.5 hours on profile HMMs giving Viterbi algorithm and forward-backward)
  10. Pair HMMs as a way of explaining alignment algorithms (3 hours?)
  11. (Not scheduled yet) Guest lecture. Christy Caldwell 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. We may meet in the Science Library for the guest lecture.
  12. 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)
  13. 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)
  14. Fast methods for searching (BLAST and BLAT). (In some years, Jim Kent has given an excellent lecture on these.)
  15. Multiple alignment techniques: Muscle, Probcons, AMAP

    documentation on MUSCLE:
    http://www.drive5.com/muscle/docs.htm Refereed 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

    AMAP http://bio.math.berkeley.edu/amap
    Ariel S. Schwartz and Lior Pachter
    Multiple alignment by sequence annealing
    Bioinformatics 2007 23(2):e24-e29; doi:10.1093/bioinformatics/btl311

    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 Misawa, 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.

  16. 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)
  17. RNA structure and Stochastic Context-Free Grammars (1.5 hour)
  18. 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. The following two papers are the guts of the method:

    Rachel Karchin, Melissa Cline, Yael Mandel-Gutfreund, and Kevin Karplus. Hidden Markov models that use predicted local structure for fold recognition: alphabets of backbone geometry. Proteins: Structure, Function, and Genetics, 51(4):504–514, June 2003. doi:10.1002/prot.10369 reprint

    Rachel Karchin, Melissa Cline, and Kevin Karplus. Evaluation of local structure alphabets based on residue burial. Proteins: Structure, Function, and Genetics, 55(3):508–518, 5 March 2004. doi:10.1002/prot.20008 reprint

Topics for last week requested by students

Rough list of topics we didn't have enough time to do more than briefly mention in recent years.

Other resources on the web

UCSC Genome Browser—gateway to at least 47 eukaryotic genomes.
UCSC Microbial Browser—gateway to more than 300 archeal and bacterial genomes.
User's Guide to the Human Genome (in Nature Genetics).

SoE home
sketch of Kevin Karplus by Abe
Kevin Karplus's home page
Biomolecular Engineering Department
BME 205 home page UCSC Bioinformatics research

Questions about page content should be directed to Kevin Karplus
Biomolecular Engineering
University of California, Santa Cruz
Santa Cruz, CA 95064
318 Physical Sciences Building