Registro:
| Documento: | Tesis de Grado |
| Título: | Arreglos de sufijos para alineamiento de secuencias de ADN con memoria acotada |
| Título alternativo: | Suffix arrays for DNA sequence alignment with limited memory |
| Autor: | Deymonnaz, Alejandro Martín |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Publicación en la web: | 2025-06-12 |
| Fecha de defensa: | 2012 |
| Fecha en portada: | Marzo 2012 |
| Grado Obtenido: | Grado |
| Título Obtenido: | Licenciado en Ciencias de la Computación |
| Departamento Docente: | Departamento de Computación |
| Director: | Becher, Veronica Andrea |
| Jurado: | Marenco, Javier Leonardo; Urtasun, Martín Javier |
| Idioma: | Español |
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/seminario_nCOM000743_Deymonnaz |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000743_Deymonnaz.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/seminario/document/seminario_nCOM000743_Deymonnaz |
| Ubicación: | Dep.COM 000743 |
| Derechos de Acceso: | Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Deymonnaz, Alejandro Martín. (2012). Arreglos de sufijos para alineamiento de secuencias de ADN con memoria acotada. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/seminario_nCOM000743_Deymonnaz |
Resumen:
El secuenciamiento de ADN sufrió una reciente revolución a raíz de las llamadas tecnologías de Secuenciamiento de Nueva Generación o Next Generation Sequencing en inglés, que permiten secuenciar en la actualidad más de mil millones de nucleótidos por día en una sola máquina con un costo comparativamente bajo. La clave de esta eficiencia en el secuenciamiento radica en el alto paralelismo, secuenciando millones de cadenas cortas de ADN en una sola pasada. El problema del mapeo de reads consiste en ubicar o alinear dentro de un genoma de referencia previamente secuenciado las millones de cadenas cortas de ADN (reads) para luego ensamblarlas en un nuevo genoma. Por el tamaño y cantidad de estos datos, que se espera siga creciendo con los avances de esta tecnología, el problema del mapeo de reads ofrece un desafío computacional. Entre las numerosas herramientas de software que surgieron para resolver este problema, las más eficientes se basan en una estructura de indexación completa del texto. La indexación de texto por medio del arreglo de sufijos tiene ya 20 años y está tendiendo a ser reemplazada por los índices basados en arreglos de sufijos comprimidos o sobre la transformación de Burrows y Wheeler, que requieren menos espacio en memoria. No obstante, estos nuevos índices son más lentos. En este trabajo proponemos un método para realizar un compromiso entre espacio y tiempo de ejecución a fin de poder utilizar un arreglo de sufijos en un contexto de memoria acotada aprovechando su eficiencia en la búsqueda aplicado al problema de mapeo de reads. Realizamos un estudio comparativo aplicando este método tanto a herramientas desarrolladas por nosotros como a herramientas existentes y concluimos las condiciones sobre las cuales es conveniente aplicarlo.
Abstract:
DNA sequencing suffered a recent revolution as a result of the so-called Next Generation Sequencing technologies, now allowing to sequence more than a billion nucleotides per day in a single machine with considerable low cost. The key to this efficiency relies on the high sequencing parallelism, yielding more than a million short DNA reads in a single run. The computational problem known as the mapping problem requires to locate within a previously sequenced reference genome millions of short DNA reads in order to assemble them as a new genome. Due to the size and number of the input data, and the high speed at which it is generated, the mapping problem is indeed a computational challenge. Among the many software tools that have emerged to solve it, the most efficient in the trade off of memory and time consumption are based on a full-text index structure. Text indexing using suffix arrays is already 20 years old and it is tending to be replaced by indices based on compressed suffix arrays or the Burrows-Wheeler transform, which require less memory space. However, these newer indexing structures are slower to operate. In this work we propose a method to maximize the efficiency in the compromise between space and time when using a suffix array structure to solve the mapping problem in a context of limited memory. Using this method we performed a comparative study of how different memory sizes and data contexts impact on the mostly used existing tools as well as on tools developed by us based on known algorithms. As a conclusion we reveal the conditions that maximize efficiency in each case.
Citación:
---------- APA ----------
Deymonnaz, Alejandro Martín. (2012). Arreglos de sufijos para alineamiento de secuencias de ADN con memoria acotada. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000743_Deymonnaz
---------- CHICAGO ----------
Deymonnaz, Alejandro Martín. "Arreglos de sufijos para alineamiento de secuencias de ADN con memoria acotada". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2012.https://hdl.handle.net/20.500.12110/seminario_nCOM000743_Deymonnaz
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000743_Deymonnaz.pdf
Distrubución geográfica
