Differences

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

--- teaching:2026summer:seqalgobioinfo [2026/04/16 11:31]
luca created
+++ teaching:2026summer:seqalgobioinfo [2026/04/16 14:50] (current)
luca
@@ Line 1: / Line 1: @@
-| [[https://ekvv.uni-bielefeld.de/kvv_publ/publ/vd?id=659868809]] | Parmigiani | Summer 2026 | Wednesday 10:15-11:45 | U10-146 |
+| [[https://ekvv.uni-bielefeld.de/kvv_publ/publ/vd?id=659868809 | 392174]] | Parmigiani | Summer 2026 | Wednesday 10:15-11:45 | U10-146 |
 This course is held in English.\\
 \\
-Based on selected **book chapters** from *Genome-Scale Algorithm Design* (Veli Mäkinen, Djamal Belazzougui, Fabio Cunial, Alexandru I. Tomescu),
+Based on selected **book chapters** from **Genome-Scale Algorithm Design** (Veli Mäkinen, Djamal Belazzougui, Fabio Cunial, Alexandru I. Tomescu),
 the participants will give oral presentations (20-45 min) and write a
 short summary (5-10 pages) about the an algorithmic problem in bioinformatics and their solutions. Talks and essays must be done in English.
@@ Line 19: / Line 19: @@
 Possible concrete chapters/topics to be presented and discussed in the seminar include:
-==== Indexing and Pattern Matching ====
+==== 5. Network flows ====
-  * Exact pattern matching algorithms
+  * 5.1 Flows and their decompositions
-  * Suffix arrays and suffix trees
+  * 5.2 Minimum-cost flows and circulations
-  * Burrows-Wheeler Transform (BWT)
+  * 5.3 Bipartite matching problems
-  * FM-index and backward search
+  * 5.4 Covering problems
-==== Compressed Data Structures ====
+==== 7. Hidden Markov models ====
-  * Rank and select data structures
+  * 7.1 Definition and basic problems
-  * Wavelet trees
+  * 7.2 The Viterbi algorithm
-  * Compressed suffix arrays
+  * 7.3 The forward and backward algorithms
-  * Succinct text indexes
+  * 7.4 Estimating HMM parameters
-==== k-mer and q-gram based methods ====
+==== 8. Classical indexes ====
-  * q-gram indexes
+  * 8.1 k-mer index
-  * Minimizers and sketches
+  * 8.2 Suffix array
-  * Applications of k-mer spectra
+  * 8.3 Suffix tree
-  * String similarity and filtering techniques
+  * 8.4 Applications of the suffix tree
-==== Graph-based genome representations ====
+==== 9. Burrows-Wheeler indexes ====
-  * De Bruijn graphs
+  * 9.1 Burrows-Wheeler transform (BWT)
-  * Compacted and colored de Bruijn graphs
+  * 9.2 BWT index
-  * Variation graphs and pan-genome models
+  * 9.3 Space-efficient construction of the BWT
+  * 9.4 Bidirectional BWT index
-==== Approximate Matching ====
+==== 10. Alignment-based genome analysis ====
+  * 10.1 Variation calling
+  * 10.2 Pattern partitioning for read alignment
+  * 10.3 Dynamic programming along suffix tree paths
+  * 10.4 Backtracking on BWT indexes
+==== 11. Alignment-free genome analysis and comparison ====
+  * 11.1 De novo variation calling
+  * 11.2 Space-efficient genome analysis
+  * 11.3 Comparing genomes without alignment
+==== 12. Compression of genome collections ====
+  * 12.1 Lempel-Ziv parsing
+    * 12.1.1 Basic algorithm for Lempel-Ziv parsing
+    * 12.1.2 Space-efficient Lempel-Ziv parsing
+  * 12.2 Bit-optimal Lempel-Ziv compression
+==== 13. Fragment assembly ====
+  * 13.1 Sequencing by hybridization
+  * 13.2 Contig assembly
+  * 13.3 Scaffolding
+  * 13.4 Gap filling
+==== 14. Haplotype analysis ====
+  * 14.1 Haplotype assembly and phasing
+    * 14.1.1 Minimum error correction
+    * 14.1.2 Hardness
+  * 14.2 Haplotype matching and positional BWT
+==== 15. Pangenomics ====
+  * 15.1 Overview of pangenome representations
+    * 15.1.1 Colored de Bruijn graphs
+    * 15.2 Aligning reads to a pangenome
+  * 15.3 Variation calling over pangenomes
-  * Edit distance algorithms
-  * Seed-and-extend paradigm
-  * Filtering techniques for approximate string matching

Genome Informatics

Differences