Lecture Bioinformatik I

Lecturers

Lecture: Rolf Backofen, Florian Eggenhofer, Dilmurat Yusuf, Omer Alkhnbashi
Exercise: Rick Gelhausen, Stefan Mautner, Teresa Müller

Dates

Lecture: Wed 10-12, via Zoom (instructions for installation can be found here)
Exercise Session: Fri 10-12

Topic and Objectives

This is an introductory lecture to bioinformatics and is mandatory for the group's advanced lectures in bioinformatics.

The topics of the course include sequence alignment and comparison, Markov Chain models, and building phylogenetic trees.

Objectives: The course shall give an overview of basic bioinformatics topics and understanding of some fundamental algorithms. The special focus of the course is on sequence analysis.

Requirements

basic knowledge about molecular biology
basic understanding of algorithms

Although the course requires a basic understanding of molecular biology, an introduction to the necessary foundations is also given in the respective lectures.

Enrolled students agree to ...

When you enroll for this course, you agree to the following general set-up:

Lecture recordings: Due to the current situation, lecture recordings will be provided.
Lecture slides are not sufficient to understand or learn a topic. They are not intended as a reader but as additional material to avoid typos on the blackboard and to present examples etc.
Thus, you are supposed to take your own notes of the discussed lecture material, e.g. by annotating printed versions of the slides.
Solving exercise sheets is optional but highly recommended. Observations from previous semesters show that attending the exercises and solving the sheets deepens your understanding.
We will provide solution sheets that might only show the final result but not each calculation step.
You can use the exercise session for (supervised) solving the sheets or to ask questions. You can solve them independently or as group.
We do not grade nor collect exercises.
Given that you gain 6 ECTS, your workload is estimated with up to 8h per week dedicated to this lecture. Thus, there is plenty of time for reading additional material, rechecking of previous lecture material, implementation of algorithms.
For the latter, we point to respective programming problems on Rosalind. In our experience, it is highly beneficial to solve these implementation tasks for a thorough understanding.

Rosalind implementation tasks

We have setup a class within Rosalind that lists problems related to the course's material with respective due dates, typically the next lecture session.
In order to access the Rosalind class you have to follow the Rosalind class enroll link.
Your solution submission has to be accompanied with the respective source code. Once you have successfully solved a problem, you can post your source code within a respective forum to discuss and review the source submissions of your fellow students.

Forum

We set up a forum in ILIAS to enable exchange with of your fellow students.

Schedule and Material

[04.11.2020] Introduction, Organization, Overview
- Kickoff lecture (via Zoom) at 10am
- Slides:
- Recordings:
- Implementation Tasks:
  - Python introduction (if needed)
- Further Reading:
  - OpenStax, Anatomy and Physiology
[06.11.2020] NO exercise session !
[11.11.2020] Essential Biology Basics
- Slides:
  - Bio Introduction I - DNA and RNA
  - Bio Introduction I - DNA and RNA (handout)
- Recordings:
- Exercise sheet:
  - Sheet 1: Biology Basics DNA/RNA
  - when you have solved the sheet you can compare your solution with Sheet 1: Master Solultion
- Implementation Tasks:
- Further Reading:
  - OpenStax, Anatomy and Physiology
  - Central Dogma by Francis Crick (1958) [[pdf]]
[13.11.2020] NO exercise session !
[18.11.2020] Edit Distance, Alignment Distance, Pairwise Sequence Alignment
- Q and A session for Essential Biology Basics:
- Slides:
- Recordings:
- Exercise sheet:
  - Sheet 2: Edit Distance
  - when you have solved the sheet you can compare your solution with Sheet 2: Master Solultion
- Implementation Tasks:
  - Counting Point Mutations
