====== Algorithms in Comparative Genomics (2V + 2Ü) ====== | [[https://ekvv.uni-bielefeld.de/kvv_publ/publ/vd?id=228328203| 392189]] | Dias Vieira Braga | Winter 2020/21 | Th 10:15 - 11:45 (V) online via Zoom | | [[https://ekvv.uni-bielefeld.de/kvv_publ/publ/vd?id=228328762|392192]] | Bohnenkämper | Winter 2020/21 | Fr 08:30 - 10:00 (Ü) online via Zoom | The details of both Zoom meetings were already announced via mail list. ===== 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 and gene clusters. Algorithms discussed in this course are mostly combinatorial by nature, similar to the sequence analysis course. This lecture can ideally be combined with the seminar [[https://gi.cebitec.uni-bielefeld.de/teaching/2020winter/compan|"Computational Pangenomics (2S)"]]. 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 ===== to be announced later ===== Topics ===== - Distance and Sorting * Breakpoint Distance * Double-Cut-and-Join (DCJ) distance * DCJ-indel distance * Reversal Distance * Single-Cut-or-Join (SCJ) distance - Computing NP-hard distances via ILP * Balanced genomes * Natural genomes * Family-free genomes - Ancestral Reconstruction * SCJ Median * Small Parsimony - Common Intervals and Gene Clusters ===== 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 (S) ^ S + notes ^ Literature ^ Exercises ^ | 29.10. | Introduction, Genomes, Breakpoint distance | {{teaching:2020winter:cg:cg01.pdf | S01}} | {{teaching:2020winter:cg:cg01-notes.pdf | SN01}} | [[https://doi.org/10.1186/1471-2105-10-120|Tannier et al. 2009]] | {{teaching:2020winter:cg:sheet01.pdf | Ex01}}| | 05.11. | Breakpoint and Single-Cut-or-Join (SCJ) distances | {{teaching:2020winter:cg:cg02.pdf | S02}} | {{teaching:2020winter:cg:cg02-notes.pdf | SN02}} | [[https://doi.org/10.1109/TCBB.2011.34|Feijão & Meidanis 2011]] | {{teaching:2020winter:cg:sheet02.pdf | Ex02}} | | 12.11. | Breakpoint and SCJ median and halving | {{teaching:2020winter:cg:cg03.pdf | S03}} | {{teaching:2020winter:cg:cg03-notes.pdf | SN03}} | | {{teaching:2020winter:cg:sheet03.pdf | Ex03}} | | 19.11. | Breakpoint median/ Double-Cut-and-Join (DCJ) halving | {{teaching:2020winter:cg:cg04.pdf | S04}} | {{teaching:2020winter:cg:cg04-notes.pdf | SN04}} | {{teaching:2020winter:cg:b1998.pdf | Bryant 1998}}, [[https://doi.org/10.1007/978-3-540-69733-6_28|Mixtacki 2008]] | {{teaching:2020winter:cg:sheet04.pdf | Ex04}} | | 26.11. | DCJ distance and relational graph | {{teaching:2020winter:cg:cg05.pdf | S05}} | {{teaching:2020winter:cg:cg05-notes.pdf | SN05}} | [[https://doi.org/10.1007/11851561_16|Bergeron et al. 2006]],\\ [[https://doi.org/10.1089/cmb.2011.0116|Kováč et al. 2011]] |{{teaching:2020winter:cg:sheet05.pdf | Ex05}} | | 03.12. | Inversion distance and relational diagram | {{teaching:2020winter:cg:cg06.pdf | S06}} | {{teaching:2020winter:cg:cg06-notes.pdf | SN06}} | {{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:2020winter:cg:sheet06.pdf | Ex06}} | | 10.12. | Inversion distance / DCJ-indel distance | {{teaching:2020winter:cg:cg07.pdf | S07}} | {{teaching:2020winter:cg:cg07-notes.pdf | SN07}} | [[https://doi.org/10.1089/cmb.2011.0118|Braga et al. 2011]]| {{teaching:2020winter:cg:sheet07.pdf | Ex07}} | | 17.12. | DCJ-indel distance / Restricted DCJ-indel distance| {{teaching:2020winter:cg:cg08.pdf | S08}} | {{teaching:2020winter:cg:cg08-notes.pdf | SN08}}| [[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]] | {{teaching:2020winter:cg:sheet08-christmas.pdf | Ex08 - Christmas}} | | 07.01. | Capped relational graph | {{teaching:2020winter:cg:cg09.pdf | S09}} | {{teaching:2020winter:cg:cg09-notes.pdf | SN09}} | [[https://doi.org/10.1089/cmb.2020.0434|Bohnenkämper et al. 2020]] | {{teaching:2020winter:cg:sheet09.pdf | Ex09}} | | 14.01. | DCJ with duplicated genes (double-distance / balanced genomes) | {{teaching:2020winter:cg:cg10.pdf | S10}} | {{teaching:2020winter:cg:cg10-notes.pdf | SN10}} | [[https://doi.org/10.1186/1471-2105-10-120|Tannier et al. 2009]] | {{teaching:2020winter:cg:sheet10.pdf | Ex10}} | | 21.01. | ILP / DCJ distance of balanced genomes | {{teaching:2020winter:cg:cg11.pdf | S11}} | {{teaching:2020winter:cg:cg11-notes.pdf | SN11}} | [[https://doi.org/10.1089/cmb.2014.0096|Shao et al. 2015]] | {{teaching:2020winter:cg:sheet11.pdf | Ex11}} | | 28.01. | DCJ-indel distance of natural genomes\\ (guest lecture by L. Bohnenkämper) | {{teaching:2020winter:cg:cg12.pdf | S12}} | --- | [[https://doi.org/10.1089/cmb.2020.0434|Bohnenkämper et al. 2020]] | {{teaching:2020winter:cg:sheet12.pdf | Ex12}} | | 04.02. | DCJ distance and DCJ-indel distance\\ of family-free genomes | {{teaching:2020winter:cg:cg13.pdf | S13}} | {{teaching:2020winter:cg:cg13-notes.pdf | SN13}} | [[https://doi.org/10.4230/LIPIcs.WABI.2020.3|Rubert et al. 2020]] | {{teaching:2020winter:cg:sheet13.pdf | Ex13}} | | 11.02. | Small parsimony under SCJ / review | {{teaching:2020winter:cg:cg14.pdf | S14}} | {{teaching:2020winter:cg:cg14-notes.pdf | SN14}} | [[https://doi.org/10.1109/TCBB.2011.34|Feijão & Meidanis 2011]] | --- |