Mañana, JUEVES, 24 DE ABRIL, el sistema se apagará debido a tareas habituales de mantenimiento a partir de las 9 de la mañana. Lamentamos las molestias.
Implementación y análisis de algoritmos de alineación para datos de Next Generation Sequencing (NGS)
Author
Giménez Llorente, DanielEntity
UAM. Departamento de Ingeniería InformáticaDate
2016-06Subjects
InformáticaEsta obra está bajo una licencia de Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional.
Abstract
El coste del proceso de secuenciación de los genomas de los seres vivos, se ha reducido en
gran cantidad en los últimos diez años debido a la aplicación de nuevas técnicas de secuenciación
denominadas Next Generation Sequencing (NGS). Esta situación ha propiciado la aparición de
muchos alineadores que nos permiten, dada una serie de secuencias provenientes de la secuenciación
NGS, conseguir hallar la posición en el genoma del que proceden usando un genoma de
referencia. Sin embargo es difícil escoger cuál es el alineador que mejor se puede adaptar a cada
problema, dada la dificultad de encontrar comparaciones justas entre alineadores en términos
de efectividad en la alineación y coste computacional. Además, dentro de un mismo alineador el
correcto ajuste de los metaparámetros que definen cada uno de los alineadores es otro problema
al que también se enfrentan normalmente los bioinformáticos. Estas dificultades se ven acentuadas
por el hecho de que estos alineadores son comúnmente usados como cajas negras dada su
complejidad y la dificultad de encontrar descripciones y análisis detallados de los mismos.
El objetivo de este TFG es el análisis teórico e implementación de tres alineadores para su
posterior comparación, determinando en qué casos es mejor optar por la utilización de unos
u otros. Adicionalmente, se proporciona un análisis de la influencia de sus metaparámetros
en el rendimiento de cada alineador. Se han escogido Bowtie, BWA y BWT-SW, para cubrir
tanto alineadores de secuencias cortas como largas, así como alineadores únicamente tolerantes a
mutaciones y alineadores tolerantes a mutaciones y huecos. Estos alineadores usan una estructura
común, FM-Index, que les permite realizar búsquedas en el genoma de referencia de forma
óptima a través de la transformada de Burrows-Wheeler y propiedades. Este TFG ofrece una
descripción detallada del funcionamiento de cada uno de los algoritmos, que ha sido posible tras
el análisis de cada uno de los artículos científicos donde se encuentran definidos los mismos.
A continuación, tanto los alineadores como el FM-Index se han implementado en C++, y su
correcto funcionamiento se ha verificado mediante una serie de pruebas unitarias de caja blanca
y caja negra.
Una vez implementados, se usó el programa ART para la simulación de un generador de
secuencias NGS. Este programa recibe como parámetros la tecnología a simular y otros valores
que permiten controlar la longitud de la secuencia de salida y las probabilidades de mutaciones
y huecos. Se ha comparado el comportamiento de los tres alineadores para diferentes valores de
estos parámetros en términos de tiempos de ejecución y tasas de acierto, haciendo variar a su
vez los metaparámetros de cada alineador.
Las contribuciones derivadas de este TFG son un estudio detallado del funcionamiento de
algunos de los algoritmos de alineación más utilizados, que pretende completar la literatura
existente, una implementación sencilla de los mismos que facilita su mejor comprensión y comparación,
y un análisis cuantitativo y comparativo de estos alineadores que permite determinar
la naturaleza de los problemas de alineación para los cuales cada uno de ellos es más adecuado. The cost of sequencing a living being’s genome has been greatly reduced due to the advent
of Next Generation Secuencing (NGS) techniques. This situation has led to the apparition of
many new aligners that can find the position of a given NGS sequence in a reference genome.
However, it is difficult to choose the aligner that best adapts to a problem given the shortage of
fair comparisons between aligners in terms of alignment effectiveness and computational cost.
Besides, another problem commonly faced by bioinformaticians is the correct adjustment of
aligner’s metaparameters. These difficulties are even greater considering that these aligners are
commonly used as black-boxes due to their complexity and the lack of a detailed description
and analysis of them.
The objective of this Masters Thesis is to provide a theoretical analysis and implementation
of three aligners that will serve to compare them, showing which is the best algorithm for each
type of NGS sequencing problem. Additionally, this work includes an analysis to determine
the influence of aligners’ metaparameters in their performance. In order to cover both long
and short sequence aligners as well as aligners considering either only mutations (mismatches)
or both mutations and gaps, three different aligners, namely Bowtie, BWA and BWT-SW,
have been selected for the analysis. These aligners have a common structure, the FM-Index,
that allows optimal searching in the reference genome with low memory consumption by using
the Burrows-Wheeler transform and its properties. This Masters Thesis offers a description of
the hidden details of every algorithm, which has been possible through the thorough study of
scientific papers where these algorithms are proposed. Both the FM-Index and the aligners were
implemented in C++, and their proper functioning was verified by black and white box unit
testing.
Once the aligners were implemented, ART software was used to simulate NGS sequences.
This software receives as parameters the NGS technology to simulate and other values to control
sequences’ length, number of mismatches, and gap probability. The behaviour of these three
aligners for different values of these parameters has been compared in terms of execution time
and hit rate, varying every aligner’s metaparameters as well.
The outcomes of this Masters Thesis are a detailed study of some of the most used alignment
algorithms based on the FM-Index, which intends to complement existing literature; a simple
implementation of these aligners, which favors their comprehension and comparison; and a quantitative
comparative analysis, which allows us to conclude when each aligner is more suitable
than others for an specific sequencing problem.
Files in this item
Google Scholar:Giménez Llorente, Daniel
This item appears in the following Collection(s)
Except where otherwise noted, this item's license is described as https://creativecommons.org/licenses/by-nc-nd/4.0/
Related items
Showing items related by title, author, creator and subject.
-
Análisis de expresión diferencial para datos de Next Generation Sequencing (NGS) con múltiples condiciones experimentales
Giménez Llorente, Daniel
2017-09 -
Análisis e implementación de diferentes medidas de similitud para un algoritmo global de selección de variables
Dorado Alfaro, Sara
2017-05 -
Implementación y evaluación de algoritmos de cálculo de ruta y selección de longitud de onda para un PCE multicapa
Martínez de Tejada Ayuso, Sergio
2013