[20.11.2020] Exercise session: Essential Biology Basics. Write down your questions until 19.11.2020 at 14:00 Questions will be answered in the Zoom session at 10:15 with the following login credidentials: https://uni-freiburg.zoom.us/j/88511636209
Meeting ID: 885 1163 6209
Passcode: z0WGAFT5@
[25.11.2020] Global Pairwise Sequence Alignment
- Q and A session for Edit Distance, Alignment Distance, Pairwise Sequence Alignment:
- Slides:
- Recordings:
- Literature:
  - Needleman+Wunsch (1970)
  - Hirschberg (1974)
- Exercise Sheet:
  - Sheet 3: Sequence Alignment
  - write your questions here until 3.12. 2pm
  - when you have solved the sheet you can compare your solution with sheet 3 solution
- Implementation Tasks:
[27.11.2020] Exercise session Questions will be answered in the Zoom session at 10:15 with the following login credidentials: https://uni-freiburg.zoom.us/j/88511636209
Meeting ID: 885 1163 6209
Passcode: z0WGAFT5@
[02.12.2020] Non-linear Gap Scoring
- Q and A session for Global Pairwise Sequence Alignment:
- Slides:
  - Gap Penalties, Waterman-Smith-Beyer and Gotoh
  - Gap Penalties, Waterman-Smith-Beyer and Gotoh (Handout)
- Recordings:
  - Waterman
  - Gotoh
- Literature:
  - Waterman+Smith+Beyer (1976)
  - Gotoh (1982)
- Implementation Tasks:
  - Global Alignment with Constant Gap Penalty
  - Global Alignment with Scoring Matrix and Affine Gap Penalty
Exercise Sheet:
- Sheet 4: Sequence Alignment
- write your questions here until 10.12. 2pm
- when you have solved the sheet you can compare your solution with sheet 4 solution
[04.12.2020] Exercise
- Questions will be answered in the Zoom session at 10:15 with the following login credidentials: https://uni-freiburg.zoom.us/j/88511636209
  Meeting ID: 885 1163 6209
  Passcode: z0WGAFT5@
[09.12.2020] Local Pairwise Sequence Alignment
- Q and A session for Non-linear Gap Scoring:
- Slides:
- Recordings:
  - Smith-Waterman
  - Normalized Local Alignment
- Literature:
- Implementation Tasks:
- Exercise Sheet:
  - Sheet 5: Sequence Alignment
  - write your questions here until 17.12. 2pm
  - when you have solved the sheet you can compare your solution with sheet 5 solution
[11.12.2020] Exercise
- Questions will be answered in the Zoom session at 10:15 with the following login credidentials: https://uni-freiburg.zoom.us/j/88511636209
  Meeting ID: 885 1163 6209
  Passcode: z0WGAFT5@
[16.12.2020] Bio Introduction Proteins
- Q and A session for Local Pairwise Sequence Alignment:
- Slides:
  - Proteins and Translation
  - Proteins and Translation (handout)
- Recordings:
  - Proteins and Translation
- Implementation Tasks:
- Exercise Sheet:
  - Sheet 6: Biology Basics Protein
  - write your questions here until 14.01. 2pm
  - when you have solved the sheet you can compare your solution with sheet 6 solution
- Literature:
  - Central Dogma by Francis Crick (1958) [[pdf]]
[18.12.2020] Exercise
[13.01.2021] Markov chains
- Q and A session for Bio Introduction Proteins:
- Slides:
- Recordings:
  - recording.mp4
- Implementation Tasks:
  check and understand this Markov-chain-based text generator
- Sheet 7
- write your questions here until 21.1. 2pm
- when you have solved the sheet you can compare your solution with sheet 7 solution
[15.01.2021] Exercise
[20.01.2021] Substitution Scoring
- Q and A session for Markov chains:
- Slides:
- Recordings:
  - Substition Scoring
- Literature:
- Implementation Tasks:
  recompute the PAM250 matrix for amino acids using the following information from (Dayhoff et al., 1978)
  - amino acid substitution counts (assumed to by symmetric, thus only lower triangular matrix given)
  - amino acid counts within underlying alignment
  - final PAM250 scores are computed by 10*log10(odds)
  - see referenced publication for intermediate tables (notation: f = q, M = R1)
