Por favor, use este identificador para citar o enlazar este ítem:
http://cicese.repositorioinstitucional.mx/jspui/handle/1007/461| Optimización del conjunto de mosaicos en el auto-ensamblado de ADN de patrones en 2D Optimization tile set in DNA self-assembly of 2D patterns | |
| FELIPE LEZA ALVAREZ | |
| ISRAEL MARCK MARTINEZ PEREZ | |
| Acceso Abierto | |
| Atribución | |
| El problema de sintetizar un conjunto de mosaicos para el auto-ensamblado de patrones (PATS, por sus si-
glas en inglés), consiste en encontrar un conjunto mínimo de tipos de mosaicos para que auto-ensamblen un
patrón P de dos dimensiones previamente definido. El auto-ensamblado se realiza con el modelo abstracto
de ensamblado de mosaicos, cuyas unidades fundamentales son mosaicos cuadrados que representan una
molécula de ADN con extremos pegajosos. Este modelo provee el comportamiento combinatorio del auto-
ensamblado de ADN y puede utilizarse como modelo de cómputo y como método de construcción para
nanoestructuras de ADN. En este último, el objetivo es diseñar secuencias de ADN que automáticamente
ensamblen una estructura deseada. El problema PATS pertenece al conjunto de problemas NP-difícil. Los
métodos propuestos en el estado del arte abordan el problema aplicando diferentes heurísticas. Sin em-
bargo, estos métodos no obtienen los conjuntos óptimos para todos los casos de prueba. En este trabajo
de investigación se propone un algoritmo de recocido simulado para resolver el problema. Se utilizan dos
tipos de representación: con grafos y matricial. El diseño incluye operaciones para generar el vecindario de
soluciones, así como la utilización de tres perfiles de enfriamiento. Los experimentos realizados con los pa-
trones de prueba obtienen los conjuntos óptimos para patrones pequeños (menores a 8 × 8), aunque para
patrones de mayor tamaño solamente se logra superar a los métodos voraces del estado del arte, pero no
así a los métodos basados en procesamiento paralelo. The Patterned self-Assembly Tile set Synthesis (PATS) problem consists in finding a minimal set of unit squa- re tiles that self-assemble a predefined two-dimensional pattern. DNA self-assembly is performed by using the abstract Tile Assembly Model (aTAM), where a tile represents a DNA molecule with four sticky ends protruding from it. This model can be viewed from two different angles: as a computational model, on one hand, and as a construction method for nanoscale structures, on the other. In the latter case, the goal is to design DNA sequences that automatically assemble into a target structure. However, the task of finding a minimum-size tile set is known to be NP-hard. To date, four different approaches have been proposed for the resolution of this problem. In this thesis, a simulated annealing algorithm to solve the PATS problem is presented. In total, five neighborhood operations were developed on a matrix structure and three cooling schedules were considered. Computational experiments were performed on 14 patterns to find an optimal solution. Experimental results show that simulated annealing algorithm performs very well when conside- ring small-size instances. Nevertheless, for instances greater than 8 × 8, obtained results cannot improve those of the state of art. | |
| 2016 | |
| Tesis de maestría | |
| Español | |
| Leza Álvarez, F. 2016. Optimización del conjunto de mosaicos en el auto-ensamblado de ADN de patrones en 2D. Tesis de Maestría en Ciencias. Centro de Investigación Científica y de Educación Superior de Ensenada, Baja California. 117 pp. | |
| CIENCIAS TECNOLÓGICAS | |
| Aparece en las colecciones: | Tesis - Ciencias de la Computación |
Cargar archivos:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| Tesis_Felipe_Leza.pdf | Versión completa de la tesis | 14.71 MB | Adobe PDF | Visualizar/Abrir |