Árboles de sufijos comprimidos prácticos
Autores: Abeliuk, Andrés; Cánovas, Rodrigo; Navarro, Gonzalo
Idioma: Inglés
Editor: MDPI
Año: 2013
Acceso abierto
Artículo científico
2013
Árboles de sufijos comprimidos prácticos
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
árbol de sufijos
Bioinformática
Representaciones comprimidas
Compensaciones espacio-temporales
índice modificado
Colecciones repetitivas
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 36
Citaciones: Sin citaciones
El árbol de sufijos es una estructura de datos extremadamente importante en bioinformática. Las implementaciones clásicas requieren mucho espacio, lo que las hace inútiles para manejar grandes colecciones de secuencias. Investigaciones recientes han obtenido varias representaciones comprimidas para árboles de sufijos, con diferentes compensaciones de espacio y tiempo. En este documento mostramos cómo el uso de produce nuevas representaciones que logran compensaciones prácticas entre espacio y tiempo. Además, demostramos cómo esos árboles pueden modificarse para indexar colecciones altamente repetitivas, obteniendo la primera representación comprimida de árbol de sufijos que se adapta eficazmente a ese escenario.
Descripción
El árbol de sufijos es una estructura de datos extremadamente importante en bioinformática. Las implementaciones clásicas requieren mucho espacio, lo que las hace inútiles para manejar grandes colecciones de secuencias. Investigaciones recientes han obtenido varias representaciones comprimidas para árboles de sufijos, con diferentes compensaciones de espacio y tiempo. En este documento mostramos cómo el uso de produce nuevas representaciones que logran compensaciones prácticas entre espacio y tiempo. Además, demostramos cómo esos árboles pueden modificarse para indexar colecciones altamente repetitivas, obteniendo la primera representación comprimida de árbol de sufijos que se adapta eficazmente a ese escenario.