(In case of considerable interest in the seminar, participants will be working in groups of two or three for the presentations part of the seminar. The term papers remain individual assignments.)

• Seminar:
  • Lecturer: prof.dr Jan van Leeuwen.
  • Participants: Peter van den Berg, Arne de Both, Max van Boxel, Mircea Cretu Stancu, Luuk van der Graaff, Ioannis Katsikarelis, Thom Klaasse, Thomas Krak, Dafne van Kuppevelt, Jaap Landheer, Fotios Paraschiakos, Justin Paston-Cooper, Duncan van Roermund, Jacob Swenson.
  • Time:
    • Monday   13.15-15.00, in: BBL 075, and
    • Thursday   9.00-10.45, in: BBL 075.
  • First meeting: Monday, April 23, 13.15-15.00 (in: BBL 075).
• Term paper: instructions; topics: see topics (this page).
• Grades: overview
• Office: BBL 505, tel. 030-2534001, office hours: by appointment, email: -- (email address no longer active).
• Form 1, form 2.
• Back to main.

Weekly schedule

Sections etc refer to the seminar text. Indicated sections are tentative.
The sections from the book are required reading for all. Other references are for additional study.
NB to means up to and including.

Week 17

• Monday, 23 April
  Speaker: Jan van Leeuwen.
  • Introduction (administrivia, scope, schedule).
  • Ch1 (Introduction, central dogma of molecular biology, see also here, Bioinformatics notes).
  • Ch 2 (Basics of molecular biology, Helsinki notes).

