Algorithmic Bioinformatics (Prof. Canzar)

Numerous problems in bioinformatics and other domains can be formulated as optimization tasks; we seek the shortest, cheapest, or longest among many possible solutions that satisfy certain constraints. For some problems, there is no known algorithm that can find the optimal solution efficiently, or the problem can be proved NP-hard. Even in such cases, we are interested in a solution that is as good as possible, to learn something about the underlying (biological) problem.
This course introduces fundamental techniques for modeling and solving combinatorial optimization problems. The first half of the course emphasizes exact methods, especially those based on (integer) linear programming. The second half explores heuristic and metaheuristic approaches, which provide practical solutions when exact methods become infeasible.

A meaningful interpretation of biomedical data requires a basic understanding of the biological units and processes from which the data were generated as well as knowledge of the technologies that produced the data. The aim of this module is to equip students with this understanding. It will cover fundamental concepts in molecular and cellular biology, genetics, and strengths and limitations of current DNA sequencing technologies. Furthermore, it will highlight how biological questions can be translated into computational problems, from sequence alignment and genome assembly to gene regulation and disease variant detection.

Computational genomics increasingly depends on complex data analysis pipelines, making reproducibility essential for reliable scientific research. In this seminar, students learn the principles of reproducible genomic data science through a hands-on project: working in teams, they reproduce selected analyses from published genomics studies, identify reproducibility challenges, and develop reproducible workflows using Snakemake while applying best practices for computational research.

In the lecture and lab Applied Algorithms, students learn how to apply algorithmic methods to real-world problems. A broad range of algorithmic techniques is covered, including:

• Brute-force and branch-and-bound methods for identifying hidden motifs
• Greedy strategies
• Dynamic programming
• Graph-based algorithms
• Data structures for efficient pattern matching
• Clustering methods
• Hidden Markov models

The course combines theoretical concepts with practical examples and case studies, mostly from biology.