Masked Superstrings for Efficient k-Mer Set Representation and Indexing

• Název práce v češtině: Maskované nadřetězce pro efektivní reprezentaci a indexování množin k-merů
• Název v anglickém jazyce: Masked Superstrings for Efficient k-Mer Set Representation and Indexing
• Klíčová slova: množiny k-merů|bioinformatika|výpočetní genomika|datové struktury|algoritmy|problém nejkratšího nadřetězce
• Klíčová slova anglicky: k-mer sets|bioinformatics|computational genomics|data structures|algorithms|shortest superstring problem
• Akademický rok vypsání: 2023/2024
• 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í: 21.09.2023
• Datum zadání: 21.09.2023
• Datum potvrzení stud. oddělením: 09.10.2023
• Datum a čas obhajoby: 28.06.2024 09:00
• Datum odevzdání elektronické podoby: 07.05.2024
• Datum odevzdání tištěné podoby: 07.05.2024
• Datum proběhlé obhajoby: 28.06.2024
• Oponenti: prof. Paul Medvedev
• Konzultanti: Karel Břinda

Zásady pro vypracování

Student se zaměří na prozkoumání algoritmů, které počítají efektivní textové reprezentace množin k-merů, což jsou podřetězce délky k získané z DNA sekvencí. Řešitel si nastuduje nejlepší známé metody pro reprezentaci množiny k-merů a porovná je s výstupy aproximačních algoritmů pro problém nejkratšího nadřetězce. Cílem je vyvinout nový framework založený na nadřetězcích, který bude pro vstupní množiny k-merů počítat jejich co nejkratší textové reprezentace a bude umožňovat efektivní indexování.

Práce navazuje na řešitelův ročníkový projekt KmerCamel.

Seznam odborné literatury

Břinda, Karel, Michael Baym, and Gregory Kucherov. "Simplitigs as an efficient and scalable representation of de Bruijn graphs." Genome biology 22 (2021): 1-24.
Rahman, Amatur, and Paul Medevedev. "Representation of k-mer sets using spectrum-preserving string sets." Journal of Computational Biology 28.4 (2021): 381-394.
Schmidt, Sebastian, Shahbaz Khan, Jarno N. Alanko, Giulio E. Pibiri, and Alexandru I. Tomescu. "Matchtigs: minimum plain text representation of k-mer sets." Genome Biology 24, no. 1 (2023): 1-32.
Schmidt, Sebastian, and Jarno N. Alanko. "Eulertigs: minimum plain text representation of k-mer sets without repetitions in linear time." Algorithms for Molecular Biology 18, no. 1 (2023).
Ukkonen, Esko. "A linear-time algorithm for finding approximate shortest common superstrings." Algorithmica 5, no. 1-4 (1990): 313-323.
Gusfield, Dan: Algorithms on Strings, Trees, and Sequences. Cambridge University Press, 1997.