This shows you the differences between two versions of the page.
— |
teaching:2018winter:cg [2020/02/14 09:07] (current) |
||
---|---|---|---|
Line 1: | Line 1: | ||
+ | |||
+ | ====== 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 <tab>. 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]] |