Algorithmen der Bioinformatik
LecturersProf. Dr. Daniel Huson, Hans-Joachim Ruscheweyh and Mohamed El-Hadidi
LecturesMondays, 10:15-12:00, A302, Sand 1
Problem sessions

1) Wednesdays, 12:15-14:00, Seminarraum 1, Sand 6/7

2) Wednesdays, 14:15-16:00 Seminarraum 1, Sand 6/7

Target audienceMSc and diploma students in bioinformatics and computer science
ModulesSee "Modulhandbuch"
LanguageEnglish

Contents

Bioinformatics I focuses on concepts, data-structures and algorithms for sequence analysis.

Here is a tentative schedule:

DateContents, script and links to resourcesAssignments
15.10.2012

1. Introduction

What is bioinformatics

Assignment 1
17.10.2012

2. Pairwise sequence alignment

BLOSUM62 matrix

Additional reading:

Needleman-Wunsch algorithm

Smith-Waterman algorithm

22.10.2013continued

Assignment 2

Files 2

24.10.2012

3. BLAST and BLAT

Additional reading:

Original BLAST paper

29.10.2012continued

Assignment 3

Files 3

31.10.2012

4. Multiple sequence alignment

Additional reading:

BLOSUM matrices

Clustal-W

Benchmark study of MSA algorithms

5.11.2012continued

Assignment 4

Files 4

7.11.2012continued
12.11.2012

5. Suffix trees

Additional reading:

WOTD algorithm

MUMMER

Project assignment

Assignment 5
14.11.2012continued
19.11.2012continued

Assignment 6 (due 3.12.2012)

Practice exam handed out in class

21.11.2012continued
26.11.20126. Sequencing
28.11.2012Mid-term exam (cobering chapters 2-5)
3.12.2012

7. Genome alignment

Additional reading:

MAUVE

Paper on Yersinia involving Mauve

Assignment 7
5.12.2012

8. Sequence assembly

Additional reading:

Celera assembler

Velvet paper

10.12.2012continued

Assignment 8

reads.fna

ecoli-testrun-2000.fna

12.12.2012

9. Read mapping

Bowtie

Additional reading:

Bowtie2

17.12.2012

10.RNA-seq and mapping

Additional reading:

TopHat

Cufflinks

11. String matching

Assignment 10
19.12.2012continued
7.1.2013

No lecture

(will take place 17.1., 2-4pm)

(No assignment - please work on projects)
9.1.2013

No lecture

(will take place 24.1., 2-4pm)

14.1.2013

12. Phylogeny

Additional reading:

Neighbor-Joining

Fitch1971

Assignment 10
16.1.2013

continued

Projects due

17.1.2013

14-16h, in C118, Sand 14

continued
21.1.2013continued

Assignment 11

Files 11

23.1.2013continued

24.1.2013

14-16h, in C118, Sand 14

Project presentations

(first six, order as below)

28.1.2014

Project presentations

(remaining five)

30.1.2013

13. Metagenomics

Additional reading:

Megagenomics: Application of Genomics to Uncultured Microorganisms

Metagenomics Discovery of Biomass-Degrading Genes and Genomes from Cow Rumen

A human gut microbial gene catalogue established by metagenomic sequencing

RDP project

Naive Bayesian classifier for rapid assignment of rRNA sequences into the new bacterial taxonomy

MEGAN analysis of metagenomic data

Assignment 12

Files 12

4.2.2013

Free for exam preparation

(If you have questions, please arrange to meet with your tutor between 10 and 12)

6.2.2013Final exam (covering chapters 6-13)

Recommended textbooks

(none of them covers the whole course)

  • Hodgeman, Frence and Westhead, Instant Notes- Bioinformatics, Taylor and Francis, second edition, 2012.
  • Neil C. Jones, Pavel A. Pevzner: An Introduction to Bioinformatics Algorithms. MIT Press, 2004.
  • Richard Durbin, Sean R. Eddy, Anders Krogh, and Graeme Mitchison: Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge UP, 1998.
  • Pierre Baldi, Soren Brunak: Bioinformatics: The Machine Learning Approach. MIT Press, 1998.
  • Dan Gusfield: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge UP, 1997.

How to get credit for this course

  • Always participate in the weekly problem sessions and actively present your results.
  • Pass the mid-term exam
  • Pass the final exam
  • Work on and successfully present a project
  • You may work on and hand-in assignments in groups of up to two people.
  • Assignments are set every Monday and are due on the following Monday, 10 am.
  • Your final grade is determined as follows: 20 % assignments, 20 % project, 30 % mid-term exam, 30 % final exam.

Student projects

As part of this course each participant will work on a small project. The aim is to work through a topic, produce a 3-10 page (10 page max) description of results and a 10-15 minute presentation to the class. The progress of your project will be discussed in the weekly tutorials. Due date for slides and description is the 16.01.2013. Prior discussion with tutor is strongly recommended.

Student NameTopicTutor
Sebastian Nagel Pairwise alignment: Global, local and overlap alignmentMohamed El-Hadidi
Jie JuPairwise alignment: linear space and K-BandHans-Joachim Ruscheweyh
Andrej GawrischenkoMSA: sum of pairs and dynamic proframmingMohamed El-Hadidi
Sonja HaegeleMSA: progressive alignmentHans-Joachim Ruscheweyh
Manuel RuffBLASTMohamed El-Hadidi
Qiunan ShenSequence assembly using velvetMohamed El-Hadidi
Marian TheissSuffix trees: how to build themHans-Joachim Ruschweyh
Wei Ding Suffix trees: MUMsHans-Joachim Ruscheweyh
Sebastian LehnererSuffix trees: inexact repeatsHans-Joachim Ruscheweyh
Tanja KrumpeRead mapping using bowtieMohamed El-Hadidi
Mirjam Gutekunst RNA-seq analysis using TopHatMohamed El-Hadidi