261-5112-00L Advanced Approaches for Population Scale Compressive Genomics (Autumn 2019)
|Semester||Autumn Semester 2019|
|Language of instruction||English|
Research in Biology and Medicine have been transformed into disciplines of applied data science over the past years. Not only size and inherent complexity of the data but also requirements on data privacy and complexity of search and access pose a wealth of new research questions.
This interactive course will explore the latest research on algorithms and data structures for population scale genomics applications and give insights into both the technical basis as well as the domain questions motivating it.
Over the duration of the semester, the course will cover three main topics. Each of the topics will consist of 70-80% lecture content and 20-30% seminar content.
1) Algorithms and data structures for text and graph compression. Motivated through applications in compressive genomics, the course will cover succinct indexing schemes for strings, trees and general graphs, compression schemes for binary matrices as well as the efficient representation of haplotypes and genomic variants.
2) Stochastic data structures and algorithms for approximate representation of strings and graphs as well as sets in general. This includes winnowing schemes and minimizers, sketching techniques, (minimal perfect) hashing and approximate membership query data structures.
3) Data structures supporting encryption and data privacy. As an extension to data structures discussed in the earlier topics, this will include secure indexing using homomorphic encryption as well as design for secure storage and distribution of data.
Prerequisites / Notice
Data Structures & Algorithms
The list of papers for presentation will be announced within the first weeks of the lecture.
The lecture will be held at ETH in CHN D 48 (link to location). Wednesdays 13-15.
|25.09.2019||Lecture: Introduction to the topic and Formalities||Lecture Slides 01|
|02.10.2019||Lecture: String indexing (suffix arrays, BWT, FM-index)||TBA|
|09.10.2019||Lecture: Space-efficient index construction||TBA|
|16.10.2019||Lecture: Rank/select structures, BWT construction, Bi-directional BWT||TBA|
|23.10.2019||Lecture: Variations of BWT (Indexing of trees and graphs, PBWT, gPBWT, generalized compressed suffix arrays)||TBA|
|30.10.2019||Lecture: Genome compression||TBA|
|13.11.2019||Lecture: Alignment-free genome comparison (kernels, winnowing, hashing)||TBA|
|20.11.2019||Lecture: Approximate genome representation using filters||TBA|
|27.11.2019||Lecture: Sketching techniques, Cardinality estimation||TBA|
|04.12.2019||Lecture: Homomorphic encryption for bioinformatics||TBA|
|11.12.2019||Lecture: Student seminars; Secure communication for personalized genomics||No slides|
|18.12.2019||Lecture: Recap / Exam prep||TBA|