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