===== K-mer basierte Algorithmen in der Bioinformatik (S) =====
| [[https://ekvv.uni-bielefeld.de/kvv_publ/publ/vd?id=514778069|392219]] | Wittler | Summer 2025 | Wednesday 10:15-11:45 | U10-146 |\\
\\


(Je nach Wunsch/Bedarf der Studierenden wird das Seminar auf Deutsch oder Englisch durchgeführt.\\
Depending on the wishes/demands of the students, this seminar can be held in English or German.)\\
\\

Based on original research papers, the participants will give oral presentations (20-45 min) and write short summaries (5-10 pages) about algorithmic problems in bioinformatics and their solutions. Talks and essays can be done in German or English. The first day covers an overview of possible topics, which will then be distributed to the students. Aspects of scientific writing and presenting will be covered as well.\\
\\

The overarching topic of this semester are **//k//-mers** (a.k.a. //q-grams//). This simple concept builds a basis for many algorithmic solutions in bioinformatics, such as assembly, alignment, genome comparison, pangenomics, etc.\\
\\

To practice algorithm design and presentation, each participant will specify a simple //k//-mer counting algorithm and present it using pseudocode (a LaTeX template will be provided). Afterwards, they will implement the algorithm as a basic prototype. In a coding showdown, all implementations will battle it out to see which one takes the crown! (This can be credited as "392041 Implementation of Algorithms (Ü)", 1 LP.) 

\\


Possible concrete methods/publications to be presented/discussed in the seminar are:


==== Assembly ====

  * Zerbino, Daniel R., and Ewan Birney. "Velvet: algorithms for de novo short read assembly using de Bruijn graphs." [[https://genome.cshlp.org/content/18/5/821.full.pdf|Genome research 18.5 (2008): 821-829.]]
  * Chikhi, Rayan, and Guillaume Rizk. "Space-efficient and exact de Bruijn graph representation based on a Bloom filter. (Minia)" [[https://link.springer.com/article/10.1186/1748-7188-8-22|Algorithms for Molecular Biology 8.1 (2013): 1-9.]]


==== De Bruijn Graphs ====

  * Holley, Guillaume, and Páll Melsted. "Bifrost: highly parallel construction and indexing of colored and compacted de Bruijn graphs." [[https://genomebiology.biomedcentral.com/articles/10.1186/s13059-020-02135-8|Genome biology 21.1 (2020): 1-20.]]
  * Ekim, Barış, Bonnie Berger, and Rayan Chikhi. "Minimizer-space de Bruijn graphs: Whole-genome assembly of long reads in minutes on a personal computer." [[https://doi.org/10.1016/j.cels.2021.08.009|Cell systems 12.10 (2021): 958-968.]]

==== Alignment ====

  * Li, Heng. "Minimap2: pairwise alignment for nucleotide sequences." [[https://academic.oup.com/bioinformatics/article/34/18/3094/4994778?login=false|Bioinformatics 34.18 (2018): 3094-3100.]]
  * Ondov, Brian D., et al. "Mash: fast genome and metagenome distance estimation using MinHash." [[https://genomebiology.biomedcentral.com/articles/10.1186/s13059-016-0997-x?ref=https://codemonkey.link|Genome biology 17.1 (2016): 1-14.]]

==== Counting k-mers ====

  * Kokot, Marek, Maciej Długosz, and Sebastian Deorowicz. "KMC 3: counting and manipulating //k//-mer statistics." [[https://academic.oup.com/bioinformatics/article/33/17/2759/3796399?login=false|Bioinformatics 33.17 (2017): 2759-2761.]] (plus previous versions)
  * Lucas Robidou and Pierre Peterlongo. "fimpera: drastic improvement of Approximate Membership Query data-structures with counts" [[https://www.biorxiv.org/content/10.1101/2022.06.27.497694v3|bioRxiv (2023)]]
  *  Téo Lemane, Paul Medvedev, Rayan Chikhi, and Pierre Peterlongo. "kmtricks: efficient and flexible construction of Bloom filters for large sequencing data collections." [[https://academic.oup.com/bioinformaticsadvances/article/2/1/vbac029/6576015|Bioinformatics Advances, 2.1 (2022)]]
  *  Jens Zentgraf and Sven Rahmann. "Fast gapped //k//-mer counting with subdivided multi-way bucketed Cuckoo hash table." [[https://drops.dagstuhl.de/opus/volltexte/2022/17046/pdf/LIPIcs-WABI-2022-12.pdf|In 22nd International Workshop on Algorithms in Bioinformatics (WABI). Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2022)]]

==== Storing k-mers ====

  *  Sebastian Schmidt and Jarno N. Alanko. "Eulertigs: minimum plain text representation of //k//-mer sets without repetitions in linear time." [[https://link.springer.com/article/10.1186/s13015-023-00227-1|Algorithms for Molecular Biology 18(1), 5 (2023)]]
  * Giulio Ermanno Pibir. "Sparse and skew hashing of K-mers." [[https://academic.oup.com/bioinformatics/article/38/Supplement_1/i185/6617506?login=true|Bioinformatics 38.Suppl1 (2022):i185-i194.]]

==== Pangenomics ====

  * Luca Parmigiani, Roland Wittler, and Jens Stoye. “Revisiting pangenome openness with k-mers.” [[https://peercommunityjournal.org/item/10.24072/pcjournal.415.pdf|Peer Community Journal (4):e47 (2024)]] 

==== Timetable ====

| 09.04. | Organization,  topic selection, Scientific reading  | {{:teaching:2022summer:algbioinf:howtoread.pdf|Slides: HowToRead}} |
| 16.04. | Pseudocode | [[https://texdoc.org/serve/algorithm2e/0|algorithm2e-docu]], {{:teaching:2025summer:kmer:template_algo.tex.pdf|LaTeX template (remove .pdf from file name)}}, {{:teaching:2025summer:kmer:template_algo.pdf|notes/example}} |
| 23.04. | -- (self study) | [[:teaching:2024summer:karp:writing|Scientific Writing]], [[https://doi.org/10.1371/journal.pcbi.0030077|Ten Simple Rules for Making Good Oral Presentations, Philip E Bourne]], [[https://doi.org/10.1371/journal.pcbi.1005373|Ten simple rules for short and swift presentations, Christopher J. Lortie]] |
| 30.04. | -- |
| 07.05. | Pseudocode vorstellen |
| 14.05. | KMC 3: counting and manipulating //k//-mer statistics | Kathrin |
| 21.05. | k-mer counting challenge | (fast) alle | 
| 28.05. | -- |
| 04.06. | Fast gapped //k//-mer counting with subdivided multi-way bucketed Cuckoo hash table | Sofie  |
|            | Minimizer-space de Bruijn graphs: Whole-genome assembly of long reads in minutes on a personal computer | Liliana |
| 11.06. | Sparse and skew hashing of K-mers | Alena |
| 18.06. | Space-efficient and exact de Bruijn graph representation based on a Bloom filter. (Minia) | Max |
| 25.06. | Minimap2: pairwise alignment for nucleotide sequences | Igor |
|             | Revisiting pangenome openness with k-mers | Mathis |
| 02.07. | -- |
| 09.07. | |
| 16.07. | -- |
 
==== Details on the k-mer counting exercise ====

**Input:**
  * Multiple fasta file, containing nucleotide sequences (small or capital letters, maybe N's)
  * //k//-mer length **k**
  * threshold **c**

**Output:**
  * Number of canonical //k//-mers occurring at least **c** times.