====== 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 | [[http://ekvv.uni-bielefeld.de/kvv_publ/publ/vd?id=70302741|ekvv]]/[[http://ekvv.uni-bielefeld.de/kvv_publ/publ/vd?id=70311969|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 [[https://ekvv.uni-bielefeld.de/sinfo/publ/modul/61394968|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 | {{:teaching:2016summer:gr:exercises01BpDistance.pdf|Sheet 1}} | Based on parts of: [[http://dx.doi.org/10.1186/1471-2105-10-120|Tannier, Zheng, Sankoff: Multichromosomal median and halving problems under different genomic distances. BMC Bioinformatics 10: 120, 2009]]  |
| 20.05.2016 | DCJ distance | {{:teaching:2016summer:gr:exercises02Dcj.pdf|Sheet 2}} | Based on: [[http://dx.doi.org/10.1007/11851561_16|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 | {{:teaching:2016summer:gr:exercises03DcjIndel.pdf|Sheet 3}} | Based on: [[http://dx.doi.org/10.1089/cmb.2011.0118|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 | {{:teaching:2016summer:gr:exercises04GenomeHalving.pdf|Sheet 4}} | Based on parts of: [[http://dx.doi.org/10.1186/1471-2105-10-120|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 | {{:teaching:2016summer:gr:exercises05Reversals.pdf|Sheet 5}} | Based on: Bergeron, Mixtacki, Stoye: The inversion distance problem. In: [[https://global.oup.com/academic/product/mathematics-of-evolution-and-phylogeny-9780198566106|Mathematics of Evolution and Phylogeny, Gascuel (ed.)]], 262-290, 2005 |
| 17.06.2016 | Genomic distance via DCJ distance | {{:teaching:2016summer:gr:exercises06Hp.pdf|Sheet 6}} | Based on: [[http://dx.doi.org/10.1016/j.tcs.2009.09.008| 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 [[http://dx.doi.org/10.1016/j.aml.2010.08.021|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) | {{:teaching:2016summer:gr:exercises07FFDCJ.pdf|Sheet 7}} | Based on: [[http://dx.doi.org/10.1186/s13015-015-0041-9 | Martinez, Feijão, Braga, Stoye: On the family-free DCJ distance and similarity. Algorithms Mol. Biol. 10:13, 2015]] |
| 08.07.2016 | SCJ | {{:teaching:2016summer:gr:exercises08Scj.pdf|Sheet 8}} | Based on: [[http://dx.doi.org/10.1109/TCBB.2011.34 | 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: [[http://dx.doi.org/10.1186/1471-2105-16-S14-S3 | 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|Teaching]]