Introducción al Trabajo de Título
Entrar

Construcción eficiente de índices para texto comprimido con Relative Lempel-Ziv Memoria Ciencia e Ingeniería de datos Teoría de la computación

Profesor Guia
Sub Áreas Procesamiento masivo de datos, Análisis y diseño de algoritmos y estructuras de datos

Descripción


Una memoria reciente (Fernanda Sanchirico) creó una herramienta para convertir el formato VCF usado en la divulgación de bases de datos genómicas, al formato RLZ usado para indexar colecciones de texto repetitivas. Un escollo que quedó por resolver, y que sigue sin permitir usar la herramienta, es la necesidad de ordenar un subconjunto de n sufijos de un gran texto de largo N, usando espacio O(n) y en tiempo más bien cercano a n que a N. El texto está ya en formato RLZ, lo que dificulta un poco las soluciones. 

En esta memoria se busca superar este problema y completar la herramienta, que tendrá un valor bioinformático importante. Concretamente, se tienen dos técnicas, una básica y otra recientemente publicada, que permiten ordenar un subconjunto de sufijos. La memoria consiste en implementarlas, compararlas en este escenario, elegir la mejor, e incorporarla a la herramienta, para posteriormente terminar la interfaz de la herramienta para poder indexar y buscar en las colecciones sin descomprimirlas. Puede llevar a una publicación si el resultado es bueno.