# 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 | — | — |

^{*}Login required; get credentials from Raphael.

^{+}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