• Thursday, 26 April
  Speaker: Jan van Leeuwen.
  • Ch 3 (Basic concepts: strings, graphs, approximation algorithms, Motwani's notes).

Week 18

• Monday, 30 April
  No class: Koninginnedag.

• Thursday, 3 May
  Speakers: Jacob Swenson (A), group (B).
  • A: Sect 4.1 to Sect 4.3 (String matching, Boyer-Moore algorithm, Horspool's algorithm).
  • B: Sect 4.4 (Suffix trees, Ukkonen's algorithm).

• Assignment: begin choosing topic/paper(s) for your term paper
  Specifications are listed here.

Week 19

• Monday, 7 May
  Speakers: Peter van de Berg (C), Arne de Both (D)
  • C: Sect 4.5 (Further applications of suffix trees, overview, Ko-Aluru).
  • D: Sect 4.6 (Suffix arrays, dynamic suffix arrays).

• Thursday, 10 May
  No class: meeting European Forum for ICST.

Week 20

• Monday, 14 May
  Speakers: Max van Boxel (E), Mircea Cretu Stancu (F)
  • E: Subsect 5.1.1 to Subsect 5.1.3 (Alignment of two strings, Needleman-Wunsch, Wilbur-Lipman, Smith-Waterman, Myers-Miller).
  • F: Sect 5.1.4 to Sect 5.2 (Heuristic methods, Lipman-Pearson yielding FASTA, Altschul et al yielding BLAST, alignment software).

• Thursday, 17 May
  No class: Ascencion Day (Hemelvaartsdag)

• Friday, 18 May
  Assignment: topic/paper(s) for your term paper selected now.

Week 21

• Monday, 21 May
  Speakers: Luuk van der Graaff (G), Ioannis Katsikarelis (H)
  • G: Subsect 5.3.1 to Subsect 5.3.2 (Multiple alignments, Räihä-Ukkonen)
  • H: Subsect 5.3.3 (Combining multiple alignments, Feng-Doolittle, Gusfield).

• Thursday, 24 May
  Speakers: Thomas Krak (I), Dafne van Kuppevelt (J)
  • I: Sect 7.1 to Subsect 7.1.1 (Restriction site mapping, double digest approach, Goldstein-Waterman, Cieliebak-Eidenbenz-Woeginger)
  • J: Subsect 7.1.2 to Subsect 7.1.3 (Partial digest approach, overview, Lemke-Werman, Zhang)

Week 22

• Monday, 28 May
  No class: herkansingsweek (and Tweede Pinksterdag)
  
• Thursday, 31 May
  No class: herkansingsweek

Week 23

• Monday, 4 June
  Speakers: Jaap Landheer (K), Fotios Paraschiakos (L)
  • K: Sect 7.2 to Subsect 7.2.1 (Fingerprinting, mapping with unique probes, Booth-Lueker, overview)
  • L: Subsect 7.2.2 to Subsect 7.2.3 (Mapping with unique probes and errors, mapping with non-unique probes, Manuch-Patterson)

• Thursday, 7 June
  Speakers: Justin Paston-Cooper (M), Thom Klaasse (N)
  • M: Sect 8.1 to page 182 (Shotgun sequencing, shortest common superstring problem, Tammi, Gallant-Maier-Storer)
  • N: page 182/183 to page 189 (Greedy algorithm, Tarhio-Ukkonen, Blum et al)

Week 24

• Monday, 11 June
  Speakers: Duncan van Roermund (O), Jan van Leeuwen (P)
  • O: page 190 to page 196 (Cycle cover algorithm, overview, Mucha)
  • P: Subsect 8.1.3 to Sect 8.2 (Sequence reconstruction, sequencing by hybridization, Kececioglu, Blazewicz et al, Ben-Dor et al.)

• Thursday, 14 June
  Speakers: Peter van de Berg - Thom Klaasse (Q), Thomas Krak - Dafne van Kuppevelt (R)
  • Q: Sect 9.1 to Sect 9.2 (Similar substrings, tandem repeats, Li-Ma-Wang, Benson, Main-Lorentz)
  • R: Sect 9.3 to Sect 9.4 (Frequent and infrequent substrings, Hidden Markov Models, Yemini)

Week 25

• Monday, 18 June
  Speakers: Ioannis Katsikarelis - Jacob Swenson (S), Mircea Cretu-Stancu - Jaap Landheer (T)
  • S: Sect 10.1 to Sect 10.4 (Genome rearrangements, sorting undirected permutations, Sorting directed permutations, syntenic distance, Caprara, see also here, Hannenhalli-Pevzner, Bulteau et al, Dasgupta et al)
  • T: Sect 11.1 to Sect 11.2 (Phylogenetic trees, ultrametric distances, additive trees, Ciortuz, overview)

• Thursday, 21 June
  Speakers: Arne de Both - Max van Boxel (U), Luuk van der Graaff - Duncan van Roermund (V)
  • U: Sect 11.3 to Sect 11.4 (Binary states, parsimony principle, quartet method, Gusfield, Fitch, Buneman, Steel, Jiang-Kearney-Li, Strimmer-von Haeseler, Cilibrasi-Vitanyi)
  • V: Sect 12.1 (Inferring haplotypes from a population, what is, Bafna et al, Ding et al, implementations, overview)

Week 26

• Monday, 25 June
  Speakers: Fotios Paraschiakos - Justin Paston-Cooper (W), all participants (X)
  • W: Sect 12.2 (Haplotyping a single individual, Lancia et al, Lippert et al, Rizzi et al)
  • X: evaluation.

• Thursday, 28 June
  Speakers: All participants (Y)
  • Y: Final session, flash talks: 5-minute summaries of chosen topics (`what is it about', `what type of results', `what is your opinion').

• Friday, 29 June
  Assignment: term papers on assigned topic/paper(s) due.
  • Z: Strict deadline: Monday morning, July 2nd, 09.00 AM. (Mailbox closed after this.)

  Topics:

  • Peter van de Berg -> S. Kim: "A survey of computational techniques for genome sequencing", 2002.
  • Arne de Both -> S. Schbath: "Mapping reads on a genomic sequence: An algorithmic overview and a practical comparative analysis", 2012.
  • Max van Boxel -> H.L. Chan et al: "The mutated subsequence problem and locating conserved genes", 2005.
  • Mircea Cretu Stancu -> P.W.H. Wong et al: "An efficient algorithm for optimizing whole genome alignment with noise", 2004.
  • Luuk van der Graaff -> B. Kun et al: "A practical distributed string matching algorithm architecture and implementation", 2005.
  • Ioannis Katsikarelis -> L. Cai et al: "Parameterized complexity and biopolymer sequence comparison", 2008.
  • Thom Klaasse -> J.D. Kececioglu et al: "A polyhedral approach to sequence alignment problems", 2000.
  • Thomas Krak -> P. Fariselli et al: "A new decoding algorithm for hidden Markov models improves the prediction of the topology of all-beta membrane proteins", 2005.
  • Dafne van Kuppevelt -> J. Henderson et al: "Finding Genes in DNA with a Hidden Markov Model", 1997.
  • Jaap Landheer -> K-B. Schürmann, J. Stoye: "An incomplex algorithm for fast suffix array construction", 2007.
  • Fotios Paraschiakos -> P.E.C. Compeau et al: "How to apply De Bruijn graphs to genome assembly", 2011.
  • Justin Paston-Cooper -> T. Akutsu, S. Miyano: "On the approximation of protein threading", 1999.
  • Duncan van Roermund -> M. Weinard, G. Schnitger: ""On the Greedy Superstring Conjecture", 2006.
  • Jacob Swenson -> Z. Zhang et al: "A greedy algorithm for aligning DNA sequences", 2000.

Week 27

• Monday, 2 July
  No class: tentamenweek

• Thursday, 5 July
  No class: tentamenweek

Disclaimer:

This website is intended for educational purposes only. Linked documents should be cited by their original reference. We explicitly distance ourselves from the contents of any documents or websites this website, or any other related website maintained by us, links to outside of our own realm and declare that we do not adopt those contents as our own nor accept any responsibility for them.

Last modified: June, 2012