Biological Sequence Analysis

582483
5
Bioinformatiikka
Syventävät opinnot
The course covers selected high-throughput methods for the analysis of biological sequences, including advanced alignment methods, Hidden Markov Models, and next-generation sequencing data analysis methods. Prerequisities: Basics of bioinformatics and algorithms.

Koe

28.02.2013 09.00 B123
Vuosi Lukukausi Päivämäärä Periodi Kieli Vastuuhenkilö
2013 kevät 14.01-21.02. 3-3 Englanti Veli Mäkinen

Luennot

Aika Huone Luennoija Päivämäärä
Ma 12-14 C222 Veli Mäkinen 14.01.2013-21.02.2013
To 10-12 C222 Veli Mäkinen 14.01.2013-21.02.2013

Harjoitusryhmät

Group: 1
Aika Huone Ohjaaja Päivämäärä Huomioitavaa
Ma 10-12 C222 Veli Mäkinen 14.01.2013—22.02.2013

Yleistä

Content

  • Mon 14.1 10-12: Background check, we'll solve some simple exercises online to check prerequisites.
  • Mon 14.1 12 -14: Lecture 1, Alignments revisited + shortest detour, sections 3.1, 3.3, 3.4.1, and 3.4.2.
  • Thu 17.1 10-12: Lecture 2, Invariant techniques, sparse dynamic programming, sections 3.2, 3.4.4, and 3.4.5.
  • Mon 21.1 10-12: Exercise 1: [PDF], [solutions]
  • Mon 21.1 12-14: Lecture 3, Markov chains, score schemes, log-odds, BLOSUM, GC-content, GC-skew, CAI [slides.pptx] [slides.pdf]
  • Thu 24.1 10-12: Lecture 4, Hidden Markov Models, forward, backward, sections 4-4.7
  • Mon 28.1 10-12: Exercise 2 [PDF]
  • Mon 28.1 12-14: Lecture 5, Baum-Welch, More complex HMMs, pair HMMs, sections 4.8-4.10.2
  • Thu 31.1 10-12: Lecture 6, Sampling, profile HMMs, sections 4.10.3-4.11.2
  • Mon 4.2 10-12: Exercise 3 [PDF]
  • Mon 4.2 12-14: Lecture 7, Advanced pseudocounts, Jumping alignments, Multiple alignment, Carol-Lippman msa, sections 4.11.2, 4.12, 3.6
  • Thu 7.2 10-12: Lecture 8,  High-throughput sequencing (HTS) overview, variant calling, Burrows-Wheeler transform, FM-index, search space pruning [slides.pptx] [slides.pdf] + sections 7.1 and 7.3.1
  • Mon 11.2 10-12: Exercise 4 [PDF]
  • Mon 11.2 12-14: Lecture9, RNA-sequencing, splice variants, transcriptomics, co-linear chaining, sections 7.1.4, 3.5, 7.3.3, 7.3.4
  • Thu 14.2 10-12: Lecture 10, ChIP-seq, PSSMs, motif discovery, projection method [slides.pptx] [slides.pdf]+ section 7.3.2
  • Mon 18.2 10-12: Exercise 5 [PDF] [solutions]
  • Mon 18.2 12-14: Lecture 11, Whole genome alignment, MEMs and MUMs  on suffix tree and on FM-index variants [slides.pptx] [slides.pdf] + sections 7.2-7.2.2 (just definitions, not the two-way BWT algorithms),  7.3.5 + suffix tree algorithms on blackboard for maximal repeats / exact matches / unique matches (see Gusfield's book) + dot plots, k-mer counting, FASTA, BLAST ideas.
  • Thu 21.2 10-12: Lecture 12, Algorithms for fragment assembly, section 7.2.3
  • Thu 28.2 9:00-, B123 EXAM; exam is now graded, see the 2nd floor announcement board.
  • Feedback session on Thursday 14.3 at 13.00 in room A239b. See my own thoughts about the course.
  • Check renewal / separate exam dates here: http://www.cs.helsinki.fi/exams

Kurssin suorittaminen

Course consists of lectures and exercises. Exam gives maximum 40 points, weekly exercises 20 points.  Grading is based on total points gathered.  However, to pass the course, one must pass the exam with at least 20 points.

Kirjallisuus ja materiaali

This course script covers most of the material and there will be couple of powerpoint slide sets in addition. Most lectures will be given on black board.

  • Script updated 21.1 (floor to ceil in shortest detour, a -1 added and initialization at 0,0 corrected at to affine gap cost computation formulae)
  • Script updated 24.1 (definition of P(c) added to generation probability at HMMs, condition "|" converted into joint prob. "," in matching probability as that is what is actually computed)
  • Script updated 1.2 (in pair HMM sampling, one v (viterbi) replaced by f (forward), to count the prob. of a transition correctly)
  • Script updated 4.2 (multiple alignment dynamic programming formula corrected)
  • Script updated 14.2 (ChIP-seq peak detection HMM emission probability corrected to binomial distribution... now it sums to 1)