RT Conference Proceedings
T1 Boosting Backward Search Throughput for FM-Index Using a Compressed Encoding
A1 Herruzo-Ruiz, José Manuel
A1 González-Navarro, Sonia
A1 Ibáñez, Pablo
A1 Viñals, Victor
A1 Alastruey-Benedé, Jesús
A1 Plata-González, Óscar Guillermo
K1 ADN - Análisis secuencial
AB The rapid development of DNA sequencing technologies has demanded for com-pressed data structures supporting fast pattern matching queries. FM-index is awidely-used compressed data structure that also supports fast pattern matchingqueries. 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 compactsall data needed to search k symbols in a single step (k-step), reducing both memorymovement and computing requirements at the cost of increasing memory footprint.
YR 2019
FD 2019-04-11
LK https://hdl.handle.net/10630/17525
UL https://hdl.handle.net/10630/17525
LA eng
NO Universidad de Málaga. Campus de Excelencia Internacional Andalucía Tech.
DS RIUMA. Repositorio Institucional de la Universidad de Málaga
RD 19 ene 2026