Búsqueda de patrones en cadenas de ADN. Search for patterns in ADN chains.

In January 2016, Luis Ortiz Chan successfully defended his M. Sc. thesis at CIC. Luis Ortiz presentó una interesante tesis sobre búsqueda de patrones en cadenas de bases que forman el ADN.

Click here to obtain his thesis. Para obtener su tesis, pulse aquí.
Abstract.
     One of the classic problems in bioinformatics is the search of useful frequent patterns with a well-defined task among DNA sequences.
     In this work an alternative algorithm called KTreeMotif is developed for motif finding in DNA sequences, with similar performance to the most used algorithms nowadays such as Gibbs Sampler, Motif Sampler, MEME and SP-Star. KTreeMotif seeks to exploit the methodologies and advantages of a set of these algorithms in order to validate the outcome of other means.
     KTreeMotif, additionally, implements a new data structure to store and look through the substrings in a more systematic and fast way than brute force simple iteration that is mostly used; also, a simplification of the distance function between a PWM and a sequence without losing information reaching the same result was added; and finally an improvement in accuracy of the distance function between two sequences for the specific case of frequent pattern searching was included. All these innovations are easily integrable into other algorithms that tackle this problem.
     In order to make the performance tests on KTreeMotif it was necessary to implement the algorithms against which it was compared. Using the JASPAR database that provides the correct motifs, the performance tests were run with the implemented algorithms and the proposed algorithm to get their motifs results, and to compare against the correct ones.
     The proposed algorithm lacks a good response time but the aim of the proposal was to offer one more alternative to the solution of the problem, validating the results obtained by different algorithms with this proposal's, so that their results can be more reliably believed to be the correct ones.
     Besides the analysis and comparison of the methodologies that lead the motif finding algorithms, it was found that the main challenge on the accuracy is in the objective function that does not represent in a right way a pattern motif, and scores wrong patterns as better motifs. We conclude that with a function that describe better the motif it would be possible to increase the accuracy of any algorithm.

Adolfo Guzmán y  el M.enC. Luis Ortiz Chan

 
Resumen.
    Uno de los problemas clásicos en la bioinformática es la bísqueda de patrones frecuentes con una tarea bien identificada en las secuencias de ADN.
    En este trabajo se desarrolla un algoritmo alternativo llamado KTreeMotif para la búsqueda de motifs en secuencias de ADN, con rendimiento similar a los  algoritmos más usados hoy en día como son el Gibbs Sampler, el Motif Sampler, el MEME y el SP-Star. KTreeMotif busca aprovechar las metodologías y cualidades de un conjunto de estos algoritmos con la finalidad de reafirmar los resultados obtenidos por otros medios.
    KTreeMotif además, implementa una nueva estructura de datos para almacenar y recorrer las subcadenas de una manera más sistemática y rápida que el recorrido secuencial que suele usarse; también se hace una simplificación de la función de distancia entre una PWM y una secuencia sin perder información logrando el mismo resultado, y finalmente una mejora en exactitud de la función de distancia entre dos secuencias para el caso específico de la búsqueda de patrones frecuentes. Todas estas novedades son integrables a los otros algoritmos que atacan este problema.
    Para llevar a cabo las pruebas de evaluación de KTreeMotif fue necesario implementar los algoritmos contra los que se realizó su comparación; y utilizando la base de datos JASPAR que contiene los resultados correctos, estos fueron buscados por los algoritmos implementados y de igual manera por el algoritmo propuesto.
      El algoritmo adolesce en el tiempo de respuesta pero el objetivo de la propuesta es ofrecer una alternativa más a la solución del problema, al corroborar que los resultados que fueron obtenidos iguales por distintos algoritmos y por esta propuesta son más fiables de ser los correctos.
     Además del análisis y comparación de las metodologías que siguen los algoritmos de búsqueda de motifs, se encontró que el principal problema con la precisión está en la función objetivo que no representa de manera correcta un patrón motif y califica como mejores motifs a patrones diferentes al correcto. De esto se concluye que con una mejor función que modele al motif sería posible aumentar la precisión de cualquier algoritmo.