====== Algorithms in Comparative Genomics (2V + 2Ü) ====== | [[https://ekvv.uni-bielefeld.de/kvv_publ/publ/vd?id=133279728| 392189]]/[[https://ekvv.uni-bielefeld.de/kvv_publ/publ/vd?id=133279999|92]] | Dörr | Winter 2018 | Th 09:00 - 10:15 (Ü), 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 ===== Inversion Visualization Software ===== Prof. Istvan Miklos, from the {{http://renyi.hu/staff/bioinf.html|Bioinformatics Group}} in Alfréd Rényi Institute in Budapest, kindly shared his visualization software for the Breakpoint Graph. It is written in Java, and you can download it {{ teaching:2018winter: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, the numbers separated with a . There is an example in the provided archive. Select the reality 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** | **Notes** | ** Ex. ** | ** Remarks ** | | 11.10.2018 | -- no class -- | -- | -- | | | 18.10.2018 | Genome rearrangements, signed reversal distance, part I | {{ teaching:2018winter:cg:skript_01.pdf |01}}/{{ teaching:2018winter:cg:skript_02.pdf |02}} | {{ teaching:2018winter:cg:exercise01.pdf | 01 }} | lit.: {{ http://epubs.siam.org/doi/10.1137/S0097539793250627 |1}}, {{ teaching:2018winter:cg:pevzner_chapter10.pdf |2}} | | 25.10.2018 | Signed reversal distance, part II | {{ teaching:2018winter:cg:skript_02.pdf | 02 }} | {{ teaching:2018winter:cg:exercise02.pdf | 02 }} | lit.: {{ teaching:2018winter:cg:pevzner_chapter10.pdf |2}}, permutations: {{teaching:2018winter:cg:pi_2.txt|π^2}}, {{teaching:2018winter:cg:pi_3.txt|π^3}}, {{teaching:2018winter:cg:hurdle.txt|hurdle}}, {{teaching:2018winter:cg:fortress.txt|fortress}} | | 01.11.2018 | -- no class -- | -- | -- | -- | | 08.10.2018 | Signed reversal distance, part III; Sorting by reversals | {{ teaching:2018winter:cg:skript_02.pdf |02}}/{{teaching:2018winter:cg:skript_03.pdf |03}} | {{ teaching:2018winter:cg:exercise03.pdf | 03 }} |lit.: {{ teaching:2018winter:cg:inversionbergeron.pdf |3}}, permutations: {{teaching:2018winter:cg:pi_4.txt|π^4}}, {{teaching:2018winter:cg:pi_5.txt|π^5}}, {{teaching:2018winter:cg:pi_6.txt|π^6}} | | 15.11.2018 | Double-Cut-and-Join (DCJ) | {{ teaching:2018winter:cg:skript_04.pdf |04}} | {{ teaching:2018winter:cg:exercise04.pdf | 04 }} | lit.: {{ teaching:2018winter:cg:Bergeron_DCJ.pdf |4}} | | 22.11.2018 | DCJ with Insertions and Deletions | {{teaching:2018winter:cg:skript_05.pdf |05}} | {{ teaching:2018winter:cg:exercise05.pdf | 05 }} | lit.: {{ teaching:2018winter:cg:dcjindel_braga_willing.pdf| 5}} | | 29.11.2018 | Genome Halving | {{teaching:2018winter:cg:skript_06.pdf | 06 }} | {{ teaching:2018winter:cg:exercise06.pdf | 06 }} | lit.: {{ teaching:2018winter:cg:mixtacki_2008.pdf| 6}}, [[https://bmcbioinformatics.biomedcentral.com/articles/10.1186/1471-2105-10-120 | 7 ]]| | 06.12.2018 | Guest lecture by F. Martinez: On the Gene Family-free DCJ Distance and Similarity | {{teaching:2018winter:cg:ffdcj.pdf | slides }} | -- | lit.: [[https://bmcbioinformatics.biomedcentral.com/articles/10.1186/s12859-018-2130-5 | 8 ]] | | 13.12.2018 | Algebraic Theory of Genome Rearrangements | {{teaching:2018winter:cg:skript_07.pdf | 07 }} | {{ teaching:2018winter:cg:exercise07.pdf | 07 }} | lit.: {{ teaching:2018winter:cg:Medianis_Algebraic_Theory.pdf| 9}} | | 20.12.2018 | Common Intervals of Permutations | {{teaching:2018winter:cg:skript_08.pdf | 08 }} | {{ teaching:2018winter:cg:exercise08.pdf | 08 }} | lit.: {{ teaching:2018winter:cg:heber_mayr_stoye.pdf| 10}}, {{ teaching:2018winter:cg:bergeron_common_intervals.pdf| 11}}, [[ http://doi.org/10.1016/j.tcs.2014.06.004| 12]] | | 27.12.2018 | -- no class -- | -- | -- | -- | | 03.01.2019 | -- no class -- | -- | -- | -- | | 10.01.2019 | Common Intervals of Strings | {{teaching:2018winter:cg:skript_09.pdf | 09}},{{teaching:2018winter:cg:slides09.pdf | slides }} | {{ teaching:2018winter:cg:exercise09.pdf | 09 }} | lit.: {{ teaching:2018winter:cg:schmidt.pdf| 13}}, {{ teaching:2018winter:cg:didier.pdf| 14}}, {{ teaching:2018winter:cg:bender.pdf| 15}} | | 17.01.2019 | Gene Teams | -- | -- | lit.: {{ teaching:2018winter:cg:gene_teams.pdf| 16}}, E. Demaine: Recurrences [[https://www.youtube.com/watch?v=whjt_N9uYFI |1]], [[https://www.youtube.com/watch?v=-EQTVuAhSFY|2]] | | 24.01.2019 | Exam prep Q&A | -- | -- | -- | | 31.01.2019 | Oral exam | -- | -- | -- | ---- Back to [[:teaching|Teaching]]