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.

Modelo matemático SEIRD con vacunación para la simulación de la propagación de enfermedades infecciosas

In January 2016, Estrella Ruiz Anízar defended her M. Sc. Thesis at the Centro de Investigación en Computación (CIC) of Instituto Politécnico Nacional. La tesis de maestría de Estrella Ruiz trata de un modelo, un software y una simulación que estudia epidemias.

Resumen.
     La propagación de agentes infecciosos (virus, bacterias, hongos, vectores, etc.), que generan
enfermedades, es estudiada por distintas áreas de la ciencia (Medicina, Biología, Computación, Matemáticas) y sus disciplinas, las cuales trabajan en conjunto brindando diversas soluciones a este problema. Cada una de ellas, con diferentes técnicas de investigación, enfoques y estrategias abordan y estudian el problema del surgimiento de nuevas enfermedades, su comportamiento, su impacto en la sociedad, su evolución y su propagación.
      Con esto surgen subdisciplinas que brindan nuevos enfoques y soluciones, como por ejemplo la Epidemiología Matemática en la cual se desarrollan modelos matemáticos que analizan el comportamiento de distintos fenómenos complejos de la realidad, tal como lo es la propagación de agentes infecciosos. La computación desarrolla herramientas en las cuales se aplican estos modelos matemáticos, siendo un apoyo para el análisis y visualización del comportamiento de la enfermedad a través del tiempo, ya sea mediante gráficas y/o mapas geográficos. Es así que al trabajar en conjunto la Epidemiología Matemática y la Computación surge una disciplina llamada "Epidemiología Computacional" , que consiste en el uso de diversas técnicas matemáticas y computacionales utilizadas para modelar la propagación de epidemias y los efectos que tienen [20], as como la visualización, simulación, predicción y experimentación de este fen ómeno.
     La aplicación de estas técnicas ayudan a la toma de decisiones del personal correspondiente, en cuanto a la aplicación de medidas de prevención y control, como vacunas, aislamiento social o cualquier medida que ayude a disminuir el impacto de la enfermedad en la población.
      Existen diferentes motivos por los que se propagan las enfermedades infecciosas, como la facilidad de movilidad de las personas en diferentes medios de transporte, el comercio internacional (importación y exportación de productos), el incremento de la población, la naturaleza del agente infeccioso, las condiciones ambientales, geográficas entre otras. Las enfermedades infecciosas afectan a la sociedad en diferentes aspectos como el económico, las pérdidas humanas, socialmente, laboralmente, etc.
     Por todas estas razones, se encuentra la motivación de hacer una aportación en el aspecto computacional con el desarrollo de una herramienta que ayude al análisis y estudio de la propagación de una enfermedad infecciosa, basándose en la aplicación de un modelo matemático desarrollado. En este trabajo se hace una propuesta de un modelo matemático denominado "SEIRD" por sus siglas en inglés (Susceptible, Exposed, Infected, Recovered and Dead), en el cual se divide a la población total de individuos en compartimientos, es decir, que existen cinco clases de individuos: Susceptibles, Expuestos, Infectados, Recuperados, y Muertos a causa de la enfermedad.
     El caso de estudio que se consideró para aplicar el modelo SEIRD es el de la Influenza de México 2014, con el fin de observar cómo se comporta este virus en un año, en este modelo se considera el proceso de vacunación con el propósito de observar el impacto que tiene la aplicación de esta medida en la población. El modelo está basado en ecuaciones diferenciales, tomando en cuenta distintas variables y coeficientes. Finalmente, el modelo ha sido aplicado computacionalmente en un software desarrollado, llamado "SEIRD Simulator" en el cual se ingresan las condiciones iniciales del brote, se implementa el modelo SEIRD y se muestran los resultados de la simulación con y sin vacunación, en gráficas para su análisis y su validación.

Estrella Ruiz defendió exitosamente su tesis, ante este jurado. Enero 2016.

Detecting variable astronomical objects over time images. Detección de objetos variables en imágenes astronómicas a través del tiempo.

