Bioinformatics represents an application domain of increasing interest and importance for computer science. This discipline arose from the increasing need to develop appropriate computational methods for different problems of molecular biology and genetics, including the analysis of biological sequences (DNA, RNA, proteins). More specifically, recent next-generation sequencing technologies allow to generate massive amounts of biological sequence data that pose complex problems and require specific algorithms and computational analyses for their efficient and effective processing.

The goal of the course is to introduce students to some of the most important algorithms (and their underlying concepts) used in computational biology/bioinformatics, especially regarding those used for aligning biological sequences and identifying their locations in the reference genome. Also the assembly of a genome from short sequences, the modeling of functional biological sequences and the identification of mutations in a sequenced genome will be discussed. Each topic is treated both theoretically and practically. By discussing also alternative approaches for several of the algorithms, including their advantages and diadvantages, the students can learn how effective and efficient algorithms can be designed and when approximate solutions are preferable.

Detailed course program:

1. (Very brief) Introduction to the biological background

• Cells, biological molecules (DNA, RNA, proteins) and cellular processes

• DNA sequencing techniques

2. Sequence alignment

• Defining and measuring distances and similarities between sequences

• Pairwise alignment of sequences based on similarity measures

• Dynamic programming for constructing global and local sequence alignments (Needleman-Wunsch and Smith-Waterman algorithms)

• Longest common substring problem

• Multiple sequence alignment (more than two sequences)

  • Approximate versus optimal solution

  • Center star algorithm

  • Tree-based, progressive multiple sequence alignment

  • Weighted dynamic programming based on alignment/sequence profiles

  • Local multiple sequence alignment and motif scoring

• Computational complexity of sequence alignment algorithms

3. Read alignment of next-generation sequencing reads

• Suffix trie, suffix tree and suffix array

• Burrows-Wheeler transform

• FM index for searching substrings

• Exact matching and inexact matching of sequencing reads

• Computational complexity of the different approaches

4. De-novo genome assembly from next-generation sequencing reads

• Modeling sequence data and computing expected results

• Graph-based genome assembly (de Bruijn graphs, Eulerian path problem and Hierholzer’s algorithm)

5. Notions of variant calling

• Single nucleotide variants/mutations

• Copy number variants (deletions and duplications)

• Germline variants in hereditary disorders versus somatic variants in cancer

6. Introduction to Hidden Markov Models for sequence modeling

• Markov chains and Hidden Markov Model (HMMs)

• Probability of a sequence being generated by an HMM

• Viterbi decoding and posterior decoding

• HMM training: learning model parameters

• SDG2 - ZERO HUNGER
• SDG3 - GOOD HEALTH AND WELLBEING

The discussed algorithms are mainly used in basic biomedical research (SDG3 targets 3.3: fighting communicable diseases; SDG3 target 3.4: reducing mortality from non-communicable diseases) but can also be used for agricultural research, e.g., for the identification of the genetic basis of heat resistance of plants (SDG2 target 2.4: strengthening the capacity for adaptation to climate change, extreme weather, drought, flooding and other disasters).

Basic knowledge of algorithms and algorithmic complexity

The assessment will be based on a written exam to be taken in the exam sessions defined by the school and covering all aspects in the syllabus. The exam will assign up to 60 points (+ 6 possible bonus points). 30 cum laude will be assigned when the total score exceeds 64 points.

The following table provides a detailed overview of the elements that will be considered in the written exam.