Variantes de la concatenación en computación con ADN

Resumen

Las principales aportaciones de esta Tesis Doctoral a la computación con ADN y en general, a las ciencias de la computación, se pueden clasificar en dos áreas básicas: una práctica o algorítmica y otra teórica o de modelización de operaciones sobre palabras y lenguajes. Más en detalle, las aportaciones prácticas y teóricas se pueden describir como sigue. Aportaciones prácticas. Se han diseñado bio-algoritmos evolutivos para el Problema del Camino de Hamilton dirigido y se han ideado nuevos esquemas de codificación de información en hebras de ADN más versátiles que los previos y que permiten implementar estrategias evolutivas. Estas primeras aportaciones están motivadas por la limitación que presentan los esquemas de "fuerza bruta" existentes en la computación con ADN. Al intentar resolver instancias grandes de problemas complejos no se dispone del número suficiente de moléculas de ADN para seguir un esquema de fuerza bruta. Es necesario recurrir a técnicas de programación alternativas: algoritmos aproximados, heurísticas, programación dinámica, programación evolutiva. Se ha elegido esta última alternativa y se ha conseguido diseñar nuevos bio-algoritmos basados en nuevos esquemas de codificación que permiten este tipo de computación evolutiva. La evolución in vitro de moléculas (técnica de la química combinatoria) y la programación evolutiva han sido la fuente de inspiración para el diseño de estas estrategias de cómputo con ADN evolutivas. El algoritmo evolutivo para el Problema del Camino de Hamilton dirigido es el primer algoritmo completamente evolutivo propuesto en el área de la computación con ADN. En concreto, la evolución de secuencias se consigue "fragmentando y reensamblando" subcaminos a lo largo del grafo en un proceso cíclico. Se trata, por tanto, de un algoritmo iterativo de fragmentación y recombinación de hebras de ADN que codifican subcaminos a lo largo de un grafo. Los esquemas de codificación denominados I y II permiten "fragmentar y reensamblar" las soluciones de un problema siguiendo un esquema iterativo. Estos esquemas de codificación permiten codificar no sólo caminos a lo largo de un grafo sino que permiten también construir palabras binarias y simular las transiciones de un autómata finito. Estas aportaciones permiten definir el primer modelo de computación con ADN evolutiva. APORTACIONES TEÓRICAS: Modelización y estudio de la capacidad generativa de una operación denominada concatenación condicional o restringida empleada en un algoritmo evolutivo para el Problema del Camino de Hamilton presentado en la memoria. La concatenación de dos hebras de ADN es una operación análoga a la concatenación de dos palabras en la Teoría de lenguajes formales. Ahora bien, si dos cadenas de ADN sólo se pueden unir (ensamblar o concatenar) si el sufijo de una de ellas y el prefijo de la otra pertenecen a un conjunto especial, se tiene una operación de concatenación restringida similar a la restricción impuesta por unos contextos especiales. La concatenación condicional sufijo-prefijo o cola-cabeza se manifiesta también en la formación de las moléculas de colágeno que tienden a concatenarse o ensamblarse siguiendo la restricción de que la cola de una hebra de colágeno sólo se concatena con la cabeza de otra hebra de colágeno. Al añadir este tipo de restricción a la concatenación usual de lenguajes formales se obtienen resultados muy interesantes. En principio, las restricciones a la hora de aplicar la operación de concatenación no aportan gran poder computacional. Las secuencias o palabras que se obtienen tienen una complejidad pobre. Es más, las restricciones en los contextos del tipo prefijo-sufijo, cola-cabeza, etc., a la hora de concatenar dos secuencias no aumenta en nada la complejidad de las palabras obtenidas. Si se partía de palabras de un lenguaje regular, se sigue obteniendo un lenguaje regular. Si se partía de un lenguaje independiente del contexto, se sigue obteniendo un lenguaje independiente del contexto. En general, las familias de lenguajes son cerradas bajo la operación de concatenación condicional. Esta pobreza generativa se mantiene incluso cuando se itera la operación de concatenación condicional (análoga a la operación de Kleene pero ahora restringida). Estos son los "malos" resultados. Los "buenos" aparecen cuando se consideran gramáticas y reglas de reescritura. Ahora, el poder generativo surge al establecer la siguiente analogía. Una regla de reescritura A- w en la que un símbolo no terminal A se sustituye por una secuencia w se puede considerar como un doble concatenación. Si se parte de una forma sentencial genérica uAv, aplicar la regla A- w supone concatenar u con w, y el resultado uw, concatenarlo con v para obtener uwv. Si estas dos concatenaciones se consideran condicionales (es decir, sólo se podrán aplicar si se cumplen ciertas condiciones del tipo prefijo-sufijo en los contextos) la capacidad generativa de las gramáticas aumenta estrictamente. En concreto, la concatenación sufijo-prefijo aumenta la capacidad generativa de las gramáticas independientes del contexto a su máximo nivel: se convierten en gramáticas capaces de generar cualquier lenguaje de tipo 0 o recursivamente enumerable. En consecuencia, una operación surgida de la concatenación de hebras de ADN (la empleada en el algoritmo evolutivo para el Problema del Camino de Hamilton), que se ha denominado concatenación condicional, permite obtener modelos de cómputo en concreto, gramáticas universales