Ana Bertha Cruz Martínez has finished her M. Sc. Thesis (CIC, 2016. In Spanish). It can be dowloaded from here.
Abstract
     One interesting and unusual phenomenon that the astronomy studies,  is the explosion of a supernovae. It has a short duration, on the order of days. The study of supernovae has become important because they are objects that have a known light curve, specifically the Ia supernovae type. These can be used as benchmarks to measure the acceleration of the universe’s expansion. Measuring the redshift of a supernova we could known how fast away the universe expands.
     To accomplish this task we have developed different types of tools and use techniques for automated observation data acquisition that have produced large volumes of information.
     Astronomers have begun the process of extracting information with computational techniques as an alternative to the systematic analysis of the data. The main techniques used include the image and signal analysis.
      This work proposes a model that can process images, implementing some signal analysis techniques that are useful for the treatment of time series, which astronomers call light curves. Supervised classification module was also implemented for three classes: stars, variable objects and supernovae candidates, and additionally a sub-classification of the supernovae candidates in their different types of supernova: I y II.
     The model was built experimentally, trying different methods for each stage of the process, some of these methods are handled in astronomy separately to process data and make detection of supernovaes and other phenomena, the developed modules are:
     • Preprocessing: photometry and labeling images with PPP software (Picture Processing Package) developed by Phd. H. Yee carrying out this task was integrated.
     • The creation of the database was automated generating and using different SQL Statements and MySQL as manager of the database, organizing by regions and catalogs.
     • Construction of time series of each object in the database like a tuple.
     • Treatment of time series: clean background noise, interpolation supernovas filter to soften the light curve and standardization.
     • Supervised classification: constant objects, variable objects and candidates. Subclassification in supernova types using real examples from the literature.
     The software was developed with Python, testing each module with two regions of the database project CHASE Observatory from Cerro Tololo, Chile. Subsequently, the entire database is processed and its distribution of the objects was determined in three classes. This work presents the proposed model, the developed software, the final results of classification and the set of supernovae candidates, and their classification in their different types. 

Modelo de recomendación de problemas a realizar para competir en la Olimpiada de Informática

Rodrigo Rubén Santiago Nieves, in his M. Sc. thesis (2015) at CIC, writes a software that suggests (to a future competitor in the International Olympiad in Informatics) what problems to solve, so as to acquiere effective habilities.
Rodrigo Santiago Nieves, en su tesis de maestría en 2015 en el CIC, describe un software que recomienda los problemas de cómputo que un competidor debe resolver, para ejercitarse en la competencia (Olimpiada Internacional de Informática).

Resumen (parcial).

     La Olimpiada Internacional de Informática (IOI) es una de las olimpiadas de la ciencia organizadas por la UNESCO. En México la Olimpiada Mexicana de Informática (OMI) es un concurso que busca a los mejores programadores mexicanos de nivel preparatoria que representaran a México en la IOI. Para poder entrenar se han creado páginas web con un conjunto de problemas, estas páginas tienen la capacidad de evaluar y entregar resultados de forma automática. Los problemas en estas competencias son de naturaleza algorítmica, y cuentan con su descripción, la especificación de la entrada y salida, para evaluar los problemas se crean un conjunto de entradas y se evalúa la salida del programa del alumno, los programas son ejecutados con limitantes en tiempo y memoria. Estas páginas constantemente incrementan sus problemas haciendo cada vez más difícil tener un orden de ellos, por lo tanto cada vez que un alumno entra a estas páginas termina confundiéndose y sin identificar que problemas le pueden ayudar a practicar nuevas habilidades.

     El problema que pretende resolver la tesis es: Dado un conjunto de problemas , un conjunto de usuarios  y una matriz  donde se indica para cada usuario  que ha enviado una solución al problema , la puntuación . El problema es encontrar la mejor recomendación posible a cada usuario de aquellos problemas a resolver en un periodo de tiempo que le permitan mejorar su nivel de competencia.

     Debido a las limitantes de tiempo se optó por realizar una simulación, la cual modela al usuario por su motivación y habilidades. La motivación del usuario indica cuantos problemas está dispuesto a intentar en cada ciclo, las habilidades indican en nivel del usuario en cada uno de los temas que se evalúan. La motivación puede ser modificada positivamente cuando el usuario resuelve un problema y puede decrecer cuando el usuario no puede resolver un problema. La habilidad puede incrementar cuando el usuario resuelve un problema. 
     En base a los registros históricos de la página desde enero del 2009 a enero del 2014 se calculan las probabilidades de resolver un problema dado el nivel del usuario y la probabilidad de que su nivel sea de n o superior dado que resolvió un problema. Con esas probabilidades la simulación determina cuando el usuario resuelve un problema que intenta y en caso de resolverlo cuando sube su nivel de habilidad.

