Název:
Efektivní reprezentace množin k-merů
Překlad názvu:
Efficient representation of k-mer sets
Autoři:
Milyutina, Ekaterina ; Veselý, Pavel (vedoucí práce) ; Kolman, Petr (oponent) Typ dokumentu: Bakalářské práce
Rok:
2023
Jazyk:
eng
Abstrakt: In this thesis we explore and compare various methods for efficient k-mer set representation. We evaluate traditional de Bruijn graph representation techniques against greedy approximation algorithms for the Shortest Superstring Problem. We describe the linear- time implementation of the well-known Greedy algorithm by Ukkonen [1990] and extend it to another related algorithm, called TGreedy. In addition, we test selected algorithms on a bacterial genome and pangenome to highlight the differences in the size of their output representation and the computational resources used, providing an insight into their respective efficiencies.
Klíčová slova:
množiny k-merů|nejkratší nadřetězec|bioinformatika|hladový algoritmus; k-mer sets|shortest superstring|bioinformatics|greedy algorithm