Efficient representation of k-mer sets

• Název práce v češtině: Efektivní reprezentace množin k-merů
• Název v anglickém jazyce: Efficient representation of k-mer sets
• Klíčová slova: množiny k-merů|nejkratší nadřetězec|bioinformatika|hladový algoritmus
• Klíčová slova anglicky: k-mer sets|shortest superstring|bioinformatics|greedy algorithm
• Akademický rok vypsání: 2021/2022
• Typ práce: bakalářská práce
• Jazyk práce: angličtina
• Ústav: Informatický ústav Univerzity Karlovy (32-IUUK)
• Vedoucí / školitel: Mgr. Pavel Veselý, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 27.07.2022
• Datum zadání: 04.08.2022
• Datum potvrzení stud. oddělením: 15.02.2023
• Datum a čas obhajoby: 07.09.2023 09:00
• Datum odevzdání elektronické podoby: 12.07.2023
• Datum odevzdání tištěné podoby: 12.07.2023
• Datum proběhlé obhajoby: 07.09.2023
• Oponenti: doc. Mgr. Petr Kolman, Ph.D.
• Konzultanti: Karel Břinda

Zásady pro vypracování

This thesis will focus on efficient representations of k-mer sets, which are substrings of length k obtained from a DNA sequence. The student will study state-of-the-art methods from the literature (e.g., simplitigs) and experimentally compare them to approximation algorithms for the shortest superstring problem. The aim is also to generalize existing concepts for representing k-mer sets into an overarching definition.

The thesis is a continuation of the student's Individual Software Project.

Seznam odborné literatury

K Břinda, M Baym, G Kucherov: Simplitigs as an efficient and scalable representation of de Bruijn graphs. Genome biology, 2021.
A Rahman, P Medvedev: Representation of k-mer Sets Using Spectrum-Preserving String Sets. International Conference on Research in Computational Molecular Biology, 2020.
S Schmidt, S Khan, J Alanko, AI Tomescu: Matchtigs: minimum plain text representation of kmer sets. bioRxiv, 2021.
D Gusfield: Algorithms on Strings, Trees, and Sequences. Cambridge University Press, 1997.