You are here: home » teaching » 2018winter » cg

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

— 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]]