Maskované nadřetězce pro efektivní reprezentaci a indexování množin k-merů
| 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ů|nadřetězec|problém nejkratšího nadřetězce|bioinformatika|hladový algoritmus |
| Klíčová slova anglicky: | k-mer sets|superstring|shortest superstring problem|bioinformatics|greedy algorithm |
| Akademický rok vypsání: | 2023/2024 |
| Typ práce: | bakalářská práce |
| Jazyk práce: | |
| Ú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 |
| 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. |