In this work we present a mapper, an algorithm to find short DNA sequences in large reference texts. Our algorithm uses the standard seed-and-extend approach, utilized by most modern mappers, combined with a novel genome annotation called neighborhood annotation. The neighborhood annotation is a data structure that contains information of similarity between sequences of the same reference. Based on this annotation, we build a statistical model to aid the processes of seeding and mapping quality estimation. Overall, our algorithm achieves higher sensitivity and more accurate estimation of mapping reliability with simulated Illumina reads, at the same speed compared to the state-of-the art algorithms. The C source code of the algorithm implementation is available at http://github.com/ezorita/mapper.

En este proyecto presentamos un algoritmo de mapping. Los mappers son algoritmos utilizados para encontrar secuencias cortas de ADN en textos de referencia mucho más largos. Nuestro algoritmo utiliza la técnica estándar de seed-and-extend, utilizada por la mayoria de mappers actuales, combinada con una nueva anotación del genoma: el neighborhood annotation. Esta anotación es una estructura de datos que almacena información sobre las similitudes entre las secuencias del texto de referencia. Basandonos en esta estructura, hemos diseñado un modelo estadístico que utilizamos para favorecer los procesos de seeding y de estimación de la calidad de mapping. Finalmente, hemos implementado y testeado el rendimiento de nuestro algoritmo en secuencias simuladas de Illumina. Los resultados obtenidos muestran una mejor sensitividad y estimaciones más precisas de la fiabilidad de mapping, a la misma velocidad que los mappers del estado del arte. El código fuente de la implementación en C está disponible en open-source en http://github.com/ezorita/mapper.

En aquest projecte hi presentem un algoritme de mapping. Els mappers són algoritmes que s'utilitzen per trobar seqüències curtes d'ADN en textos de referència molt grans. El nostre algoritme utilitza la tècnica estàndard de seed-and-extend, utilitzada per la majoria de mappers actuals, combinada amb una nova anotació del genoma que hem anomenat neighborhood annotation. Aquesta anotació consisteix en una estructura de dades que emmagatzema informació sobre les similaritats entre les seqüències del text de referència. Basant-nos en aquesta estructura, hem dissenyat un model estadístic que utilitzem per assistir els processos de seeding i d'estimació de la qualitat de mapping. Finalment, hem implementat i mesurat el rendiment del nostre algoritme en seqüenciacions simulades d'Illumina. Els resultats obtinguts determinen millor sensitivitat i estimacions més acurades de la fiabilitat de mapping, a la mateixa velocitat que els mappers de l'estat de l'art. El codi font de la implementació en C està disponible en open-source al web http://github.com/ezorita/mapper.