Thesis (Selection of subject)Thesis (Selection of subject)(version: 368)
Thesis details
   Login via CAS
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 of electronic submission:07.05.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.
 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html