Computational Biology: Alignments and Sequencing (SS 15)
Biologists collect ever more data which we can only hope to evaluate using computers. In particular, there are huge databases of DNA and RNA resp. fragments thereof, which we model as strings. The sheer amount of data and size of individual records demands especially efficient algorithms if we want to obtain results in a timely fashion.
This course contains computer science methods for dealing with strings. This includes
- computing similarities of strings,
(suffix trees and their applications) - finding approximate matches and
(pairwise and multiple alignments) - reconstructing texts from overlapping fragments.
(partial digest and double digest methods, PQ-trees, shortest common superstrings)
We always bear in mind to keep complexities low.
It is a 4 ECTS entry-level master course with accompanying tutorials; find details in the official documents.
Registration
In order to participate in the exercise classes, you are required to register in the OLAT system.
Dates
Lectures and exercise sessions will be held throughout the reading period, that is from Apr 21st to Jul 21st. Individual sessions will take place weekly on
- Lecture: Tuesdays, 10:00 - 11:30 in 48-654
- Exercise Class (bi-weekly): Tuesdays, 13:45 - 15:15 in 48-654, starting on May 12th.
Note: There will be no lecture on June 9th and July 21st (new!). The exercise on July 21st has been moved to July 22nd, 15:30 in the usual room (new!).
Exercises
Exercises are organized by Robert.
There will be exercise sheets with problems relating to the current lecture material.
Lecture Notes
Here you can download the content of the electronic blackboard from class as pdf.
Exam
There will be oral exams at the end of the semester, please contact us in time to make an appointment. You need 40% of the achievable points in the exercises to be allowed to take the exam.
Suggested Reading
German lecture notes covering all course material are available in print; ask us for it!
Apart from the lecture notes, the following text books cover most of the course's content:
- R. Durbin, S. Eddy, A. Krogh, G. Mitchison: Biological Sequence Analysis
Cambridge University Press, 1998 - D. Gusfield: Algorithms on Strings, Trees, and Sequences
Cambridge University Press, 1997
Previous Iterations
Advanced Algorithmics (SS 15)
Complexity theory tells us that there are problems that seem to be inherently hard to solve. What can we do when faced which such a problem in practice? Over the decades, some useful techniques for tackling hard problems have emerged, for example
- using heuristics to limit search spaces,
- accepting wrong outputs with certain probability and
- accepting suboptimal but still decent solutions.
We follow these approaches and develop theoretical foundations for solving hard problems sufficiently well and fast in practice.
This is an 8 ECTS advanced-level master course; find details in the official documents.
Dates
Lectures and exercise sessions will be held throughout the reading period, that is from April 20th to July 24th. Individual sessions will take place weekly on
- Mondays, 10:00 - 11:30 in 48-654 (lecture),
- Wednesdays, 10:00 - 11:30 in 48-654 (lecture) and
- Fridays, 15:30 - 17:00 in 48-654 (exercises)
Note that we will not meet on public holidays, i.e. May 1st and May 25th. We will notify you about replacement dates and other exceptions on a case-by-case basis.
Exercises
There will be weekly exercise sheets with problems relating to the current lecture material. You can hand in your solutions for grading. We will discuss the exercise problems in weekly exercise sessions, provided sufficient participation. Your TA will be Raphael.
Participation is optional. Register via email to Raphael.
Material
| Week | Transcripts* | Exercises | Hands-On |
|---|---|---|---|
| I | L1, L2 | Sheet 1 | Sheet 1, Data |
| II | L3, L4 | Sheet 2 | Sheet 2 |
| III | L5, L6, E1 | Sheet 3 | — |
| IV | L7, L8, E2 | Sheet 4+ | Sheet 3 |
| V | L9, L10, E3 | Sheet 5 | Sheet 4 |
| VI | L11, E4 | Sheet 6 | — |
| VII | L12, L13, E5 | Sheet 7 | Sheet 5 |
| VIII | L14, E6 | Sheet 8 | — |
| IX | L15, L16, E7 | Sheet 9 | — |
| X | L17, L18, E8 | Sheet 10 | Sheet 6 |
| XI | L19, L20, E9 | Sheet 11 | — |
| XII | L21, L22, E10 | — | — |
| XIII | L23, E11 | — | — |
| XIV | E12, E13 | — | — |
+ Changed after first hand-out.
Find the Git repository used for collaboration on the hands-on sheets here. Please clone the repository and issue pull requests if you want to contribute.
Exams
There will be oral exams. Please contact Prof. Nebel towards the end of the lecture period to inquire about possible dates.
Suggested Reading
- D. Hochbaum: Approximation Algorithms for NP-Hard Problems
ISBN: 978-0-534-94968-6, available in our library (key text) - J. Hromkovič: Algorithmics for Hard Problems
ISBN: 978-3-642-07909-2, available in our library (key text) - V. Vazirani: Approximation Algorithms
ISBN: 978-3-540-65367-7, available in our library (key text) - R. Motwani, P. Raghavan: Randomized Algorithms
ISBN: 978-0-521-47465-8, available in our library - J. Balcazar, J. Diaz, J. Gabarro: Structural Complexity
ISBN: 978-3-540-58384-4 and 978-3-540-52079-5, available in our library (key text) - R. Niedermeier: Invitation to Fixed Parameter Algorithms
ISBN: 978-0-198-56607-6, available in our library
Prior Iterations
Advanced Algorithmics (SS 13)Computational Biology: Signals, Phylogenetics and Structure Prediction (SS 14)
Biologists collect ever more data which we can only hope to evaluate using computers. In particular, there are huge databases of DNA and RNA resp. fragments thereof, which we model as strings. The sheer amount of data and size of individual records demands especially efficient algorithms if we want to obtain results in a timely fashion.
This course contains computer science methods for advanced, biologically motivated analysis of string-based data, in particular
- identifying signals, patterns in strings of statistical significance,
(log-likelihood test, hidden markov models) - reconstructing phylogenetic trees and
(hierarchical clustering, tree metrics, perfect phylogenetics, quartett puzzling) - predicting folding structure of RNA.
(minimum free energy secondary structures, stochastic context-free grammars)
We always bear in mind to keep complexities low.
It is a 4 ECTS entry-level master course with accompanying tutorials; find details in the official documents.
Registration
In order to participate in the exercise classes, you are required to register in the OLAT system.
Dates
Lectures and exercise sessions will be held throughout the reading period. Individual sessions will take place weekly on
- Lecture: Tuesdays, 10:00 - 11:30 in 48-654
- Exercise Class (biweekly): Fridays, 13:45 - 15:15 in 48-654
first exercise class on 09.05.2014
Exercises
Exercises are organized by Sebastian.
Lecture Notes
Here you can download the content of the electronic blackboard from class as pdf.
Exam
There will be oral exams at the end of the semester, please contact us in time to make an appointment. You need at least 40% of the achievable points in the exercises to be allowed to take the exam.
Suggested Reading
German lecture notes covering all course material are available in print; ask us for it!
Apart from the lecture notes, the following text books cover most of the course's content:
- R. Durbin, S. Eddy, A. Krogh, G. Mitchison: Biological Sequence Analysis
Cambridge University Press, 1998 - D. Gusfield: Algorithms on Strings, Trees, and Sequences
Cambridge University Press, 1997
Previous Iterations
Advanced Algorithmics (SS 17)
Complexity theory tells us that there are problems that seem to be inherently hard to solve. What can we do when faced which such a problem in practice? Over the decades, some useful techniques for tackling hard problems have emerged, for example
- using heuristics to limit search spaces,
- accepting wrong outputs with certain probability and
- accepting suboptimal but still decent solutions.
We follow these approaches and develop theoretical foundations for solving hard problems sufficiently well and fast in practice.
This is an 8 ECTS advanced-level master course; find details in the official documents.
Solid knowledge of elementary algorithms and mathematical maturity are assumed; an introductory course on complexity classes P and NP is helpful, even though we recap the main results in class.
Please register in OLAT for the course to receive email notifications about news and short-term announcements.
Dates
Lectures and exercise sessions will be held throughout the reading period, that is from April 18th to July 22th. We will have two weekly sessions of lectures and one exercise class.
- Lectures: every Monday and Thursday, 15:30 - 17:00 in room 11-201
- Exercise Class: every Friday, 13:45 - 15:15 in room 48-453
Exercises
There will be exercise sheets with problems relating to the current lecture material. We will discuss the exercise problems in weekly exercise sessions. Your tutor will be Marvin Petersen.
Exams
There will be oral exams. The exams will have to be in July, so please arrange for some time to prepare directly after the reading period.
Oral exams can only be taken after successful participation in the course. This includes reaching at least a 1/e fraction of the total points on all exercise sheets.
Lecture Notes
Slides and notes from the lectures will be available here.
Lecture Videos
Recorded lectures are on youtube.
Suggested Reading
The lecture is self-contained and lecture notes will be available.
Further reading (might be subject to change)
- J. Hromkovič: Algorithmics for Hard Problems
ISBN: 978-3-642-07909-2, available in our library - J. Flum, M. Grohe: Parametrized Complexity Theory
ISBN: 978-3-540-29952-3, available as pdf by our library - R. Niedermeier: Invitation to Fixed Parameter Algorithms
ISBN: 978-0-198-56607-6, available in our library - M. Mitzenmachen, E. Upfal: Probability and Computing - Randomized Algorithms and Probabilistic Analysis
ISBN: 978-0-521-83540-4 - S. Arora, B. Barak: Computation Complexity - A Modern Approach
ISBN: 978-0-521-42426-4, available in our library - D. Hochbaum: Approximation Algorithms for NP-Hard Problems
ISBN: 978-0-534-94968-6, available in our library - V. Vazirani: Approximation Algorithms
ISBN: 978-3-540-65367-7, available in our library
Prior Iterations
Algorithm Engineering (SS 14)
For many problems, there are several algorithms to choose from. But how to tell which is the best for your application? Rough complexity estimates can be misleading: If constants hidden by the O-class are large, an O(n) algorithm might be much slower than an O(n log n) algorithm for any reasonable size n.
In this course, we study state of the art techniques for the analysis of algorithms for computing precise asymptotics of costs, including constant factors. We will exercise their use on practical algorithms and data structures.
Moreover, we will take additional characteristics of modern computers into account that greatly influence actual running time:
- Memory hierarchies and
- instruction pipelines.
Finally, we use our new knowledge on the performance of an algorithm to suggest possible optimizations, whose effects we quantify again using analysis techniques. That way, you will learn to engineer the best possible algorithm for solving your real world problem at hand.
This is an 8 ECTS advanced-level master course with accompanying tutorials; find details in the official documents.
Registration
In order to participate in the exercise classes, you are required to register in the OLAT system.
Dates
Lectures and exercise sessions will be held throughout the reading period. Individual sessions will take place weekly on
- Lecture: Mondays and Wednesdays, 10:00 - 11:30 in 48-654
- Exercise Class: Wednesdays, 15:30 - 17:15 in 48-654
first exercise class on 30.04.2014!
Exercises
Exercises are organized by Sebastian.
Sheet 7 can be handed in until Tuesday, 10.06., 12am. as the Monday is a holiday.
Lecture Notes
(Due to technical problems, the first lecture was only partially recorded. Therefore, we additionally provide the notes from the last iteration.)
Suggested Reading
Lecture notes covering all course material are available in print; ask us for it!
Apart from the lecture notes, the following text books cover parts of the course's content (and much more interesting stuff!):
- R. Sedgewick, P. Flajolet: An Introduction to the Analysis of Algorithms
Addison-Wesley Professional, 2nd edition, 2013 - D. Knuth: The Art of Computer Programming: Fundamental Algorithms
Addison-Wesley, 3rd edition, 1997 - D. Knuth: The Art of Computer Programming: Searching and Sorting
Addison-Wesley, 3rd edition, 1998 - P. Flajolet, R. Sedgewick: Analytic Combinatorics
Cambridge University Press, 2009
Previous Iterations
SS 12