====== Algorithms in Comparative Genomics (2V + 2Ü) ====== | [[https://ekvv.uni-bielefeld.de/kvv_publ/publ/vd?id=294211814|392192]] | Bohnenkämper | Winter 2021/22 | Th 08:30 - 10:00 (Ü) in U10-146 | | [[https://ekvv.uni-bielefeld.de/kvv_publ/publ/vd?id=288193642| 392189]] | Dias Vieira Braga | Winter 2021/22 | Th 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 - Computing NP-hard distances via ILP * Balanced genomes * Natural genomes * Family-free genomes - Inferring gene families via family-free rearrangements - Ancestral Reconstruction * Median and halving * SCJ Small Parsimony ===== 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. ===== Schedule ===== ^ Date ^ Topic ^ Slides ^ Literature ^ Exercises ^ | 21.10. | Introduction, Genomes, Breakpoint distance | {{teaching:2021winter:cg:lecture01.pdf | Slides 01}} | [[https://doi.org/10.1186/1471-2105-10-120|Tannier et al. 2009]] | {{teaching:2021winter:cg:sheet01.pdf | Sheet 01}} | | 28.10. | Single-Cut-or-Join (SCJ) distance, halving and median | {{teaching:2021winter:cg:lecture02.pdf | Slides 02}} | [[https://doi.org/10.1109/TCBB.2011.34|Feijão & Meidanis 2011]] | {{teaching:2021winter:cg:sheet02.pdf | Sheet 02}} | | 04.11. | Breakpoint median / Double-Cut-and-Join (DCJ) model | {{teaching:2021winter:cg:lecture03.pdf | Slides 03}} | {{teaching:2020winter:cg:b1998.pdf | Bryant 1998}},\\ [[https://doi.org/10.1007/11851561_16|Bergeron et al. 2006]] | {{teaching:2021winter:cg:sheet03.pdf | Sheet 03}} | | 11.11. | DCJ distance and sorting / Restricted DCJ sorting | {{teaching:2021winter:cg:lecture04.pdf | Slides 04}} | [[https://doi.org/10.1007/11851561_16|Bergeron et al. 2006]],\\ [[https://doi.org/10.1089/cmb.2011.0116|Kováč et al. 2011]] | {{teaching:2021winter:cg:sheet04.pdf | Sheet 04}} | | 18.11. | DCJ halving, double distance and median | {{teaching:2021winter:cg:lecture05.pdf | Slides 05}} | [[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:2021winter:cg:sheet05.pdf | Sheet 05}} | | 25.11. | Inversion distance | {{teaching:2021winter:cg:lecture06.pdf | Slides 06}} | {{teaching:2020winter:cg:sorting-by-reversals.pdf | Sorting by Reversals}},\\ [[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:2021winter:cg:sheet06.pdf | Sheet 06}} | | 02.12. | - NO LECTURE - | -- | -- | -- | | 09.12. | DCJ-indel distance | {{teaching:2021winter:cg:lecture07.pdf | Slides 07}} | [[https://doi.org/10.1089/cmb.2011.0118|Braga et al. 2011]] | {{teaching:2021winter:cg:sheet07.pdf | Sheet 07}} | | 16.12. | DCJ-indel: restricted / diameter and triangular inequality,\\ Capped relational graph | {{teaching:2021winter:cg:lecture08.pdf | Slides 08}} | [[https://doi.org/10.1109/TCBB.2014.2329297|Braga and Stoye, 2015]],\\ [[https://doi.org/10.1186/1471-2105-12-S9-S13|Braga et al. 2011b]],\\ [[https://doi.org/10.1089/cmb.2020.0434|Bohnenkämper et al. 2020]] | {{teaching:2021winter:cg:sheet08.pdf | Sheet 08}} | | 23.12. | Indel-potential via transitions / Overview + Review | {{teaching:2021winter:cg:lecture09.pdf | Slides 09}} | [[https://doi.org/10.1089/cmb.2020.0434|Bohnenkämper et al. 2020]] | * {{teaching:2021winter:cg:sheet09-christmas.pdf | Sheet 09 - Christmas}} * | | 30.12. | - NO LECTURE (Christmas break) - | -- | -- | -- | | 06.01. | Tutorial only (by Leonard) | -- | -- | -- | | 13.01. | ILP / DCJ distance of balanced genomes | {{teaching:2021winter:cg:lecture10.pdf | Slides 10}} | [[https://doi.org/10.1089/cmb.2014.0096|Shao et al. 2015]] | {{teaching:2021winter:cg:sheet10.pdf | Sheet 10}} | | 20.01. | DCJ-indel distance of natural genomes\\ (guest lecture by Leonard) | {{teaching:2021winter:cg:lecture11.pdf | Slides 11}} | [[https://doi.org/10.1089/cmb.2020.0434|Bohnenkämper et al. 2020]] | {{teaching:2021winter:cg:sheet11.pdf | Sheet 11}} | | 27.01. | DCJ distance and DCJ-indel distance\\ of family-free genomes | {{teaching:2021winter:cg:lecture12.pdf | Slides 12}} | [[https://almob.biomedcentral.com/articles/10.1186/s13015-015-0041-9|Martinez et al. (2015)]],\\ [[https://almob.biomedcentral.com/articles/10.1186/s13015-021-00183-8|Rubert et al. 2021 (A)]] | {{teaching:2021winter:cg:sheet12.pdf | Sheet 12}} | | 03.02. | Inferring orthologs via FF rearrangements | {{teaching:2021winter:cg:lecture13.pdf | Slides 13}} | [[https://www.worldscientific.com/doi/abs/10.1142/S021972002140014X|Rubert et al. 2021 (B)]] | -- | | 10.02. | - NO LECTURE - | -- | -- | -- | | 17.02. | - NO LECTURE - | -- | -- | -- | | 24.02. | Exam | -- | -- | -- |