Algorithms in Genome Research (Excerises)

392110 Linda Sundermann, Alexander Sczyrba Fr 8:30-12:00 in U10-146 ekvv


This class covers the basic algorithmic techniques used in the computational analysis of genome and post-genome data. This includes algorithms for genomic mapping and assembly, methods for functional genome annotation (gene finding and gene function prediction), algorithms for the analysis of DNA microarrays and mass spectra, methods and models for protein structure prediction, and algorithms for comparative genomics.


The page AlgGRLiterature contains many links to the original literature.

Script of the lessons hold by Veli Mkinen about genome scale algorithms.

Time table (lecture):

Date Topic Exercises
19.10.2012 Introduction, Logistics, Physical mapping Übungszettel 1
26.10.2012 Assembly I Übungszettel 2
02.11.2012 Assembly II Übungszettel 3
09.11.2012 Dynamic Programming Übungszettel 4
16.11.2012 High troughput mapping with Borrows-Wheeler indexes Übungszettel 5
23.11.2012 BWT-based approaches, Transcipt expression detection Übungszettel 6
30.11.2012 RNA sequencing, Overlap computation, MUMs Übungszettel 7
07.12.2012 HMMs Übungszettel 8
14.12.2012 Gene finding Übungszettel 9
21.12.2012 Phylogenetic footprinting Übungszettel 10
11.01.2013 RNASeq Übungszettel 11

Further material

Phylogenetic Footprinting
Paper from Blanchette et al.

Hands on Assembly
Nice website where you can cut out your reads and assemble them by hand:

Download PQTree.jar and run java -jar PQTree.jar -g n where n is the number of leaves for the initial PQ-Tree. Select the elements which shall appear consecutively by mouse click and Ctrl or shift in the list on the left side of the window. Then click Reduce to get the resulting tree. Use Reset to get the initial tree again. [Reference: J. Harris. A Graphical Java Implementation of PQ-Trees. (last visited 09/20/2006), April 2002. Carleton University. Debugged by Roland Wittler, Bielefeld University.]

De Bruijn graphs
Paper by Compeau et al.: How to apply de Bruijn grpahs to genome assembly

SOLiD sequencing and mapping
Next-generation sequencing: from basic research to diagnostics , Voelkerding et al., 2009
SHRiMP: Accurate Mapping of Short Color-space Reads , Rumble et al., 2009

Organisational Matters:

Together with the practical course “Bioinformatics Applications in Genome Research” in the following summer semester, this lecture forms the master module Algorithms in Genome Research.
The exercises will not be corrected or graded, but presence and activity during the exercise hours is expected. Credit points will be given based on an oral exam at the end of the semester.


Mündliche Prüfung ganztägig
Mündliche Prüfung ganztägig