Por favor, use este identificador para citar o enlazar este ítem:
http://cicese.repositorioinstitucional.mx/jspui/handle/1007/2015| Un algoritmo genético para el ensamble de secuencias de ADN A genetic algorithm for DNA sequence assembly | |
| Milton Rodríguez Zambrano | |
| CARLOS ALBERTO BRIZUELA RODRIGUEZ | |
| Acceso Abierto | |
| Atribución | |
| Algoritmos genéticos | |
| La secuenciación del genoma de un organismo permite el estudio y entendimiento de éste, para el caso de parásitos o virus, podría lograrse el desarrollo de nuevos medicamentos y vacunas. La secuenciación permite también el estudio de la evolución de las especies, mediante la identificación de variaciones genéticas. Las técnicas de secuenciación que se aplican dependendel tamaño de la cadena de ADN que se dese secuencias. Para el caso de genomasgrandes, la técnica más utilizada se denomina Shotgun, la cual comprende variasetapas, la última de ellas se conoce como Ensamble de Secuencias. El problema de ensamble de secuencias de ADN, en su modelo más sencillo, pertenece a la clase NP-Difícil, lo que significa que no se conoce método alguno que proporciones una solución óptima en tiempo polinomial. Entre las estrategias propuestas para este problema se encuentran principalmente las estrategias voraces y los algoritmos genéticos. En este trabajo se propone un algoritmo genético, para un modelo de este problema que consiste en encontrar una ruta con características específicas en un grafo dirigido completo. Este modelo considera errores de bases y la orientación desconocida de los segmentos. El algoritmo propuesto se basa en un algoritmo genético básico, al cual se le agrega una fase de eliminación de segmentos y ajuste de individuos. Se propone también una función de aptitud que intenta favorecer la generación de soluciones con la menor cantidad posible de contigs, y consecuentemente contigs con la mayor longitud posible. Se comparan los resultados del algoritmo genético propuesto contra los de un algoritmo genético básico, notándose claramente el mejor desempeño del primero. Finalmente, se comparan los resultados contra los de un algoritmo voraz disponible públicamente, obteniendo resultados comparables e incluso a favor del algoritmo genético para casos con cierta tasa de error de base. Los resultados son independientes del tamaño de los fragmentos a ensamblar y de la función de aptitud utilizada. The sequencingof an organism genome allows us to study and understand it, knowing the genomeof parasites and viruses help us to develop new medicines and vaccines. The sequencingalso allows us to study the evolution of the species through the identificationof genetic variations. The selection of a sequencing technique depends on thesize of the target DNA chain. For large genomes, the most used technique isknows as Shotgun, which includes several stages, and the last on is denominatedAssembling. The DNA assembling problem, under its simplest model, belongs tothe NP-Hard class of problems, which implies that a method providing the optimalsolution in polynomial time is unknown. Among the proposed strategies to solvethis problem the greedy strategies and the genetic algorithms are the mostcommon. In this work we propose a genetic algorithm to solve where theobjective is to find a path with specific characteristics in a completedigraph. This model considers the base call errors and the segments unknownorientation. The proposed algorithm is based on a simple genetic algorithm,where we propose a segment elimination and individuals adjustment phase. We alsopropose a fitness function, which is intended to help on generating solutionswith the minimum possible amount of contigs and, consequently, contigs with themaximum possible size.The results of the proposed genetic algorithm outperformthose obtained by a basic genetic algorithm. Finally, the experimental resultsshow that the solution quality obtained by our proposed algorithm is comparablewith the one produced by a greedy algorithm and, in some cases our algorithmperforms better. These results are independent of the fragments to assemblesize and of the fitness function. | |
| CICESE | |
| 2005 | |
| Tesis de maestría | |
| Español | |
| Rodríguez Zambrano,M.2005.Un algoritmo genético para el ensamble de secuencias de ADN.Tesis de Maestría en Ciencias. Centro de Investigación Científica y de Educación Superior de Ensenada, Baja California.x, 99 pp. | |
| CIENCIA DE LOS ORDENADORES | |
| Aparece en las colecciones: | Tesis - Ciencias de la Computación |
Cargar archivos:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| 167341.pdf | Versión completa de la tesis | 1.62 MB | Adobe PDF | Visualizar/Abrir |