CENTER FOR ALGORITHMIC SYSTEMS
MSc Programme ``Computing Science"
Seminar: Algorithmic Computational Biology (MACB)
(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
- Lecturer: prof.dr Jan van Leeuwen.
Peter van den Berg,
Arne de Both,
Max van Boxel,
Mircea Cretu Stancu,
Luuk van der Graaff,
Dafne van Kuppevelt,
Duncan van Roermund,
- 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
- 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.
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.
- Monday, 23 April
Speaker: Jan van Leeuwen.
- Thursday, 26 April
Speaker: Jan van Leeuwen.
- Ch 3 (Basic concepts: strings, graphs, approximation algorithms, Motwani's
- Monday, 30 April
No class: Koninginnedag.
- Thursday, 3 May
Speakers: Jacob Swenson (A), group (B).
- Assignment: begin choosing topic/paper(s) for
your term paper
Specifications are listed here.
- Monday, 7 May
Speakers: Peter van de Berg (C), Arne de Both (D)
- Thursday, 10 May
No class: meeting European Forum for ICST.
- Monday, 14 May
Speakers: Max van Boxel (E), Mircea Cretu Stancu (F)
- Thursday, 17 May
No class: Ascencion Day (Hemelvaartsdag)
- Friday, 18 May
Assignment: topic/paper(s) for your term paper
- Monday, 21 May
Speakers: Luuk van der Graaff (G), Ioannis Katsikarelis (H)
- Thursday, 24 May
Speakers: Thomas Krak (I), Dafne van Kuppevelt (J)
- Monday, 28 May
No class: herkansingsweek (and Tweede Pinksterdag)
- Thursday, 31 May
No class: herkansingsweek
- Monday, 4 June
Speakers: Jaap Landheer (K), Fotios Paraschiakos (L)
- K: Sect 7.2 to Subsect 7.2.1 (Fingerprinting, mapping with unique probes,
- L: Subsect 7.2.2 to Subsect 7.2.3 (Mapping with unique probes and errors,
mapping with non-unique probes,
- Thursday, 7 June
Speakers: Justin Paston-Cooper (M), Thom Klaasse (N)
- Monday, 11 June
Speakers: Duncan van Roermund (O), Jan van Leeuwen (P)
- 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,
- R: Sect 9.3 to Sect 9.4 (Frequent and infrequent substrings, Hidden Markov
- 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,
Bulteau et al,
- T: Sect 11.1 to Sect 11.2 (Phylogenetic trees, ultrametric distances, additive
- Thursday, 21 June
Speakers: Arne de Both - Max van Boxel (U), Luuk van der Graaff - Duncan van
- U: Sect 11.3 to Sect 11.4 (Binary states, parsimony principle, quartet method,
- V: Sect 12.1 (Inferring haplotypes from a population,
Bafna et al,
Ding et al,
- Monday, 25 June
Speakers: Fotios Paraschiakos - Justin Paston-Cooper (W), all participants (X)
- 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)
- Z: Strict deadline: Monday morning, July 2nd, 09.00 AM. (Mailbox closed after
- 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
- 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
- Monday, 2 July
No class: tentamenweek
- Thursday, 5 July
No class: tentamenweek
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