Criterios de selección basados en sketches para el problema de similitud genómica.
No Thumbnail Available
Date
2024
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Universidad de Concepción
Abstract
El cómputo de similitud genómica es importante para distintas aplicaciones como clustering y clasificación taxonómica en área de genómica y metagenómica. Una de las métricas de similitud más utilizadas es el coeficiente de Jaccard. Debido al alto costo computacional de métodos tradicionales, la comunidad científica ha propuesto métodos de estimación basados en estructuras de datos probabilísticas llamadas sketches. Sin embargo, estos métodos aún pueden requerir un alto tiempo de cómputo para resolver el problema de encontrar todos los pares de secuencias genómicas cuya similitud supere un umbral. Una alternativa para enfrentar esta dificultad es utilizar algoritmos que permitan decidir, con alta probabilidad, si un par no es suficientemente similar, permitiendo reducir el tiempo de cómputo. A este tipo de algoritmos es a al que llamamos criterio de selección, ya que clasifica pares entre similares y no similares. Este trabajo propone dos criterios de selección basados en propiedades de la confianza en la estimación de sketches de cardinalidad y uno basado en el sketch Super MinHash con LSH. Los criterios son implementados y validados usando la colección de genomas RefSeq. Los resultados obtenidos muestran una alta sensibilidad y especificidad de los criterios propuestos, mejorando el tiempo de cómputo entre 2 y 10 veces usando cerca del 1% de espacio adicional.
Description
Tesis presentada para optar al grado de Magister en Ciencias de la Computación
Keywords
Bioinformática, Genómica, Procesamiento de datos