Algorithms for Genome Rearrangement (2V + 2Ü)

392189/92 Dörr Summer 2017 Fr 09:00 - 10:15 (Ü), Fr 10:15 - 11:45 (V) in U10-146 ekvv/ekvv


Many questions in molecular biology, phylogenetics, and biomedicine can be approached through comparison of two or more genomes. However, a global alignment of multiple large genomes is often infeasible or comes at great expense. It is more efficient to compare genomes on a higher level of abstraction, as given by the succession of single-copy genes or other kinds of unique genomic markers on the chromosomal sequences.

In this course, various models of higher level genome comparison are discussed. We start with the classical reversal distances which are measures to study chromosomal sequences only permuted by inversions. We then continue by discussing distances such as SC/J or DCJ, and a general rearrangement distance. It then follows a discussion of methods that solve the problem of comparing sequences with unequal gene/marker content. We will also study methods for the reconstruction of ancestral genomes.

Algorithms discussed in this course are mostly combinatorial by nature, similar to the sequence analysis course.

This course is taught in German or English if needed.

Conditions for participation, prior knowledge

Required: Algorithms and Data Structures (or comparable)
Recommended: Sequence Analysis and Foundations of Genome Research

Inversion Visualization Software

Prof. Istvan Miklos, from the Bioinformatics Group in Alfréd Rényi Institute in Budapest, kindly shared his visualization software for the Breakpoint Graph. It is written in Java, and you can download it here.

Usage: java InversionVisualisation file_name

For example: java InversionVisualisation example.txt

The input must be a signed permutation in one line, the numbers separated with a <tab>. There is an example in the provided archive.

Select the reality edges on which the reversal should act, and press the button Mutate. You can go forward and backward in the list of generated genomes, and you can delete any of them, too.


Date Topic(s) Notes Exercises Remarks
21.04.2017 Genome rearrangements, unsigned reversal distance 01 01 3, 4 lit.: 1, 2, 3
28.04.2017 Unsigned (part II) and signed reversal distance 02 01 1, 2, 02 1 lit.: 4, 5
05.05.2017 Signed reversal distance (part II) 03 02 2, 03 lit.: 4, 5 permutations: π^2, π^3, fortress, Ex. 02.2
12.05.2017 Sorting by (signed) reversals 04 04 for 3, only draw OV(π) lit.: 4,6
19.05.2017 Algebraic Theory for Genome Rearrangements 05 05 lit: 7, 8, 9
26.05.2017 Double-Cut-and-Join (DCJ) 06 06 lit: 10
02.06.2017 Guest lecture by Eyla Willing: DCJ with insertions and deletions 07 lit: 11
09.06.2017 Breakpoint distance with duplicates 08 08 lit: 12, 13
16.06.2017 Family-free genome comparison 09 09 lit: 14, 15
23.06.2017 Genome median problem 10 10 lit: 16, 17
30.06.2017 Genome halving 11 11 3 lit: 18
07.07.2017 Ancestral genome reconstruction I 12 11 1, 2 lit: 19
14.07.2017 Ancestral genome reconstruction II 13 12 lit: 20, 21, 22, 23
21.07.2017 Exam prep Q&A
28.07.2017 Oral exam

Back to Teaching