Schedule UCSC BME 205 Fall 2015

Bioinformatics: models and algorithms

(Last Update: 10:45 PST 7 December 2015 )

Lecture and Homework Schedule

The lecture schedule reflects the material actually delivered. Notes from last year are included as placeholders (because it was easier than stripping everything), but I'll try to clean up the schedule after each day's class. The upcoming lectures are likely not to be in exactly the same order as last year, as I try to adapt to questions from the class.


Date Lecture Topic(s) Due
Fri 2015 Sept 25administrivia, texts, assignments, structure of course.
Mon 2015 Sept 28stdin, #!, import sys, Python for loop and yield with examples of line-at-a-time input, immutability of strings, strip(), a little on docstring vs. comment intake survey
Wed 2015 Sept 30 Unix permissions. multiple returns as a tuple, 'foo'.startswith(), transferring files with rsync. Fundamental dogma and sequencing as a major source of bioinformatic data.
Error rates of information copying (polymerases):
DNA->DNA: Taq 1/125,000; Pfu 1/2,300,000; mitochondrial pol gamma ; 1/300,000-1/500,000; pol eta 1/18-1/38
RNA->DNA: HIV 1/1700-/8000; SIV 1/19,000; Accuscript RT 1/62,000
RNA->RNA: flu 1/10,000; Qbeta 1/3,000.
Ribosome: Ecoli 1/3000; generally 1/2000-1/20,000.
Fri 2015 Oct 2DNA sequencing technologies, with notes from
what is a probability function?
Python scaffold
Mon 2015 Oct 5feedback on 1st Python program. What is a stochastic model?
Wed 2015 Oct 7 Developing i.i.d. model for strings of fixed length. i.i.d model for arbitary length strings (separate length model and stop character model producing geometric distribution).
Fri 2015 Oct 9Fellowships, Markov chains. fasta/fastq parsing
Mon 2015 Oct 12Programming hints: internal representation must be the same no matter what input or output format used. Strive for clean decomposition, separating input from processing from output. Use of 'id=None' as sentinel for "if id is not None: yield ...", to avoid treating beginning of parsing as special case. print(*quals) vs print(' '.join(str(q) for q in quals))
Wed 2015 Oct 14 Review Markov chains. Use of length model or stop character to make all finite strings be event space. Joint probability for list of sequences using i.i.d. with distribution for each sequence being a Markov chain. Started optimizing log likelihood (MLE) using Lagrangian multipliers
Fri 2015 Oct 16 Use Lagrangian multipliers to get MLE for i.i.d. model using {A,C,G,T}. Uses of models (generation, classification, search). Need for "how well do model and data fit". coding cost, log-likelihood ratio, prior and posterior ratios. Coding cost, entropy, relative entropy. fellowship
Mon 2015 Oct 19 Answered questions about Markov chain assignment. Handwaving approach to pseudocounts as update to Dirichlet distribution over all models. Soft priors vs. stiff priors. Add-one prior.
Wed 2015 Oct 21questions about Markov chain assignment, Better than chance talk through example 1
Fri 2015 Oct 23 Better than chance almost completedMarkov chains
Mon 2015 Oct 26some feedback on Markov chain homework (my off-by-one error for unseen contexts), how to choose with from weighted choices in Python, developed model for palindromes
Wed 2015 Oct 28Finishing model for palindromes and how p-value and E-value are computed.
Fri 2015 Oct 30library session: Science and Engineering Library 215 null models
Mon 2015 Nov 2 Substitution matrices
Wed 2015 Nov 4 Questions about annotation assignment. Global gapless alignment.
Fri 2015 Nov 6 Local gapless alignment annotation paper
Mon 2015 Nov 9feedback on annotation paper, Local arbitrary-gap alignment.
Wed 2015 Nov 11class canceled—Veterans' Day
Fri 2015 Nov 13 Global arbitrary-gap alignment. palindromes
Mon 2015 Nov 16 explanation of A2M format, local linear-gap alignment.
Wed 2015 Nov 18 finish local linear-gap alignment. global linear-gap alignment. traceback in global linear-gap alignment.
Fri 2015 Nov 20
Mon 2015 Nov 23 log(e^x+e^y) algorithm, global affine-gap alignment with example.
Wed 2015 Nov 25 local affine-gap alignment with example, profiles as consensus of multiple-sequence alignment, profile alignment as same algorithm as affine-gap alignment.
Fri 2015 Nov 27Thanksgiving
Mon 2015 Nov 30 progressive alignment. intro to profile HMMs alignment
Wed 2015 Dec 2 GUEST LECTURE: Data Archiving. Intro to local alignment by modifying profile HMM. Intro to forward algorithm.
Fri 2015 Dec 4 Forward algorithm. Intro to backward algorithm.
Tues 2015 Dec 8, 7:30–10:30 exam slot, no classdegenerate codons (and all REDOs)

Topics from previous years we didn't get to: intro to EM, need for backward algorithm. Lagrangian multipliers to optimize P(x|theta) with constraints on emissions and transitions, derivation of backwards algorithm, Baum-Welch updates for emissions and transitions (no silent states). Protein stucture prediction (iterated search, sequence logos, neural nets for secondary structure), various protein local-structure alphabets, multi-track HMMs. quick overview of tree-building: phylogenetic an other types of hierarchical clustering, rooted vs.unrooted, outgroups, parsimony, maximum likelihood, distance-based mthods, simple distance function -log(1-4/3 DNA change), UPGMA, progressive alignments, neighbor-joining

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