Differences

This shows you the differences between two versions of the page.

@@ Line 1: / Line 1: @@
+====== Algorithms in Comparative Genomics (2V + 2Ü) ======
+| [[https://ekvv.uni-bielefeld.de/kvv_publ/publ/vd?id=655652999|392192]] | Dias Vieira Braga, Wittler | Summer 2026 | Fr 08:30 - 10:00 (Ü) in U10-146 |
+| [[https://ekvv.uni-bielefeld.de/kvv_publ/publ/vd?id=655651721|392189]] | Dias Vieira Braga, Wittler  | Summer 2026 | Fr 10:15 - 11:45 (V) in U10-146 |
+===== 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.
+Algorithms discussed in this course are mostly combinatorial by nature, similar to the sequence analysis course.
+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 =====
+Preliminary version of the lecture notes:
+{{teaching:2021winter:cg:cg_notes-chapter1.pdf | Chapter 1}}
+{{teaching:2021winter:cg:cg_notes-chapter2.pdf | Chapter 2}}
+Other references are listed below, together with the schedule.
+===== Topics =====
+  - Distance and Sorting
+    * Breakpoint model
+    * Single-Cut-or-Join (SCJ) model
+    * Double-Cut-and-Join (DCJ) model
+    * DCJ-indel model
+    * Inversion model
+  - Ancestral Reconstruction
+    * Median and halving
+    * SCJ Small Parsimony
+  - Conserved Gene Clusters
+    * Generators for common intervals
+    * Strong common intervals and PQ-trees
+    * Common intervals of strings
+===== Inversion Visualization Software =====
+Prof. {{https://www.renyi.hu/~miklosi|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 {{teaching:2020winter:cg:inversion.zip|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 ^ Teacher ^ Topic  ^ Literature ^ Exercises ^
+| 17.04. | Marilia | Introduction, Genes, Genomes, Breakpoint (BP) distance | [[https://doi.org/10.1186/1471-2105-10-120|Tannier et al. 2009]] | {{teaching:2026summer:cg:sheet01.pdf | Sheet 01}} |
+| 24.04. | Marilia | BP and SCJ distance, median and halving | [[https://doi.org/10.1186/1471-2105-10-120|Tannier et al. 2009]],\\ [[https://ieeexplore.ieee.org/document/5719602|Feijão & Meidanis 2011]] |{{teaching:2026summer:cg:sheet02.pdf | Sheet 02}} |
+| 01.05. | -- (national holiday) ||||
+| 08.05. | Roland | Small Parsimony under SCJ | [[https://ieeexplore.ieee.org/document/5719602|Feijão & Meidanis 2011]],\\ {{teaching:2023summer:cg:spp-algo.pdf | SPP-algorithm.pdf}}   | {{teaching:2026summer:cg:sheet03.pdf | Sheet 03}}  |
+| 15.05. | Roland | Small Parsimony under SCJ | [[https://doi.org/10.1186/1471-2105-13-S19-S11|Manuch et al. 2012]],\\ [[https://doi.org/10.1109/TCBB.2018.2816034| Luhmann et al. 2014/2018]],\\ {{teaching:2023summer:cg:max-row_c1p.pdf|MAX-ROW_C1P.pdf}}| {{teaching:2026summer:cg:sheet04.pdf | Sheet 04}} |
+| 22.05. | Marilia | Double-Cut-and-Join (DCJ) model | [[https://doi.org/10.1007/11851561_16|Bergeron et al. 2006]] | {{teaching:2026summer:cg:sheet05.pdf | Sheet 05}} |
+| 29.05. | Marilia | DCJ halving, double distance and median | [[https://doi.org/10.1007/978-3-540-69733-6_28|Mixtacki 2008]],\\ [[https://doi.org/10.1186/1471-2105-10-120|Tannier et al. 2009]] |  {{teaching:2026summer:cg:sheet06.pdf | Sheet 06}} |
+| 05.06. | Marilia | Inversion distance | [[https://doi.org/10.1145/300515.300516|Hannenhalli and Pevzner 1999]],\\ [[https://link.springer.com/chapter/10.1007/978-3-540-27801-6_29|Bergeron et al. 2004]] | {{teaching:2026summer:cg:sheet07.pdf | Sheet 07}} |
+| 12.06. | Marilia | Inversion distance/DCJ-indel distance | [[https://link.springer.com/chapter/10.1007/978-3-540-27801-6_29|Bergeron et al. 2004]],\\ [[https://doi.org/10.1089/cmb.2011.0118|Braga et al. 2011]] | {{teaching:2026summer:cg:sheet08.pdf | Sheet 08}} |
+| 19.06. | Marilia | DCJ-indel distance | [[https://doi.org/10.1089/cmb.2011.0118|Braga et al. 2011]] | {{teaching:2026summer:cg:sheet09.pdf | Sheet 09}} |
+| 26.06. | Roland | Consistency of gene clusters | {{teaching:2023summer:cg:consistent_gene_clusters_slides.pdf | Slides}},\\ [[https://doi.org/10.1109/TCBB.2008.135|Stoye et al. 2009]],\\ [[https://doi.org/10.1089/cmb.2011.0083|Wittler et al. 2011]],\\ {{https://n-coder.github.io/pqtree.js|PQ- & PC-Trees applet, D. Peters and S. D. Fink}}| {{teaching:2026summer:cg:sheet10.pdf | Sheet 10}}  |
+| 03.07. | Roland | Generators for common intervals | [[https://doi.org/10.1137/060651331|Bergeron et al. 2008]], Sections 1 and 2 | {{teaching:2026summer:cg:sheet11.pdf | Sheet 11}}  |
+| 10.07. | Roland | Generators, strong common intervals and PQ-trees | see above, Sections 3, 4, 5.1, and 5.3 | {{teaching:2026summer:cg:sheet12.pdf | Sheet 12}} |
+| 07.07. | Roland | Common intervals of strings | [[https://doi.org/10.1016/j.jda.2006.03.021|Didier at al., 2006]],\\ {{teaching:2023summer:cg:didier.pdf | Dany Doerr's notes}} | {{teaching:2026summer:cg:sheet13.pdf | Sheet 13}} |
+| 17.07. | Roland | Common intervals of indeterminate strings | [[https://pub.uni-bielefeld.de/download/2902049/2902050/PhDThesis.pdf|Doerr, PhD thesis 2016]] | |

Genome Informatics

Differences