Algorithms in Comparative Genomics (2V + 2Ü)

392189 Dias Vieira Braga Winter 2020/21 Th 10:15 - 11:45 (V) online via Zoom
392192 Bohnenkämper Winter 2020/21 Fr 08:30 - 10:00 (Ü) online via Zoom

The details of both Zoom meetings were already announced via mail list.

Content

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 breakpoint distance, followed by other simple measures such as SC/J and DCJ. The reversal distance will be discussed, and a general genome rearrangement distance. We will also study methods for the reconstruction of ancestral genomes and gene clusters.

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

This lecture can ideally be combined with the seminar "Computational Pangenomics (2S)".

This course is taught in English.

Conditions for participation, prior knowledge

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

Literature

to be announced later

Topics

  1. Distance and Sorting
    • Breakpoint Distance
    • Double-Cut-and-Join (DCJ) distance
    • DCJ-indel distance
    • Reversal Distance
    • Single-Cut-or-Join (SCJ) distance
  2. Computing NP-hard distances via ILP
    • Balanced genomes
    • Natural genomes
    • Family-free genomes
  3. Ancestral Reconstruction
    • SCJ Median
    • Small Parsimony
  4. Common Intervals and Gene Clusters

Inversion Visualization Software

Prof. Istvan Miklos, from Alfréd Rényi Institute in Budapest, kindly shared his visualization software for the Breakpoint Diagram. 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, representing genome A (genome B is assumed to be the identity permutation), the numbers separated with a <tab>. There is an example in the provided archive.

Select the adjacency 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.

Schedule

Date Topic Slides (S) S + notes Literature Exercises
29.10. Introduction, Genomes, Breakpoint distance S01 SN01 Tannier et al. 2009 Ex01
05.11. Breakpoint and Single-Cut-or-Join (SCJ) distances S02 SN02 Feijão & Meidanis 2011 Ex02
12.11. Breakpoint and SCJ median and halving S03 SN03 Ex03
19.11. Breakpoint median/ Double-Cut-and-Join (DCJ) halving S04 SN04 Bryant 1998, Mixtacki 2008 Ex04
26.11. DCJ distance and relational graph S05 SN05 Bergeron et al. 2006,
Kováč et al. 2011
Ex05
03.12. Inversion distance and relational diagram S06 SN06 Sorting by Reversals,
Hannenhalli and Pevzner 1999,
Bergeron et al. 2004
Ex06
10.12. Inversion distance / DCJ-indel distance S07 SN07 Braga et al. 2011 Ex07
17.12. DCJ-indel distance / Restricted DCJ-indel distance S08 SN08 Braga and Stoye, 2015,
Braga et al. 2011b
Ex08 - Christmas
07.01. Capped relational graph S09 SN09 Bohnenkämper et al. 2020 Ex09
14.01. DCJ with duplicated genes (double-distance / balanced genomes) S10 SN10 Tannier et al. 2009 Ex10
21.01. ILP / DCJ distance of balanced genomes S11 SN11 Shao et al. 2015 Ex11
28.01. DCJ-indel distance of natural genomes
(guest lecture by L. Bohnenkämper)
S12 Bohnenkämper et al. 2020 Ex12
04.02. DCJ distance and DCJ-indel distance
of family-free genomes
S13 SN13 Rubert et al. 2020 Ex13
11.02. Small parsimony under SCJ / review S14 SN14 Feijão & Meidanis 2011