Masked Superstrings for Efficient k-Mer Set Representation and Indexing

• Thesis title in Czech: Maskované nadřetězce pro efektivní reprezentaci a indexování množin k-merů
• Thesis title in English: Masked Superstrings for Efficient k-Mer Set Representation and Indexing
• Key words: množiny k-merů|bioinformatika|výpočetní genomika|datové struktury|algoritmy|problém nejkratšího nadřetězce
• English key words: k-mer sets|bioinformatics|computational genomics|data structures|algorithms|shortest superstring problem
• Academic year of topic announcement: 2023/2024
• Thesis type: Bachelor's thesis
• Thesis language: angličtina
• Department: Computer Science Institute of Charles University (32-IUUK)
• Supervisor: Mgr. Pavel Veselý, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 21.09.2023
• Date of assignment: 21.09.2023
• Confirmed by Study dept. on: 09.10.2023
• Date and time of defence: 28.06.2024 09:00
• Date of electronic submission: 07.05.2024
• Date of submission of printed version: 07.05.2024
• Date of proceeded defence: 28.06.2024
• Opponents: prof. Paul Medvedev
• Advisors: Karel Břinda

Guidelines

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.

References

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.