Abstract (part). 

     The International Olympiad in Informatics (IOI) is one of the five international Olympiads patronized by the UNESCO. For Mexico the Mexican Olympiad in Informatics (OMI) is a contest which select the best Mexican programmers from high school who are going to represent Mexico at the IOI. In order to prepare students for these contest web pages (Online-judges) had been developed which have a set of problems, theses web pages are able to assess problems and deliver results automatically. Problems in these contests are oriented to algorithms, they are composed of their description of the problem, input and output. Assessing problems is done using a set of test cases created previously, codes are executed with limits in memory and execution time, finally the output is evaluated to asses that follow the output description. Online judges constantly add new problems which has resulted in an increase in disorder on those problems creating confusion for students and disorientation on how to progress.

     The objective problem of this thesis is: Given a set of problems , a set of users  and the matrix  where for each user  who has sent a solution to the problem  there is a rating . Find the best recommendation possible for each users that in general increase the average motivation of each user and the average ability of users in a limited time.

     Because of limits in time and ethics we decided to create a simulation instead of test with real students to evaluate different recommender systems, these simulation model user through his motivation and abilities. User’s motivation address how many problems the user is going to try in each cycle. Abilities identify the level of the user in each topic to evaluate. Motivation depends on the problems solved or not solved in previous cycle, so it increase when the problems were solved correctly and decrease in the other case.

Sistema de visualización de la información de tópicos más importantes generados en medios sociales

En esta tesis de maestría en el CIC (2015), Mauricio Iván Guerrero Hernández analiza las noticias que aparecen en secciones de periódicos.  Mauricio Guerrero analyzes news in Spanish newspapers, in order to detect the most important topics in them.

Resumen (parcial).

     En este trabajo se da una propuesta de solución de detectar los tópicos más importantes e informar de su permanencia en el tiempo, para lo cual se utiliza una versión ya implementada del algoritmo no supervisado llamado Latent Dirichlet Allocation (LDA), que con modificaciones permite identificar un número determinado de tópicos a partir de un rango de días o un período de tiempo en una colección de publicaciones preparadas con el Procesamiento de Lenguaje Natural.

      Las colecciones de publicaciones se obtienen de suscripciones RSS de secciones de periódicos, así como de tweets que son publicados por periodistas destacados por su índice de seguidores o número de publicaciones, información que es almacenada en bases de datos, pero antes es tratada con procesos del área de Minería de Datos (extracción, transformación y carga).

     En el trabajo se define el concepto de tópico más importante,  basado en el mayor número de apariciones de un tópico en diferentes noticias de la colección. También se da una definición de similitud entre tópicos de diferentes períodos que ayuda a revisar su aparición de un tópico a lo largo de varios períodos de tiempo. Definiciones útiles para identificar y dar a conocer los tópicos a los usuarios que acceden a estos medios y dar un seguimiento de ellos, si son de su interés.

     También se construye un prototipo de software que utiliza las anteriores definiciones.

Abstract (part).

     In this paper it is given a proposal for a solution to detect the most important topics and report on their permanence in time, using an already deployed version of the model called Latent Dirichlet Allocation (LDA), which allows the identification of topics from a range of days and a period of time in a collection of publications in Spanish. 
     The publications are obtained from RSS subscriptions sections of newspapers, as well as tweets are published by journalists highlighted by its index of followers or number of publications, information that is stored in databases, but before it is treated with data  mining processes (extraction, transformation and loading). 
     The most important topic concept is defined, based on the highest number of occurrences of a news topic in different collection. It also uses a definition of similarity between different periods.

      A software prototype has been built, that uses the above definitions.