Boosting Backward Search Throughput for FM-Index Using a Compressed Encoding

Autor:	Jesús Alastruey-Benedé, Pablo Ibáñez, Jose Manuel Herruzo, Sonia Gonzalez-Navarro, Oscar Plata, Víctor Viñals
Rok vydání:	2019
Předmět:	Boosting (machine learning) Compressed data structure Computer science Genomic data ADN Pattern matching ADN - Análisis secuencial Search computing Data structure Algorithm FM-index Data compression
Zdroj:	RIUMA. Repositorio Institucional de la Universidad de Málaga instname DCC
Popis:	The rapid development of DNA sequencing technologies has demanded for com- pressed data structures supporting fast pattern matching queries. FM-index is a widely-used compressed data structure that also supports fast pattern matching queries. It is common for the exact matching algorithm to be memory bound, resulting in poor performance. Searching several symbols in a single step improves data locality, although the memory bandwidth requirements remains the same. We propose a new data-layout of FM-index, called Split bit-vector, that compacts all data needed to search k symbols in a single step (k-step), reducing both memory movement and computing requirements at the cost of increasing memory footprint. Universidad de Málaga. Campus de Excelencia Internacional Andalucía Tech.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6ad999e02d29003bde6cb3e6f792266e https://hdl.handle.net/10630/17525 Zobrazit plný text záznamu