Implementación y análisis de algoritmos para intersección de conjuntos de intervalos evaluando secuencias genómicas

Abstract

La presente memoria presenta la implementación y análisis comparativos de dos algoritmos de intersección de conjuntos de intervalos, considerando la solución estado del arte desarrollada por Layer y Quinlan ella cual compararemos contra el algoritmo de búsqueda propuesto por Juan Pablo Castillo con una modificación realizada por el autor para que considere la intersección de múltiples conjuntos. Buscaremos calcular la eficiencia computacional de ambos algoritmos bajo una muestra de conjuntos de intervalos basada en el primer cromosoma de diferentes versiones de secuenciación de 3 especies de mamíferos, el ser humano, el chimpancé y el ratón. Estos datos fueron extraídos como archivos BEDs utilizando Table Browser, una potente herramienta del UCSC Genome Browser. Los análisis nos permitieron concluir como el algoritmo de búsqueda es una alternativa secuencial eficiente para la resolución del problema presentado, demostrando su eficacia con respecto al algoritmo de Layer y Quinlan y como este resulta de utilidad para el estudio comparativo de secuencias genómicas.