Differences

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

Link to this comparison view

teaching:2019winter:cg [2019/10/31 10:12]
teaching:2019winter: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=176728221| 392189]]/​[[https://​ekvv.uni-bielefeld.de/​kvv_publ/​publ/​vd?​id=176728523|92]] ​ | Wittler ​ | Winter 2019/​20 ​ | 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 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://​didy.uni-bielefeld.de/​teaching/​2019winter/​applcompgenomics|"​Applied Comparative Genomics"​]] -- a block seminar starting already on Sept. 16.
 +
 +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 =====
 +
 +... is deposited in the [[https://​bis.uni-bielefeld.de/​_layouts/​15/​UniBi.Learning/​Redirect.ashx?​CourseEkvvId=176728221|Lernraum]].
 +
 +===== Topics =====
 +
 +  - Distance and Sorting
 +    * Breakpoint Distance
 +    * Double-Cut-and-Join
 +    * Signed Reversal Distance
 +    * Genome Halving
 +  - Ancestral Reconstruction
 +    * DCJ Median
 +    * SCJ Small Parsimony I
 +    * SCJ Small Parsimony II
 +    * Ancestral/​consistent gene clusters
 +  - Gene Clusters
 +    * Common Intervals of Permutations
 +    * Common Intervals of Strings
 +    * Indeterminate Strings
 +  - Pangenomics
 +
 +===== Exercises =====
 +
 +^ Date    ^ Due ^ Topic                              ^ Exercises ​                                              ^
 +| 17.10. ​ | 24.10. ​ | Introduction,​ Breakpoint distance ​ | {{:​teaching:​2019winter:​cg:​exercise01.pdf|Exercises 1}}  |
 +| 24.10. ​ | 31.10. ​ | Double Cut and Join                | {{:​teaching:​2019winter:​cg:​exercise02.pdf|Exercises 2}}  |
 +| 31.10. ​ | 07.11. ​ | Inversion Distance (via DCJ)       | {{:​teaching:​2019winter:​cg:​exercise03.pdf|Exercises 3}}  |
 +| 07.11. ​ | 14.11. ​ | Genome Halving (under DCJ)         | {{:​teaching:​2019winter:​cg:​exercise04.pdf|Exercises 4}}  |
 +| 14.11. ​ | 21.11. ​ | DCJ Median ​                        | {{:​teaching:​2019winter:​cg:​exercise05.pdf|Exercises 5}}  |
 +| 21.11. ​ | 28.11. ​ | Small Parsimony under SCJ          | {{:​teaching:​2019winter:​cg:​exercise06.pdf|Exercises 6}}  |
 +| 28.11. ​ | 05.12. ​ | Small Parsimony under SCJ (cont'​d) | {{:​teaching:​2019winter:​cg:​exercise07.pdf|Exercises 7}}  |
 +| 05.12. ​ | 12.12. ​ | Consistency of gene clusters ​  | {{:​teaching:​2019winter:​cg:​exercise08.pdf|Exercises 8}}  |
 +| 12.12. ​ | 19.12. ​ | Generators for common intervals ​  | {{:​teaching:​2019winter:​cg:​exercise09.pdf|Exercises 9}}  |
 +| 19.12. ​ | 09.01. ​ | Generators, strong common intervals and PQ-trees ​  | {{:​teaching:​2019winter:​cg:​exercise10.pdf|Exercises 10}}  |
 +| 09.01. ​ | 16.01. ​ | Common intervals of strings ​  | {{:​teaching:​2019winter:​cg:​exercise11.pdf|Exercises 11}}  |
 +| 16.01. ​ | 23.01. ​ | Common intervals of indeterminate strings ​  | {{:​teaching:​2019winter:​cg:​exercise12.pdf|Exercises 12}}  |
 +| 23.01. ​ | 31.01. ​ | Pangenomics ​  | ... |
 +===== Materials =====
 +
 +PQ-Baum-Applet\\ Download {{:​teaching:​2012winter:​892PQTree.jar | PQTree.jar }} and run java -jar PQTree.jar -g n where n is the number of leaves for the initial PQ-Tree. Select the elements which shall appear consecutively by mouse click and Ctrl or shift in the list on the left side of the window. Then click Reduce to get the resulting tree. Use Reset to get the initial tree again. //​[Reference:​ J. Harris. A Graphical Java Implementation of PQ-Trees. www.jharris.ca/​portfolio/​academic.htm (last visited 09/​20/​2006),​ April 2002. Carleton University. Debugged by Roland Wittler, Bielefeld University.]// ​