Eulertigs: minimum plain text representation of k-mer sets without repetitions in linear time

Autor:	Sebastian Schmidt, Jarno N. Alanko
Jazyk:	angličtina
Rok vydání:	2023
Předmět:	Spectrum preserving string sets Eulerian cycle Suffix tree Bidirected arc-centric de Bruijn graph K-mer based methods Biology (General) QH301-705.5 Genetics QH426-470
Zdroj:	Algorithms for Molecular Biology, Vol 18, Iss 1, Pp 1-21 (2023)
Druh dokumentu:	article
ISSN:	1748-7188
DOI:	10.1186/s13015-023-00227-1
Popis:	Abstract A fundamental operation in computational genomics is to reduce the input sequences to their constituent k-mers. For maximum performance of downstream applications it is important to store the k-mers in small space, while keeping the representation easy and efficient to use (i.e. without k-mer repetitions and in plain text). Recently, heuristics were presented to compute a near-minimum such representation. We present an algorithm to compute a minimum representation in optimal (linear) time and use it to evaluate the existing heuristics. Our algorithm first constructs the de Bruijn graph in linear time and then uses a Eulerian-cycle-based algorithm to compute the minimum representation, in time linear in the size of the output.
Databáze:	Directory of Open Access Journals
Externí odkaz:	https://doaj.org/article/2adedb00ad7f47d09c675a1b77b83a20 Zobrazit plný text záznamu View record in DOAJ Plný text ve formátu PDF Plný text ve formátu HTML
Nepřihlášeným uživatelům se plný text nezobrazuje	K zobrazení výsledku je třeba se přihlásit.