- Sheet 8
- write your questions here until 28.1. 2pm
- when you have solved the sheet you can compare your solution with sheet 8 solution
[22.01.2021] Exercise
- Questions will be answered in the Zoom session at 10:15 with the following login credidentials:
  No Questions were asked.

[27.01.2021] Multiple Sequence Alignment and Summary
- Q and A session for Markov chains:
- Slides:
  - Multiple Sequence Alignment
  - Multiple Sequence Alignment (handout)
- Recordings:
  - recording.mp4
- Literature:
- Implementation Tasks:
[29.01.2021] Exercise
- Sheet 9
- seq.fa
- when you have solved the sheet you can compare your solution with sheet 9 solution
- Questions will be answered in the Zoom session at 10:30 with the following login credidentials:
  https://uni-freiburg.zoom.us/j/88511636209
  Meeting ID: 885 1163 6209
  Passcode: z0WGAFT5@
[03.02.2021] Phylogeny Reconstruction + UPGMA
- Q and A session for Multiple Sequence Alignments:
- Slides:
- Recordings:
  - Phylogeny
  - UPGMA
- Literature:
  - Feng+Doolittle (1987)
  - Feng+Doolittle (1996)
  - Cavalli-Sforza/Edwards (1967)
  - Sokal+Michener (1958)
  - Gusfield (Chapter 17) for phylogenetic trees with intro to ultrametric and additive metric (trees)
  - Durbin (pages 165-169) for the UPGMA algorithm (popular definition)
  - Clote & Backofen (pages 144-152) for alternate view on weighted vs. unweighted
- Implementation Tasks:
[05.02.2021] Exercise
- Sheet 10
- when you have solved the sheet you can compare your solution with sheet 10 solution
[10.02.2021] Maximum Likelihood Trees
- Q and A session for Phylogeny Reconstruction + UPGMA:
- Slides:
- Recordings:
  - Bioinformatics_Lecture12_maximum_likelihood.mp4
- Literature:
  - Felsenstein (1981)
  - Clote & Backofen (pages 157-166) max-likelihood
- Exercise:
  - Sheet 11
  - when you have solved the sheet you can compare your solution with sheet 11 solution
[12.02.2020] Quartet tree puzzling
- slides:
- Recordings:
  - Bioinformatics_Lecture13_quadtree-sampling.mp4
- Literature:
  - Strimmer+vonHaeseler (1996)
  - Clote & Backofen (pages 166-171) quartet trees
- implementation tasks:
  - Quartets
  - Counting Quartets
Exercise:
- Sheet 12
- when you have solved the sheet you can compare your solution with sheet 12 solution
[17.02.2020] - Q and A session for Maximum Likelihood Trees + Quartet tree puzzling:
[24.02.2020 - 10:15am] optional question session
- Join us in Zoom at 10:15 am with the following credidentials:
  https://uni-freiburg.zoom.us/j/89257303943
  Meeting ID: 892 5730 3943
  Passcode: ^rd62b8Z8
[16.03.2020] written examinations

Algorithm implementations

We observe that the deepest understanding of the course content is gained by implementing the introduced algorithms. In order to cross-check the results of personal implementations and to enable a fast example generation and study, we offer Javascript-based implementations and visualizations for most of the algorithms via the Freiburg RNA tools - Teaching webserver.

Books

Computational Molecular Biology: An Introduction.
Peter Clote and Rolf Backofen.
Jon Wiley & Sons, Chichester, August 2000.
Biological sequence analysis - Probabilistic models of proteins and nucleic acids.
Richard Durbin, Sean Eddy, Anders Krogh and Graeme Mitchison.
Cambridge University Press, Cambridge, 1998.
Algorithms on Strings, Trees, and Sequences.
Dan Gusfield.
Cambridge University Press, Cambridge, 1997.
Bioinformatik Interaktiv.
Grundlagen, Algorithmen, Anwendungen.
Rainer Merkl und Stephan Waack.
WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim 2009.