Algorithms for Genome Rearrangement (2V + 2Ü)

392189/92 Stoye Summer 2016 Fr 8:45 - 10:15 (Ü), Fr 10:15 - 11:45 (V) in U10-146 ekvv/ekvv

Kurzbeschreibung

Viele Fragestellungen in der Molekularbiologie, der Phylogenetik und der Biomedizin lassen sich durch den Vergleich von zwei oder mehr Genomen behandeln. Da ein globales Alignment von Genomen oft nicht möglich oder extrem aufwändig zu berechnen ist, wurden Vergleichsmethoden entwickelt, die auf der höheren Ebene der Reihenfolge der Gene oder anderer eindeutiger Genomabschnitte ansetzen.

In dieser Vorlesung werden verschiedene Modelle auf dieser höheren Ebene und darauf basierende Vergleichsmethoden behandelt. Wir beginnen mit einfachen Distanzmaßen wie der Breakpoint-Distanz, gefolgt von komplexeren Modellen wie der SCJ-, der DCJ-, der Inversions- und der allgemeinen Rearrangement-Distanz. Auch werden wir Methoden zum Auffinden von evolutionär konservierten, funktionellen Genclustern behandeln. Schließlich werden die Schwierigkeiten thematisiert, die auftreten, wenn sich vorab keine eindeutigen Genomabschnitte finden lassen, z.B. weil die Genome einzelne duplizierte Abschnitte enthalten.

Die behandelten Algorithmen sind meist kombinatorischer Natur, ähnlich wie in der Sequenzanalyse.

Teilnahmevoraussetzungen, notwendige Vorkenntnisse

Notwendig: Algorithmen und Datenstrukturen (oder Vergleichbares).

Empfohlen: Sequenzanalyse und Grundlagen der Genomforschung.

Literatur

  • Siehe in der Tabelle unten, bei den einzelnen Themen der Vorlesung.

Organisatorisches

  • Die Modulbeschreibung enthält einige Rahmenbedingungen der Veranstaltung.
  • Erfolgreiches Lösen der Übungsaufgaben (Bestehensgrenze 50% der Punkte) und aktive Teilnahme in den Tutorien (mindestens zweimal Vorrechnen) ist Voraussetzung für die Teilnahme an der Abschlussklausur oder der abschließenden mündlichen Prüfung.
  • Die Übungszettel werden in der Regel wöchentlich in der Vorlesung ausgegeben. Die Lösungen müssen bis zum kommenden Donnerstag (10 Uhr) dem Tutor in pdf-Format per E-Mail zugeschickt werden und werden dann am nächsten Tag (Freitag) besprochen.
  • Bitte den Namen deutlich auf der Abgabe vermerken. Zettel, die nicht zugeordnet werden können, werden auch nicht bewertet.

Prüfungstermine

Mündliche Prüfungen am 22.07.2016 und 29.07.2016. Nachprüfungstermine nach Vereinbarung.

Schedule

Date Topic Exercises Other
15.04.2016 Introduction
22.04.2016 (no class)
29.04.2016 (no class)
06.05.2016 (no class)
13.05.2016 Breakpoint distance Sheet 1 Based on parts of: Tannier, Zheng, Sankoff: Multichromosomal median and halving problems under different genomic distances. BMC Bioinformatics 10: 120, 2009
20.05.2016 DCJ distance Sheet 2 Based on: Bergeron, Mixtacki, Stoye: A Unifying View of Genome Rearrangements. Proceedings of WABI 2006: Springer Verlag, LNBI 4175, 163-173, 2006
27.05.2016 DCJ with indels Sheet 3 Based on: Braga, Willing, Stoye: Double Cut and Join with Insertions and Deletions. Journal of Computational Biology 18(9): 1167–1184, 2011
03.06.2016 Genome halving Sheet 4 Based on parts of: Tannier, Zheng, Sankoff: Multichromosomal median and halving problems under different genomic distances. BMC Bioinformatics 10: 120, 2009
10.06.2016 Reversal distance via DCJ distance Sheet 5 Based on: Bergeron, Mixtacki, Stoye: The inversion distance problem. In: Mathematics of Evolution and Phylogeny, Gascuel (ed.), 262-290, 2005
17.06.2016 Genomic distance via DCJ distance Sheet 6 Based on: Bergeron, Mixtacki, Stoye: A New Linear Time Algorithm to Compute the Genomic Distance Via the Double Cut and Join Distance. Theoretical Computer Science 410(51): 5300-5316, 2009 and Erdős, Soukup, Stoye: Balanced Vertices in Trees and a Simpler Algorithm to Compute the Genomic Distance. Applied Mathematics Letters 24(1): 82-86, 2011
24.06.2016 (no class)
01.07.2016 FF-DCJ (guest lecture by Kevin Lamkiewicz) Sheet 7 Based on: Martinez, Feijão, Braga, Stoye: On the family-free DCJ distance and similarity. Algorithms Mol. Biol. 10:13, 2015
08.07.2016 SCJ Sheet 8 Based on: Feijão, Meidanis: SCJ: A Breakpoint-Like Distance that Simplifies Several Rearrangement Problems. IEEE/ACM Trans. Comput. Biol. Bioinf. 8(5): 1318-1329, 2011
15.07.2016 Ancestral Genome Reconstruction Based on: Feijão: Reconstruction of Ancestral Gene Orders using Intermediate Genomes. BMC Bioinformatics 16(Suppl.4): S3, 2015
22.07.2016 Oral exams (Master students)
29.07.2016 Oral exams (Bachelor and PhD students)

Back to Teaching