Algorithmic Bioinformatics I (SS2015)

Content of the first three terms of the Bioinformatics or Computer Science studies.

At the end of the module, students are able to analyze algorithms and develop simple algorithms. Furthermore, they are capable of applying fundamental bioinformatics algorithms for sequence analysis and searching in texts and understanding the concept of NP-completeness.

Topics of Algorithmic Bioinformatics I are:

• Analysis of Algorithms: Asymptotic growth, Recurrences
• Design Techiques for algorithms: recursion, divide-and-conquer, dynamic programming, greedy algorithms, branch-and-bound
• String matching: Knuth-Morris-Pratt, Boyer-Moore, Karp-Rabin, Aho-Corsasik, Z-Algorithm
• Suffix-Trees/Tries/Arrays: construction (Ukkonens Algorithm) and applications
• Fragment Assembly, Partial (PDP) and double (DDP) digest problems
• Sequence analysis: pairwise sequence alignment (Needleman-Wunsch, Smith-Waterman, Gotoh) and scoring (edit distance, distance and similarity measures), motive search
• Multiple alignment (n-dim. DP; heuristic approaches; approximations; tree, consensus, profile and center star methods; DiAlign; ClustalW)
• NP-completeness: reducability, NP-complete problems in bioinformatics

The module consists of a lecture and in addition exercises in small groups. The concepts introduced in the lecture are practiced in the exercise class with concrete examples.

Description: written exam (successful solution of a fraction of home work assignments is required for passing the module)
Mode of exam: written
Length of exam: 90 min
Homework assignments: yes
A failed exam can be repeated at the end of the term.

To take the exam it is necessary to register for the exercise class until 22.04.15.
To pass the course you have to pass the exam. The grade of the course depends on the grade of the exam.
There is a written exam at the end of the semester. Prerequisite for the exam is the regular participation in the exercise class and to score 50% of the points on the exercise sheets.
The exam will be on the last lecture date of the semester in the usual lecture room.
An opportunity to retake a failed exam will be given on the first lecture date of Algorithmische Bioinformatik II in the respective lecture room.

Lecture slides can be found here

Homework assignments can also be found here.

Empfehlenswert ist zudem das Skript zur Vorlesung Algorithmische Bioinformatik I aus dem vorigen Jahr von Prof. Volker Heun.

• S. Aluru (Ed.): Handbook of Computational Molecular Biology, Chapman and Hall/CRC, 2006.
• H.-J. Böckenhauer, D. Bongartz: Algorithmische Grundlagen der Bioinformatik: Modelle, Methoden und Komplexität, Teubner, 2003.
• P. Clote, R. Backofen: Computational Molecular Biology - An Introduction, Wiley, 2000.
• P. Compeau, P. Pevzner: Bioinformatics Algorithms - An active learning approach, AL, 2014.
• R.C. Deonier, S. Tavare, M.S. Waterman: Computational Genome Analysis, Springer, 2005.
• R. Durbin, S. Eddy, A. Krogh, G. Mitchinson: Biological Sequence Analysis - Probabilistic Models of Proteins and Nucleic Acids, Cambridge University Press, 1998.
• D. Gusfield: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, Cambridge University Press, 1997.
• V. Heun: Algorithmische Bioinformatik, Skriptum, 2001-2015.
• N.C. Jones, P.A. Pevzner: An Introduction to Bioinformatics Algorithms, MIT Press, 2004.
• D.W. Mount: Bioinformatics - Sequence and Genome Analysis, Cold Spring Harbor Laboratory Press, 2001.
• P. Pevzner: Computational Molecular Biology - An Algorithmic Approach, MIT Press, 2000.
• J.C. Setubal, J. Meidanis: Introduction to Computational Molecular Biology, PWS Publishing Company, 1997.
• M.S. Waterman: Introduction to Computational Biology: Maps, Sequences, and Genomes, Chapman and Hall, 1995.