====== Algorithms in Comparative Genomics (2V + 2Ü) ====== | [[https://ekvv.uni-bielefeld.de/kvv_publ/publ/vd?id=391451093|392192]] | Dias Vieira Braga, Wittler | Summer 2023 | Fr 08:30 - 10:00 (Ü) in U10-146 | | [[https://ekvv.uni-bielefeld.de/kvv_publ/publ/vd?id=391447593|392189]] | Dias Vieira Braga, Wittler | Summer 2023 | 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 . 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. ===== PQ-Tree applet ===== Download the {{:teaching:2012winter:892pqtree.jar | jar-file }} and run java -jar -g n where n is the number of leaves for the initial PQ-Tree. Select the elements which shall appear consecutively by mouse click and Ctrl or shift in the list on the left side of the window. Then click Reduce to get the resulting tree. Use Reset to get the initial tree again. //[Reference: J. Harris. A Graphical Java Implementation of PQ-Trees. www.jharris.ca/portfolio/academic.htm (last visited 09/20/2006), April 2002. Carleton University. Debugged by Roland Wittler, Bielefeld University.]// ===== Schedule ===== ^ Date ^ Teacher ^ Topic ^ Literature ^ Exercises ^ | 07.04. | No class | Holiday | -- | -- | | 14.04. | Jens | Introduction, Genes, Genomes, Breakpoint (BP) distance | [[https://doi.org/10.1186/1471-2105-10-120|Tannier et al. 2009]] | {{teaching:2023summer:cg:sheet01.pdf | Sheet 01}} | | 21.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:2023summer:cg:sheet02.pdf | Sheet 02}} | | 28.04. | 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:2023summer:cg:sheet03.pdf | Sheet 03}} | | 05.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:2023summer:cg:sheet04.pdf | Sheet 04}} | | 12.05. | Marilia | Double-Cut-and-Join (DCJ) model | [[https://doi.org/10.1007/11851561_16|Bergeron et al. 2006]] | {{teaching:2023summer:cg:sheet05.pdf | Sheet 05}} | | 19.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:2023summer:cg:sheet06.pdf | Sheet 06}} | | 26.05. | 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:2023summer:cg:sheet07.pdf | Sheet 07}} | | 02.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:2023summer:cg:sheet08.pdf | Sheet 08}} | | 09.06. | Marilia | DCJ-indel distance | [[https://doi.org/10.1089/cmb.2011.0118|Braga et al. 2011]] | {{teaching:2023summer:cg:sheet09.pdf | Sheet 09}} | | 16.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]] | {{teaching:2023summer:cg:sheet10.pdf | Sheet 10}} | | 23.06. | Roland | Generators for common intervals | [[https://doi.org/10.1137/060651331|Bergeron et al. 2008]], Sections 1 and 2 | {{teaching:2023summer:cg:sheet11.pdf | Sheet 11}} | | 30.06. | Roland | Generators, strong common intervals and PQ-trees | see above, Sections 3, 4, 5.1, and 5.3 | {{teaching:2023summer: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}} | | | 07.07. 13:00 | Roland | Common intervals of indeterminate strings | [[https://pub.uni-bielefeld.de/download/2902049/2902050/PhDThesis.pdf|Doerr, PhD thesis 2016]] | {{teaching:2023summer:cg:sheet13.pdf | Sheet 13}} | | 14.07. | (see above) | | | |