SISTEMA ELECTRóNICO DE EMULACIóN DE LA CADENA DE LA ESTRUCTURA DE "ADN" DE UN CROMOSOMA

OBJETO DE LA INVENCIóN

La invención que nos ocupa, tal y como lo expresa el enunciado de esta memoria descriptiva, tiene por objeto proporcionar un sistema electrónico de emulación de la cadena de la estructura de "ADN", para permitir, resolver problemas de computación con "ADN" , que en el caso de la invención, es "ADN" inorgánico ya que se materializa mediante circuitos electrónicos y no mediante "ADN" orgánico, tal y como se realiza convencionalmente, y así aprovechar las características de la naturaleza orgánica del "ADN" a partir de un "ADN" inorgánico.

La invención consiste en un sistema hardware que proporciona una estructura electrónica del "ADN" que permite resolver problemas de trayectorias, redes y flujos, los cuales son utilizados en los cálculos de trayectorias de los sistemas "GPS" (Sistema de Posicionamiento Global) , cálculo de rutas en navegadores terrestres, marítimos o aéreos, y también en problemas de control industrial en procesos de producción u optimización de los flujos de trabajo industriales.

En general la invención es aplicable en la resolución de cualquier problema que pueda ser representado mediante grafos que se asocian a la cadena de la estructura de ^λλ ADN" , tal y como será descrito más adelante .

ANTECEDENTES DE LA INVENCIóN

La matemáticas y la computación se unen de la mano, en un área de la ciencia que es conocida como la teoría de grafos. Los grafos son colecciones de elementos que se denominan nodos o vértices, los cuales están unidos por aristas o arcos, que a su vez, estas aristas pueden tener dirección u orientación designada. Uno de los primeros pioneros dentro de este campo, fue Leonard Euler, quien en 1736 se planteó un problema que es conocido como el

problema de los puentes de Kónigsberg, que era una ciudad prusiana que poseía siete puentes. Euler suscitó la cuestión, de si era posible recorrer toda la ciudad cruzando cada uno de los puentes, una y sólo una vez. En una representación esquemática de la ciudad se puede observar que los puentes unen cuatro porciones de tierra, por lo que la búsqueda de prueba y error, no conducen a ningún resultado, por ese motivo, si se puede representar este problema, mediante un grafo, se podrían aplicar técnicas, métodos y algoritmos de la teoría de grafos para encontrar la solución. A raíz de este problema se dio el primer paso hacia la teoría de grafos, la cual ha evolucionado a lo largo del tiempo y, donde existen numerosos grupos de investigación trabajando en áreas o campos de esta disciplina. Unos años más tarde, el matemático, físico, y astrónomo irlandés, William Rowan Hamilton planteó uno de los problemas más complejos que existen en la teoría de grafos, el problema de los caminos hamiltonianos o el problema del viajante que consiste en tener un camino o grafo en el que se visita cada vértice exactamente una vez . Este problema por su complej idad es considerado en computación como un problema NP-Completo. En este punto cabe señalar que los problemas matemáticos o de computación se clasifican por su complejidad en diferentes grupos:

Complejidad P, donde los problemas pueden ser resueltos en una máquina determinista en tiempo polinómico.

Complejidad NP, donde los problemas pueden ser resueltos por una máquina no determinista en tiempo polinómico.

Complejidad NP-Completo, que son problemas de complejidad NP que tienen difícil solución en tiempos polinomiales, con una máquina no determinista.

También existen implementaciones paralelas para la solución del problema del camino hamiltoniano pero necesitan un gran volumen de recursos y comunicaciones entre los nodos conectados. Por ese motivo Adleman presentó una nueva alternativa para programar con "ADN" orgánico que presenta un masivo paralelismo en la realización de las operaciones y por tanto en la obtención de los resultados finales, pero con las limitaciones comentadas anteriormente. Diseño un sistema para resolver el problema del camino hamiltoniano con programación "ADN" orgánico y, por lo tanto demostró que se podían resolver problemas NP- Completos en un tiempo computacional cercano al polinomial. En este sentido puede citarse el documento de patente US7167847. Ya en el siglo XX, el científico Edsger Dijkstra, planteó unos nuevos sistemas para el cálculo de rutas, de modo que no sólo se establecía cómo se debía de llegar de un punto a otro, sino que también se establecía que fuera en el menor tiempo posible. Dijkstra apoyó sus investigaciones en las ciencias de la computación, fruto de ello fue el algoritmo de Dijkstra. Este algoritmo se fundamenta en la determinación del camino más corto, dado un vértice origen en un grafo dirigido y con pesos positivos en las aristas. La idea es ir explorando todos los caminos más cortos que parten del vértice origen y, que llegan a todos los demás vértices . Una vez determinado el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene. Este algoritmo se basa en una estrategia, conocida como algoritmo voraz, que no funciona con grafos con aristas de coste negativo. Más tarde Robert W. Floyd, junto con Wharshall, modificaron el algoritmo de Dijkstra, aunque, las modificaciones eran relevantes, aún no podían ser aplicados en redes industriales o en el cálculo de rutas. Viendo la problemática de una y las ventajas de la otra

- A - ciencia, la invención establece una tecnología que une la electrónica y la genética, dos áreas hasta la fecha disjuntas. Esta tecnología está basada en circuitos integrados, electrónica y, "ADN" o genética, creando con ello el primer "ADN" inorgánico con circuitos electrónicos, motivo por el cual la invención ha denominado a esta tecnología InChroSil (Inorganic CHROmosome based in SILicon) .

El sistema de la invención tiene la gran ventaja de que permite su reutilización, ya que el usuario puede utilizarlo tantas veces como se desee, ya que se materializa mediante circuitos electrónicos.

DESCRIPCIóN DE LA INVENCIóN

Para resolver los inconvenientes y conseguir los objetivos anteriormente indicados, la invención ha desarrollado un nuevo sistema que consigue la obtención de un "ADN" inorgánico .

Para comprender la invención, es necesario realizar una introducción genética de los cromosomas, que están formados por "ADN" y proteínas. A su vez el "ADN" está compuesto por dos fibras longitudinales unidas por centrómero. Estas fibras se llaman cromatidas y representan dos hebras idénticas del "ADN" duplicado.

Por consiguiente el "ADN" está compuesto por hebras o cadenas de nucleótidos, los cuales se diferencian en cuatro tipos que se numeran a continuación:

Adenina, se representa mediante la letra A. Guanina, se representa mediante la letra G. Citosina, se representa mediante la letra C. - Timina, se representa mediante la letra T.

Por consiguiente el "ADN" está compuesto por dos hebras enlazadas y cada hebra contiene innumerables nucleótidos. En una misma hebra no existen nucleótidos complementarios, es decir, pueden unirse sin restricción alguna. En cambio al enlazar las dos hebras, existen

restricciones de complementariedad, de tal modo, que una Adenina (A) de una hebra sólo se puede unir con las Timinas (T) de la hebra complementaria, de igual modo las Guaninas (G) sólo se pueden unir con las citosinas (C) . El sistema de la invención se caracteriza porque comprende medios de codificación binaria de los diferentes cuatro tipos de nucleótidos que componen las hebras, de manera que a los nucleótidos que forman enlaces complementarios se les asignan códigos complementarios mediante la inversión de uno de ellos. Además la invención incluye unidades de almacenamiento de un código de un nucleótido y de un código seleccionado entre su código complementario o ningún código; todo ello para obtener un nucleótido y su complementario o únicamente un nucleótido, conectándose dichas unidades de almacenamiento en serie para formar la cadena de nucleótidos que constituyen cada hebra de una cadena de "ADN" . Por consiguiente mediante la codificación comentada, que se almacena en las unidades de almacenamiento, se obtiene una estructura electrónica a la que se permite el acceso a un nucleótido y/o a su complementario, a una hebra y a las dos hebras de la cadena de "ADN" según se requiera, mediante circuitos electrónicos conocidos que realicen la selección de las diferentes unidades de almacenamiento en función de los requerimientos deseados.

La invención prevé diferentes módulos que están constituidos por agrupaciones de unidades de almacenamiento, en las que en cada módulo se almacena una cadena de "ADN" , estando los módulos conectados en filas y columnas, de manera que se permita acceder a cada cadena de "ADN" mediante la selección de filas o columnas.

De la descripción realizada se deduce que la primera aplicación de la invención consiste en su empleo como banco de datos de "ADN" . En la realización preferente de la invención el código

asignado a cada nucleótido comprende dos bits y su almacenamiento depende de las entradas aplicadas a cada unidad de almacenamiento mediante medios electrónicos, de manera que cada unidad de almacenamiento puede ser codificada según el nucleótido que se desee y su complementario .

La invención prevé la incorporación de medios de codificación de numeración en base 4 compuesta por cuatro nucleótidos de un cromosoma (A, G, C y T) . Además prevé que los dos bits correspondientes a cada nucleótido adquieren las cantidades decimales de 0 a 3 de manera que se permite conformar una- pluralidad de presentaciones numéricas determinadas por la posición de los dos bits y por el valor que recibe en cada posición. Esta codificación permite que cualquier sistema de codificación que tenga correspondencia con el decimal o binario, puede ser codificado con el sistema de numeración y codificación de la invención.

La codificación comentada permite que la invención incorpore medios para efectuar operaciones como son sumas, restas, multiplicaciones y/o divisiones, así como codificar cualquier número en coma fija o flotante de simple y doble precisión utilizando codificación en complemento Al y en complemento A2. Al igual que las memorias del estado de la técnica, las unidades de almacenamiento de la invención pueden ser volátiles, pero en este caso la invención denomina InCroSil Access Memory (IAM) , pudiendo ser también memorias no volátiles de sólo lectura que la invención denomina InCrosil Read OnIy Memory (IROM) . La invención incorpora medios de acceso estructurado a los módulos y unidades de almacenamiento mediante localización de una cadena de "ADN" , posterior localización de una hebra y a continuación mediante la designación de un nucleótico o grupo de nucleótidos, de manera que se pueda acceder a toda la

cadena o parte de ella. Por consiguiente, mediante los módulos y unidades de almacenamiento de la invención no se accede por filas o columnas como sucede en las memorias convencionales, sino que permite tres accesos diferentes, según ha sido comentado, por lo que se permite un acceso a partir de tres selecciones que puede denominarse acceso tridimensional .

A su vez, tal y como ya fue comentado con anterioridad una cadena de "ADN" puede ser considerada como una fila o como una columna, es decir, el sistema que administra la memoria IAM, puede estipular cómo estarían almacenadas las cadenas de "ADN" en la memoria, ya sea por filas o por columnas .

En base a toda la estructura descrita, se comprende que la invención puede incorporar medios para codificar en las unidades de almacenamiento, que forman hebras, representaciones de problemas mediante grafos que comprenden elementos constituidos por vértices y aristas y opcionalmente pueden incorporar el peso o dirección de la arista, de manera que el sistema de la invención codifica a una hebra en un primer conjunto que contiene vértices y aristas y no contiene el peso de éstas, correspondientes a elementos iniciales y los correspondientes a los elementos que no contienen elementos finales; habiéndose previsto que en la hebra complementaria se codifique un segundo conjunto que contiene elementos del grafo constituidos igualmente por vértices y aristas correspondientes a los elementos finales y los correspondientes a los elementos que no contienen elementos finales. Cada una de las unidades de almacenamiento de ambas hebras están unidas entre sí mediante comparadores que forman una matriz para que se realice el procesado de ambas hebras de forma paralela así como las comparaciones entre todos los elementos de ambos conjuntos lo que permite resolver problemas que pueden representarse mediante grafos.

Los comparadores forman una matriz y están conectados a un buffer al que se aplican medios de recuperación de caminos de orden polinomial para determinar la ruta más óptima entre dos puntos del grafo. Como fue señalado las aristas de los grafos pueden tener peso o dirección, en cuyo caso la invención comprende medios adicionales de almacenamiento del peso de una arista, así como medios para sumar los pesos de cada arista y obtener los pesos totales de cada arista, habiéndose previsto que además incorpore medios de ordenación de los pesos totales de cada arista según criterios previamente establecidos, lo que permite resolver problemas de algoritmos conocidos como son Dijkstra, Floyd-Warshall y Bellman-Ford, Ford-Fulkenson. La estructura descrita permite su aplicación en problemas de flujo como pueden ser flotas de vehículos, optimización de procesos industriales, flujos de trabajo, programas de acoplamientos y de redes de comunicaciones, para lo que estos problemas se representan como un grafo. Así por ejemplo la información e instrucción de la maquinaria de una planta industrial puede ser representada como un grafo para resolver el problema planteado.

Igualmente la invención prevé codificar el problema del camino hamiltoniano en las unidades de memoria de almacenamiento que constituyen las hebras, en una de las cuales se codifica el grafo completo y en las complementarias el grafo completo con restricciones conocidas. En este caso las hebras están conectadas a comparadores formando una matriz para comparar las aristas de ambos grafos dos a dos de forma paralela para indicar si los bits del resultado de cada comparación son todos iguales y se refieren a una misma arista y en consecuencia ésta pertenece a ambos grafos.

Al resultado de la comparación se la aplican medios para crear niveles del árbol de wallace indicativo de si la

arista es camino o no lo es, de forma que se resuelve el problema del camino hamiltoniano.

En este caso los comparadores que comparan las aristas de ambos grafos dos a dos, están constituidos por semisumadores lógicos sin acarreo, cuya salida está conectada a una puerta lógica de detección de un solo bits del resultado de la comparación, para obtener un solo dato, tal y como fue señalado, y que indica si los bits del resultado de cada comparación pertenecen a ambos grafos de los conjuntos codificados.

Los medios para crear niveles del árbol de wallace comprenden unas primeras puertas lógicas por cada columna de la matriz de comparadores que representa el grafo completo y están conectadas a las salidas de los comparadores para confirmar la pertenencia de dicha arista al conjunto de aristas del grafo con restricciones de forma que indica si es o no camino.

Las salidas de las primeras puertas lógicas están conectadas a una segunda puerta lógica de detección de si todas las aristas son camino, de manera que la invención determina el camino hamiltoniano. Además incorpora medios de almacenamiento del resultado obtenido.

En este caso la invención también prevé la posibilidad de que se tenga en cuenta el peso de las aristas, para lo que comprende medios para recibir los caminos encontrados y establecer la correspondencia entre peso y arista y obtener los pesos de cada camino. En este caso también comprende medios de ordenación de los pesos de los caminos según criterios previamente establecidos para la elección del mejor camino.

En otra realización de la invención cuando se codifiquen los vértices y, por lo tanto se establezca el valor de las aristas que los unen, el sistema almacena en esa dirección de memoria, el valor del peso de esa arista en el grafo. En este caso se busca el valor de las aristas

en la memoria, ya que como se conoce su dirección, se conoce su valor, es decir se codifica una referencia a la memoria, como es su dirección y no el valor de la arista. Los pesos obtenidos se suman para obtener los totales de cada camino que se almacenan en memorias con direcciones consecutivas y mediante medios de ordenación de los pesos de los caminos según criterios previamente establecidos, se efectúa la elección del mejor camino.

Esta configuración también permite la aplicación de la invención a la solución de problemas de ciclos hamiltonianos mediante una codificación indicativa de que el vértice de salida del grafo es igual al vértice destino.

También cabe señalar que la invención incorpora medios para codificar un grafo de manera que los vértices representan las aristas y a la inversa y así obtener qué secuencia de vértices se debe seguir para pasar por todas las aristas y permitir resolver el problema del camino euleriano .

Mediante la incorporación de medios para codificar en las hebras que el vértice inicial es el mismo que el vértice final, se permite la aplicación de la invención para resolver ciclos eulerianos .

La invención también permite establecer codificación del peso de las aristas en la resolución de caminos eulerianos o ciclos eulerianos, de forma que permite plantear nuevos problemas de optimización de los caminos eulerianos .

A continuación para facilitar una mejor comprensión de esta memoria descriptiva y formando parte integrante de la misma, se acompañan una serie de figuras en las que con carácter ilustrativo y no limitativo se ha representado el objeto de la invención.

BREVE ENUNCIADO DE LAS FIGURAS

Figura 1.- Muestra una representación de la cadena de "ADN" orgánica.

Figura 2.- Muestra los diferentes tipos de estructuras de cadena "ADN" y las uniones entre nucleótidos.

Figura 3.- Muestra un posible ejemplo de realización de una implementación de una unidad de almacenamiento de un nucleótido y de su complementario.

Figura 4.- Muestra una tabla de la correspondencia entre diferentes sistemas de numeración comparados con la codificación en base 4 de la invención.

Figura 5.- Muestra una tabla correspondiente a la operación suma de dos nucleótidos según la codificación de la invención.

Figura 6.- Muestra una tabla equivalente a la figura anterior, pero para la resta.

Figura 7.- Muestra una representación de un posible ejemplo de resta.

Figura 8.- Muestra una tabla equivalente a las figuras 5 y 6, pero para la multiplicación.

Figura 9.- Muestra un posible ejemplo de una multiplicación . Figura 10.- Muestra una tabla de representación de coma flotante en simple precisión según la codificación de la invención.

Figura 11.- Muestra una tabla de diferentes combinaciones del exponente (como fija, complemento Al, A2 y exceso 4 ⁴ ) .

Figura 12. - Muestra una tabla de representación de coma flotante de doble precisión.

Figura 13.- Muestra una representación esquemática de la unidad de almacenamiento básica representada en la figura 3.

Figura 14.- Muestra una representación esquemática equivalente a la figura anterior, pero según una configuración más detallada.

Figura 15.- Muestra una representación de la

estructura de una posible agrupación de memorias volátiles y no volátiles representadas en las figuras 13 y 14.

Figura 16.- Muestra una representación de un posible ejemplo de un grafo. Figura 17.- Muestra una posible implementación para el cálculo de caminos .

Figura 18.- Muestra una representación de un grafo hamiltoniano dirigido y no ponderado.

Figura 19.- Muestra una representación del grafo del camino hamiltoniano.

Figura 20.- Muestra una cadena de "ADN" inorgánico de la invención referente a una agrupación posible de aristas y vértices para resolver el problema del camino hamiltoniano. Figura 21.- Muestra una codificación de los vértices y aristas según la figura anterior.

Figura 22. - Muestra una codificación de los vértices y aristas detallada de la figura anterior.

Figura 23.- Muestra el conjunto de cadenas de "ADN" inorgánicos de la invención con todas las posibles soluciones del camino.

Figura 24,- Muestra la representación de un semisumador lógico que se aplica en el sistema de la invención. Figura 25.- Muestra una representación de una posible implementación para efectuar la comparación de aristas en aristas en paralelo para la resolución del problema hamiltoniano.

Figura 26.- Muestra un diagrama de bloques funcional de la implementación de la invención para la resolución de problemas hamiltonianos.

Figura 27.- Muestra el circuito completo para la solución del camino hamiltoniano.

Figura 28.- Muestra un diagrama de bloques funcional de una primera implementación para la resolución del

probleraa del camino hamiltoniano ponderado.

Figura 29.- Muestra un diagrama de bloques funcional de una segunda implementación para la solución del problema del camino hamiltoniano ponderado. DESCRIPCIóN DE LAS FOR]XtAg DE REALIZACIóN PREFERIDAS

A continuación se realiza una descripción de la invención basada en las figuras anteriormente comentadas.

Como ya ha sido comentado con anterioridad, un cromosoma está formado por "ADN" y proteínas. A su vez el "ADN" está compuesto por hebras o cadenas de nucleótidos, los cuales se diferencian en cuatro tipos : Adenina (A) ,

Guanina (G) , Citosina (C) y Timina (T) .

El "ADN" está compuesto por dos hebras enlazadas y cada hebra contiene innumerables nucleótidos . En una misma hebra no existe nucleótidos complementarios, es decir, pueden unirse sin restricción alguna. En cambio al enlazar las dos hebras, existen restricciones de complementariedad, de tal modo, que un Adenina (A) de una hebra sólo se podrá unir con las Timinas (T) de la hebra complementaria, de igual modo con las Guaninas (G) con las Citosinas (C) , es otro enlace posible. Debido a esta organización de las hebras, la codificación del ADN no puede ser al azar y debe tener una estructura previamente definida (véase figura 1) .

Para modelar el comportamiento orgánico del cromosoma se diseño una codificación, que se describe de forma detallada en secciones posteriores, para cada uno de los nucleótidos, en la siguiente enumeración se presenta una parte de esta codificación:

• Adenina (A) se le asigna el valor de "00".

• Guanina (G) se le asigna el valor de "01".

• Citosina(C) se le asigna el valor de "10".

• Timina (T) se le asigna el valor de "11".

Una vez codificados los nucleótidos, siguiendo la codificación implementada, el siguiente paso es la implementación a nivel físico mediante circuitos electrónicos (por ejemplo, biestables u otro dispositivo que almacene los nucleótidos o estados) , y establecer la estructura física de los mismos dentro de las hebras y sus relaciones con la hebra complementaría. La idea que se planteó inicialmente era un circuito, el cual estaba dividido en cuatro partes iguales. Cada parte del circuito estaba separado de la otra mediante un material aislante, para no producir interferencias entre los distintos componentes que se almacenan en ellas. Por otro lado, en cada parte del circuito, se colocarían los componentes que codifican a un determinado nucleótido inorgánico. Esto permite la libre elección de un determinado nucleótido dentro de la posición de una hebra artificial mediante las conexiones permitidas entre los diferentes nucleótidos.

La longitud de la hebra dependerá del número de circuitos colocados en forma de pila, creando así un chip tridimensional, cosa que permitirá la emulación de la estructura orgánica (cromosoma) . También se puede realizar a nivel planar, la elección de una tecnología u otra, dependería de los recursos existentes y las necesidades finales del proyecto. Una vez codificado el circuito con los cuatro nucleótidos, se debe conectar cada circuito con su circuito superior, mediante conexiones en serie, de esta forma se obtiene una hebra o cadena de nucleótidos . Por otra parte se pensó en las conexiones en paralelo o enlaces con la hebra complementaria, hay que tener en cuenta las relaciones de complementariedad de los distintos nucleótidos, relación explicada anteriormente. Estos enlaces se codificaran dentro del propio circuito mediante componentes lógicos .

Con este sistema se definiría el nucleótido de una hebra y con el circuito combinacional o método de inversión se obtendría de forma inmediata el nucleótido complementario en la otra hebra. Si esto se aplica en cada circuito apilado, se produciría una reacción en cadena, que nos permitiría definir la hebra completa. De esta forma se evitaría inconsistencias entre los enlaces paralelos, ya que no se pueden unir dos nucleótidos que no sean complementarios . Por otra parte, los enlaces en serie o entre nucleótidos de una misma hebra se realizará por posición concreta, es decir, se realizará de una forma contigua, por lo se podrán realizar tanto accesos secuenciales como aleatorios a un determinado nucleótido dentro de una determinada hebra. Con este sistema de acceso, y las conexiones paralelas, se podrá activar un determinado par de nucleótidos en cualquier momento y poder conseguir innumerables combinaciones y, cromosomas diferentes.

Este planteamiento inicial desaprovecha mucha información en cada operación, ya que existen partes del circuito que no se utilizan, aprovechándose sólo la mitad del circuito, es decir, el planteamiento inicial era realizar un circuito con los cuatro nucleótidos de forma estática, de esta forma si se elegía un nucleótido determinado, en el mismo circuito se activaba el nucleótido de la hebra complementaría. Indicar que en este planteamiento inicial los nucleótidos de un mismo nivel residen en el mismo circuito y, se activan por la activación de uno de los dos. Por ese motivo si se configuraba un par de nucleótidos se desaprovecha la mitad de los recursos del circuito, por esa causa se pensó en un planteamiento más dinámico, donde los nucleótidos no estuvieran predefinidos en el circuito y que dependiendo de unas determinadas entradas obtuviéramos un determinado nucleótido u otro.

Con este nuevo planteamiento los nucleótidos en un circuito pasan a ser dos y, además son dinámicos, es decir, dependiendo de unas determinadas entradas se obtiene un determinado tipo de nucleótido. Esta reducción hace que se aprovechen mejor los recursos del circuito, ya que se pasa de un circuito de cuatro partes a un circuito de dos. Toda esta simplificación no afectará la estructura del nucleótido, ya que seguirá estando compuesto de dos biestables o componentes electrónicos equivalentes, aunque el valor almacenado en ellos dependerá de las entradas aplicadas, ya que deben de ser dinámicos.

Con este nuevo diseño se pasa de una estructura de pila a una forma totalmente helicoidal como se ve en la figura 1. Por tanto, con este planteamiento se simplifica el circuito y la utilización del mismo, además en fase de fabricación existe una reducción considerable en los costes de producción y la utilización de recursos digitales y electrónicos, al aprovechar mejor el espacio y los componentes Las conexiones inorgánicas del cromosoma se dividen en dos partes muy importantes: la conexión en serie, donde un determinado nucleótido pueda conectarse con otro nucleótido del mismo tipo u otro y, por otra parte las conexiones paralelas donde un determinado nucleótido de una hebra sólo se puede conectar con su complementario o ninguno. Por lo tanto, si la hebra tiene todas sus conexiones o enlaces se le dice que la hebra está completa, mientras que si uno de los nucleótidos no tiene correspondencia con su complementario, la hebra está incompleta. Esta característica se tuvo en cuenta a la hora de diseñar las conexiones en paralelo entre nucleótidos de hebras complementarias, ya que en la activación de uno de los nucleótidos se indica al mismo si va producirse la activación del nucleótido complementario. Con este proceder se emula cualquier estructura de cromosomas, ya que no

todos poseen las mismas características y todos los pares de nucleótidos.

Para explicar las posibles combinaciones de las cadenas de ADN, en la figura 2 se presentan las combinaciones que se podrían dar. Estas estructuras permiten poder realizar operaciones con las cadenas de ADN, de tal modo que se pueden realizar problemas complejos, tales como los NP o NP-Completos . Como se ha comentado la invención se basa completamente en la relación existente entre el par nucleótido y todos sus posibles enlaces entre nucleótidos de una misma hebra, como entre nucleótidos de hebras complementarías .

En la figura 3 se representa un ejemplo de implementación que se ajusta a la descripción anteriormente comentada y en la que una unidad de almacenamiento 1 se materializa mediante cuatro biestables 2 de tipo D, de forma que los dos superiores están previstos para la codificación de un nucleótido y los dos inferiores para la codificación de su complementario. Por ejemplo, supongamos una implementación como la figura 3, si sólo se quiere utilizar el nucleótido de arriba (hebra incompleta) se activara la señal SELO de la figura 3, de este modo la señal de entrada/salida (E/S) nos permite establecer el valor que se desee que almacenen los biestables 2 del nucleótido de arriba. En cambio si sólo se quiere el nucleótido de abajo se activará la señal SELl de la figura 3 y, del mismo modo la señal (E/S) permitirá establecer el valor de los biestables del nucleótido de abajo . En cambio, si se quiere que los dos nucleótidos se activen (hebra completa) se activaran las señales SELO y SELl y mediante las señales (E/S) se estable el valor de uno de los nucleótidos, mientras que el otro nucleótido se activara con la utilización de puertas XOR. Con este diseño de un par de nucleótidos se pueden conseguir todas las

combinaciones posibles entre nucleótidos de hebras complementarias y por lo tanto emular el comportamiento de las posibles combinaciones de un cromosoma orgánico.

Las puertas lógicas de la unidad de almacenamiento 1 permite codificar los enlaces dentro del propio circuito, así como establecer que se desea almacenar un nucleótido o obtener su valor mediante la señala de escritura/lectura

(W/E) .

La representación esquemática de esta unidad de almacenamiento 1 se muestra en las figuras 13 y 14 tal y como será descrito con posterioridad.

También prevé la codificación de un sistema de numeración en base 4, el cual está compuesto por dos nucleótidos que forman una hebra de "ADN" . Este nuevo sistema es denominado en la invención Cod-InChroSil

(CODification - Inorganic CHROmosome based in SILicon) , de forma que se proporciona la posibilidad de aumentar la precisión de los sistemas numéricos actuales, además de poder utilizar en las operaciones, las características intrínsecas de la estructura de una hebra de ADN.

El sistema de numeración en base 4 de la invención utiliza como símbolo los nucleótidos de una hebra de "ADN" A, G, C y T. Convencionalmente es conocida la codificación del "ADN" orgánico de forma macroscópica, ya sea mediante la codificación de una hebra o porción, o también codificando las operaciones con sus operandos. Estas codificaciones no permiten tanta flexibilidad, porque limitan el número de combinaciones que se pueden realizar. Por ese motivo la invención consiste en un sistema de numeración donde se codifica el ADN de forma microscópica, es decir, a nivel de nucleótido que forma la hebra de ADN. Esta característica de atomicidad, permite realizar combinaciones para generar un sistema de numeración que tenga una potencia y escalabilidad, necesarias para la representación de cantidades numéricas. Se define la

codificación de un nucleótido como una secuencia de dos bits, los cuales adquieren las cantidades decimales de 0 a

3. Este sistema de numeración que presentamos, permite conformar numerosas representaciones numéricas, conformadas por la posición y el valor del símbolo dentro de la cadena numérica, resaltar que este sistema numérico es posicional y que el símbolo tiene dos significados, por una parte la posición dentro de la cadena numérica y, por otra parte el valor que recibe el símbolo. Con la combinación de ambas informaciones, se permite obtener parte del valor final de la cantidad numérica que se desee representar. En la figura

4, se observan la correspondencia entre nuestro sistema de numeración de la invención y el resto de sistema de numeración que se están utilizando en la actualidad. Siempre un ejemplo es más aclaratorio que un conjunto de palabras, por ese motivo, si se considera el número 4567io en base decimal, la representación correspondiente en binario es 000100011101011I ₂ , en octal es 010727 ₈ , en hexadecimal es 11D7 ₁₆ y finalmente en la codificación de Cod- JnChroSil es AGAGTGGT ₄ . También se puede cambiar de un sistema numérico utilizando un desarrollo polinómico del número (teorema fundamental de la numeración) , donde las cifras del número poseen dos valores, por una parte el intrínseco como cifra y luego el posicional, de este modo la ecuación de cambio viene determinada como la siguiente:

n° (X _n-1 X ₂ XiX ₀ ) b = X _n -Ib" ^"1 + +X ₂ b ² +X ₁ b ¹ +X ₀ b°

Por ejemplo, tenemos el siguiente número codificado en Cod- JnChroSil AGAGTGGT ₄ , el número en decimal es el siguiente :

AGAGTGGT ₄ = A- 4 ⁷ + G- 4 ⁶ + A- 4 ⁵ + G- 4 ⁴ + T- 4 ³ + G- 4 ² + G- 4 ¹ +

Tr--44°° == 00--44 ⁷⁷ ++ 1l--44 ^6e + 00--44 ⁵⁵ ++ 11--44 ⁴⁴ ++ 3-4 ^J 1-4 ² + 1-4 ¹ + 3 ^• 4 ^o = 4567io

La operación inversa de un número decimal a una codificación Cod- JnChroSil . Suponiendo el número en decimal 189io, el número en Cod- JnChroSil es el siguiente:

189 div 4 = 47 -> restθ(189,4) = 1 -> G 47 div 4 = 11 -> resto(47,4) = 3 -> T 11 div 4 = 2 -> resto(ll,4) = 3 -> T 2 div 4 = 2 -> resto (2, 4) = 2 -> C

Se muestran ejemplos, supongamos se tiene el número 873,875i ₀ y se quiere pasar a Cod- InCh.roSil , la mecánica es la siguiente:

• La parte entera es calculada como el ejemplo anterior TGCCG.

• 0,875 x 4 = 3,5 -) la parte entera es 3 entonces es T.

• 0,5 x 4 = 2 -) la parte entera es 2 entonces es C. • Finalmente, la parte decimal es cero, entonces el número final es TGCCG, TC ₄

De forma general en un sistema de numeración se puede representar una cantidad numérica de la siguiente forma N _b = [a _n -i a _n-2 a _n . ₃ ... a ₃ a ₂ ai a ₀ , a.χ a _-2 a _-3 ...a _k ] _b , donde n+k indica la cantidad de dígitos de la cifra, a su vez n indica el numero dígitos en la parte entera, mientras que k indica la parte fraccionaria. Finalmente indicar, que con la utilización del sistema de numeración Cod-JnChroSil lo se hace compatible con el resto de sistemas de numeración actuales, prueba de ello la encontramos en los párrafos anteriores, que se ha pasado de decimal a Cod-JnChroSil y de Cod-JnChroSil a decimal.

Todo sistema de numeración necesita de unas reglas y operaciones para poder realizar cálculos entre sus operandos . Por ese motivo en Cod-InChroSil, consideran las habituales, como son; la suma, resta, multiplicación, división, etc. En primer lugar es define la suma, debido a que es una operación altamente utilizada en numerosos cálculos matemáticos. La suma es una operación aritmética definida sobre un conjunto de números y sus estructuras

(vectores, conjuntos, etc.) . En la invención, la suma se define como una operación sobre números codificados en Cod-

JnChroSil . Como bien es sabido, la suma posee diferentes propiedades que la caracterizan y que serán aplicables en la invención, estás son; la propiedad conmutativa, donde el orden de los operandos no altera el resultado, la propiedad asociativa, el elemento neutro y, finalmente el elemento opuesto. En la figura 5 se dan las directrices para la suma de dos nucleótidos. Resaltar, que como en la suma decimal que cuando se supera la base se dice la frase y llevamos una, en esta operación de suma también se tiene en cuenta el acarreo ocasionado por un desbordamiento, lo podemos observar en la figura 5 donde hay celdas de la tabla que posee dos símbolos, el primero de ellos representa el desbordamiento producido y, el segundo el resultado de la operación, es decir, suponiendo que se quieren sumar dos números ATCGATA y TAGCCAA, en este caso no se produce ningún acarreo.

Cuenta o acarreo

ATCGATA número 1 (3660 en decimal) + TAGCCAA número 2 (12704 en decimal)

TTTTCTA resultado (16364 en decimal)

En este otro ejemplo tenemos los siguientes números ATCGATA y ATCTTTC, en este caso si que se producen acarreos.

G G G G G cuenta o acarreo A T C GA T A número 1 (3660 en decimal)

+ A T C T T T C número 2 (3838 en decimal)

GiTtGtGTAtCC resultado (7498 en decimal o GTGGACC)

La siguiente operación que se define es la resta en codificación Cod- JnChroSil . La resta es conocida como una operación aritmética opuesta a la suma, en el caso particular de la invención la resta entre dos nucleótidos se define siguiendo las siguientes directrices de la figura 6.

Como se observa en la figura 6 se ha tenido en cuenta el acarreo ocasionado al restar dos nucleótidos, por ese motivo y al igual que se hizo con la operación de suma, en una misma celda de la tabla (véase figura 6) , se escriben dos símbolos, el primero hace referencia al desbordamiento o acarreo y el segundo hace referencia al resultado. Para ver como funciona la resta mediante esta codificación se muestra un ejemplo aclaratorio de esta operación. Los siguientes números en Cod-JnChroSil, TGAT ₄ (en decimal es el 211) y GCCC ₄ (en decimal es el 106) , el resultado de la resta es 105 en decimal GCCG ₄ en Cod-JnChroSil, seguidamente se realiza el cálculo paso a paso con la resta que ha sido definida en la figura 7.

Como observamos en la figura 7, cuando se resta T - C =

G no se produce acarreo, pero si cuando se resta A - C = GC

(la siguiente cifra del numero) , el resultado es C, pero el acarreo es G, esta cantidad tiene que sumarse a la siguiente cifra, en este caso es C. De esta operación de suma se obtiene T. A continuación se resta G del numero 1 al nuevo resultado (T) , obteniendo el valor de GC, de nuevo se ha producido un acarreo con valor G. Se suma este acarreo con la siguiente cifra del numero 2 y el resultado

se resta con su homólogo posicional del numero 1, el cual se obtiene G. Como se observa el mecanismo es el mismo que en la resta en decimal, cuando la cifra del número 1 es mayor a la cifra del numero 2 se realiza la resta y no se provoca desbordamiento, pero cuando es al contrario, se calcula cuantos llevamos desde la cifra del numero 2 hacia la cifra del numero 1, siendo este el resultado. A continuación se suma una unidad a la siguiente cifra y se restan ambas cifras de la misma posición. La resta también se puede establecer como la suma de dos números, donde uno de ellos se utiliza el opuesto (en este caso complementario) más la suma del nucleótido G (más tarde se explicará en secciones posteriores este formato de representación) . Como se comentó en JnChroSil la cadena de ADN está formada por dos hebras que se rigen por propiedades de complementariedad, es decir, un nucleótido de una hebra no se puede unir con cualquier nucleótido de la hebra complementaria, sólo con su complementario establecido. Esto permite que cuando se codifique un número en Cod- TnChroSil en una cadena de ADN, se esté codificando automáticamente su complementario en la hebra complementaria. Esta propiedad intrínseca de las cadenas de ADN, permite aplicar operaciones de suma muy fácilmente, debido a que ya se posee el opuesto o complementario del numero, sólo faltaría que este número fuera sumado por el nucleótido G, formato de representación denominado complemento a 2 y, que en líneas posteriores a este documento se explica con detalle. Se recurre otra vez al ejemplo, para dar una visión más aclaratoria de la operación resta en este sistema de numeración. Si se tiene el numero TGCG (217 en decimal) y se quiere restarlo con el numero CCCT (171 en decimal) , la resta decimal nos da el siguiente resultado; 46 (ACTC) . En este sistema de numeración se aplican los siguientes pasos:

• El primer operando no se modifica (TGCG)

• Se toma el complementario del segundo operando, es decir, A se transforma en T y viceversa y, C se transforma en G y viceversa, en este caso en concreto es GGGA.

• Al número resultante del punto 2, se suma G (GGGG) .

• Se suma el primer operando y el numero del punto 3.

• Se elige, el número máximo de nucleótidos de los dos operandos y, este será el resultado de la operación, en este ejemplo es ACTC.

En forma de ecuación quedaría de la siguiente forma: Resol _ReSt a = Operandol ₄ + Complemento (Operando2 ₄ ) + G ₄ ) , donde Resol _Resta es el resultado de la resta, Operandol ₄ es el primer operando en codificación Cod- InChroSil , Operando2 ₄ es el segundo operando en la misma codificación que el Operandol ₄ y, finalmente G ₄ que representa el literal del nucleótido G de una hebra de ADN. Por otra parte se define la función Complemento, como una función inyectiva tal queVx, ye {A, G, C, T} , 3 una f, función de complemento, tal que f:{A, G, C, T} ->{A, G, C, T} , donde f (x) = y, x ≠ y, y es el nucleótido complementario de x.

La siguiente operación que se define es la multiplicación. La multiplicación o producto se define como una operación aritmética donde se realizan sucesivas sumas. Al igual que en las anteriores operaciones se dan unas directrices para la multiplicación a nivel de nucleótidos, estos productos se observan en la figura 8.

Se tienen los siguientes números GTTG (125 en decimal) y GGA (20 en decimal) entonces el producto de ambos es el que se muestra en la figura 9. Como se observa se realiza un producto de un nucleótido por toda la cadena, generando así sumas sucesivas, al igual que pasa con la multiplicación decimal. Resaltar que en la operación anterior se han tenido en cuenta los acarreos en las sub-sumas, aunque no

se han representado, la causa es la no sobre-carga gráfica de información en la representación del producto anterior. Además se explicó en la definición de sumas, que debido a la suma de dos nucleótidos que provocan desbordamiento o acarreo, se suma la cantidad de acarreo al nucleótido siguiente.

Por último falta definir la operación aritmética de la división. La división se realiza igual (tiene el mismo mecanismo) que en el caso decimal, pero a diferencia de la de decimal, la restas y multiplicaciones se realizan mediante la operaciones de resta y multiplicación respectivamente, que se han definido en este documento. Por ejemplo, supongamos los siguiente números en Cod- InChroSil; dividendo es AGAACGA (en decimal es 1060) , mientras que el divisor es TGA (en decimal es 52) . Tras realizar la operación el cociente de la división es 20 en decimal (GGA en Cod- InChroSil) y, el resto, también es 20 en decimal

(GGA Cod-JnChroSil) , de esta forma, AGAACGA = TGA • GCA +

GCA (dividendo = divisor x cociente + resto) . Finalmente indicar, que con este sistema de numeración, Cod- JnChroSil, se pueden realizar todo tipo de operaciones al igual que con los existentes sistemas (binario, octal, hexadecimal, etc.). Esta característica unida a la gran posibilidad de migración a otros sistemas numéricos, permite trabajar con la información de las hebras de ADN, con mayor facilidad y, realizar con ellas operaciones que anteriormente eran impensables. Por ese motivo, el sistema de numeración Cod- JnChroSil, además de servir como apoyo a toda la tecnología relacionada a InChroSil y a esta invención, se presenta como una alternativa para la manipulación y utilización de la información contenida en las hebras de ADN.

Por otra parte, decir que una representación en coma flotante es un método de representación de números reales, donde la peculiaridad es la flotación o el movimiento de la

coma, elemento que separa la parte entera de la parte decimal (fraccionaria) de un número real. En oposición existe el sistema de representación en coma fija, donde de antemano se establece el número de dígitos que pertenecen a la parte decimal y cual a la parte entera. Estos sistemas de representación en coma flotante permiten a los sistemas de numeración representar cantidades numéricas grandes. Esta es la causa por la que se ha utilizado ampliamente este formato de coma flotante para la representación de números grandes. Un claro ejemplo, se encuentra en la área de la informática, que ha utilizado este tipo de representación, para el almacenamiento de representaciones numéricas muy grandes, que luego podían ser manipuladas matemáticamente. Por otra parte, todo número en coma flotante sigue un patrón establecido, el cual se puede resumir en la siguiente ecuación: r = m • b ^e , donde r es el número real, m es la mantisa, b es la base y finalmente e es el exponente, que permite elevar la base. Por ejemplo, el número 0.000123i ₀ en coma fija (utilizamos el sistema decimal) , en coma flotante podría tener las siguientes representaciones: 1.23 10 ^"4 , 0.123 10 ^'3 , 0.0123 10 ^~2 , 0.00123 10 ^"1 , etc. Como se observa en las anteriores representaciones numéricas, todas hacen referencia al mismo número pero con diferente representación en coma flotante . Por ese motivo y para evitar las ambigüedades en las representaciones de cantidades numéricas, se estableció un estándar que permite la representación homogénea de los números en coma flotante. Este estándar fue presentado al IEEE en el siglo pasado, más concretamente en la década de los ochenta, con el nombre de estándar IEEE 745. Este estándar permite definir un amplio rango de formatos de representación de cantidades numéricas, como son el cero y valores des-normalizados (el infinito y NAN) . Por otra parte, también se definen un conjunto de operaciones que se pueden hacer en este formato, denominada Aritmética de Coma

Flotante. En este estándar, el número de bits que se puede utilizar viene relacionado con la precisión que se puede obtener con la representación de los números, es decir, si utilizan más bits la precisión y el rango de representación es mayor. Esto permite diferenciar dos grandes grupos, aunque existen en la literatura extensiones de ambos. El primero de ellos es el de simple precisión, el cual utiliza 32 bits para su representación. Estos 32 bits están repartidos en tres secciones que identifican al número. Por otra parte, tenemos otro formato del estándar, que presenta mayor capacidad en sus representación y, que está compuesto por 64 bits, el doble, de ahí su nombre doble precisión. Al igual que su hermano pequeño, los bits de este formato están repartidos entre 3 secciones o campos, que caracterizan e identifican al número. En las siguientes líneas explicaremos el sistema en coma flotante para el sistema de numeración Cod- JnChroSil. Como se comento anteriormente se está tratando con un sistema de numeración que permite representar cantidad numéricas con sólo cuatro símbolos, los nucleótidos que componen una hebra de ADN. Pero al igual que los sistemas de numeración actuales, se necesitan muchos símbolos del sistema para representar cantidades numéricas grandes. Como se ha observado anteriormente la flexibilidad que posee los formatos en coma flotante es muy importante, por ese motivo, se ha considerado establecer un formato en coma flotante que permita representar números muy grandes mediante la codificación en Cod- JnChroSil. Si se utiliza esta codificación en los sistemas JnChroSil encontramos que por una parte se tiene la posibilidad de representar números muy grandes y, por otra parte, se aumenta la información almacenada del número, debido a que cuando se representa un número en este formato, también se está almacenando el número complementario u opuesto a este. Esto permite simplificar en gran medida las operaciones matemáticas que

necesiten ambos números. El siguiente paso es ¿Cómo establecer el formato para poder utilizar esta característica que ofrece los sistemas TnChroSil y, en definitiva el ADN?, la contestación la encontramos en las siguientes líneas, donde se explica como se ha definido un formato de representación en coma flotante para números codificados en Cod- JnChroSil . La invención puede definir dos grandes precisiones para las representaciones en coma flotante; por una parte está el formato de simple precisión, el cual se ha definido que posea 20 nucleótidos en su representación, haciendo un pequeño inciso en esta parte del documento, como bien ha percibido el lector en las líneas anteriores no se está hablando para cuantificar la longitud de la representación, de bits, sino, de nucleótidos. Continuando con la explicación del formato, se han utilizado 20 nucleótidos para establecer el formato de simple precisión. En este formato los 20 nucleótidos se reparten o distribuyen en 6 secciones o campos, que se describen a continuación; dos secciones de las seis están dedicadas a establecer cual de las dos hebras se utiliza para representar o definir el exponente y la mantisa respectivamente. Sendas secciones poseen una longitud de un nucleótido, información suficiente para poder decidir qué parte se debe elegir. Por ejemplo, si encontramos una representación donde en una sección anterior al exponente, aparece el nucleótido A, indica que el exponente que se necesita está en la hebra superior, por el contrario, si se encuentra un nucleótido T, indica que el exponente viene representado por la hebra inferior. Con este juego de posiciones se pueden realizar diversas combinaciones en la representación de un mismo número y simplificar en gran medida posibles operaciones matemáticas. Dentro del formato de representación en coma flotante existen otras dos secciones que tienen la función de especificar el tipo de codificación que están representados el exponente y la

mantisa. Se puede considerar para este formato cuatro tipos de codificación, que son los que se presentan en la siguiente enumeración.

• Signo Magnitud (toma el valor de A en la sección) : El formato de representación de enteros con signo que se denomina Signo Magnitud, la cual imita nuestra escritura manual de enteros, por una parte el signo y luego la magnitud del numero. Por ejemplo, el número - 34 _i0 el cual en Cod- InChroSil es GAAC ₄ , si se considera que el signo negativo se codifica como C y, por el contrario el signo positivo por A, por lo tanto el número de nuestro ejemplo es el siguiente CGAAC.

• Complemento a uno (toma el valor de G en la sección) : Se define el complemento a uno con la siguiente ecuación N _b ^Cal = b ⁿ - N _b/ donde N _b ^Cal es el numero en complemento a uno del numero N _b Sea N ₄ = CCTAAAG entonces su complemento a uno es N ₄ ^Cal = 4 ⁷ - CCTAAAG = GAAAAAAA - CCTAAAG = GGATTTC.

• Complemento a dos (toma el valor de C en la sección) : Una vez calculado el complemento a l, es fácil obtener el complemento a 2, por lo tanto el cálculo del complemento a dos sería mediante la siguiente ecuación N _b ^Ca2 = b ⁿ -N _b +l, por lo tanto siguiendo el ejemplo anterior, el numero en complemento a dos es el siguiente N ₄ ^Ca2 = 4 ⁷ -N ₄ + G = GAAAAAAA - CCTAAAG + G = GGATTTT.

• Exceso N (toma el valor de T) : El exceso n se formula de la siguiente forma N ^Exceso ₄ = N ₄ + (N-I) .

En definitiva, estas secciones especifican la codificación en la que está el elemento (exponente o

mantisa respectivamente) , es decir, si el anterior nucleótido al exponente o la mantisa posee por ejemplo el valor de G, esto indica que el exponente o mantisa está codificado en complemento Al. Finalmente, indicar que la longitud de estas secciones es de un nucleótido, al igual que como las secciones que determinaban la hebra a utilizar. Para poner punto final a la explicación de las secciones que conforman el formato de coma flotante de simple precisión, se refiere la sección de signo con una longitud de uno nucleótido y, que permite saber el signo del numero que se representa, es decir, si en esta sección se tiene el nucleótido A, quiere decir que el numero es positivo, por el contrario si se tiene el nucleótido T el numero es negativo. Por otra parte, está la sección del exponente, la cual posee una longitud de 4 nucleótidos. Finalmente esta la sección de la mantisa que con una longitud de 11 nucleótidos se completa los 20 nucleótidos que forman el formato de representación. En general y de forma gráfica en la figura 10 se muestran las diferentes secciones en que se divide el formato de coma flotante en simple precisión con 20 nucleótidos.

Con el anterior formato se puede conseguir exponentes con los siguientes rangos de valores, que se presentan en la siguiente enumeración.

• Coma fija con signo, Sea x el exponente entonces x e [-127,0] U [0,+127]

• Complemento Al, Sea x el exponente entonces x e [- 127,0] U [0,+127] • Complemento A2, Sea x el exponente entonces x € [- 128,0] Kj [0,+128)

• Exceso 4 ⁴ , Sea x el exponente entonces x e [-128,0] U [0,+128)

En la figura 11 se puede observar las diferentes codificaciones que puede adquirir el exponente. También se pueden observar las diferentes relaciones del mismo número en diferentes sistemas de codificación, además de la característica de la doble hebra que puede ser utilizada según las operaciones o el propósito convengan.

Por otra parte, se tiene que la mantisa que esta compuesta por 11 nucleótidos, de este modo los rangos que se pueden obtener con las diferentes codificaciones son los siguientes:

• Coma fija sin signo, Sea m la mantisa entonces m e [- 4 ^X1 -1,O] U [0,4"-I]

• Complemento Al, Sea m la mantisa entonces m e [-4 ¹¹ - 1,0] u [0,4"-I]

• Complemento A2, Sea m la mantisa entonces m e [-4",O] u [0, 4 ¹¹ ) -

• Exceso 4 ¹¹ , Sea m la mantisa entonces m e [-4",O] u

[0, 4")

De forma global, con este formato de representación en coma flotante con simple precisión se pueden conseguir números que estarían comprendidos en el siguiente intervalo numérico [-17592186044416 • 10 ¹²⁷ , 0] U [0,17592186044416 • 10 ¹²⁷ ] . Finalizaremos la explicación del formato de simple precisión con un ejemplo que ya ha sido utilizado para el formato IEEE 745. Recordando que el número era -118.625i ₀ y su codificación en IEEE 745 de simple precisión es 1100001011101101010000000000000 0, un numero binario de 32 bits. Por tanto utilizando nuestro sistema de coma flotante en simple precisión de la invención se tiene la siguiente codificación.

Hebra 1: T AT CAGG AA AGCCCAAAAAA Hebra 2 : A TA GTCC TT TCGGGTT T TTT

Como se puede observar el numero es negativo, por ese motivo se a codificado el primer nucleótido como T, los siguiente nucleótidos indican que el exponente esta representado en la hebra 1 y su codificación es exceso 128. Con respecto a la mantisa esta representada con coma fija sin signo y se corresponde con la hebra 1.

El siguiente formato de representación en coma flotante es la doble precisión, la cual utilizaba 40 nucleótidos o dos hebras de 20 nucleótidos. El formato de representación en doble precisión es el mismo que el de simple, bajo la salvedad que se aumenta el numero de nucleótidos en las secciones de exponente y mantisa. De forma gráfica en la figura 12 se muestra el formato de representación en doble precisión para 40 nucleótidos.

El rango de valores que puede admitir el exponente vendría definido por la siguiente enumeración.

• Coma fija con signo, Sea x el exponente entonces x e [-4 ⁷ -l,0] U [0,4 ⁷ -l]

• Complemento Al, Sea x el exponente entonces x € [-4 ⁷ - 1,0] U [0, 4 ⁷ -l]

• Complemento A2, Sea x el exponente entonces x e [- 4 ⁷ ,0] u [0, 4 ⁷ ) • Exceso 4 ⁷ , Sea x el exponente entonces x e [-4 ⁷ ,0] u [0, 4 ⁷ )

Para el caso de la mantisa el rango de valores que se podrían representar en este formato de coma flotante de doble precisión son los que se muestran en la siguiente enumeración.

• Coma fija sin signo, Sea m la mantisa entonces m e [- 4 ²⁸ -l,0] u [0, 4 ²⁸ -l]

• Complemento Al, Sea m la mantisa entonces m e [-4 ²⁸ - 1,0] u [0, 4 ²⁸ -l]

• Complemento A2 , Sea m la mantisa entonces m e [-4 ²⁸ ,0] u [0, 4 ²⁸ ) • Exceso 4 ²⁸ , Sea m la mantisa entonces m e [-4 ²⁸ ,0] U [0, 4 ²⁸ )

Realizando diferentes combinaciones entre el exponente y la mantisa se pueden obtener números con este formato de coma flotante de doble precisión que estarían comprendidos dentro de este intervalo numérico e [-72057594037927936 • 10 ^6553e , 0] U [0,72057594037927936 • 10 ⁶⁵⁵³⁶ ] .

La unidad de almacenamiento 1 descrita, puede ser de dos tipos que la invención ha denominado Mem- JnChroSil (Memory INorganic CHROmosome based in SILicon) . La invención puede utilizar memorias volátiles y no volátiles. La memoria volátil implementada, se ha denominado como JnChroSil Access Memory (IAM) . Este tipo de memorias, además de tener la característica de ser volátil, tiene la propiedad de acceso estructurado, de este modo accedemos a un nucleótido, mediante la previa localización de la hebra, para posterior designar el nucleótido. La memoria volátil de la invención permite la escritura y lectura de la información almacenada en ella. Esta memoria es volátil, es decir, si se desconecta de la energía eléctrica, la información se pierde. Por este motivo, este tipo de memoria temporal se suele utilizar para almacenar resultados intermedios o, datos que no son permanentes. El acceso diseñado, para este tipo de memorias es estructurado, es decir, si se quieren obtener datos de esta memoria, la funcionalidad es la siguiente; se elige una cadena de ADN inorgánico (o también denominado JnChroSil) de la memoria. Una vez determinada la cadena de ADN inorgánico se elige que hebra, que contiene la información que buscamos, indicar que las cadenas de ADN inorgánico que

se ha desarrollado para las memorias, están compuestas de dos hebras, al igual que sus homologas orgánicas. Con estas dos premisas localizadas, el siguiente punto es determinar que nucleótido o grupo de nucleótidos se quiere acceder, aunque también se puede dar el caso, que el usuario quiera acceder a la vez, a parte o a toda la cadena de ADN inorgánico, el cual previamente se había localizado. Con este sistema tridimensional, que hemos implementado para un sistema de memoria volátil, se ha utilizado la tecnología básica explicada en este documento ( XnChroSil) , ya que es fácilmente integrable en la tecnología existente, para la fabricación de memorias volátiles. Por otra parte, esta característica de estructuración hace que el sistema de memoria de la invención sea innovador y novedoso, ya que se ha considerado una dimensión más, la hebra, ya sea está principal o la complementaria, ya que en los anteriores sistemas de memoria volátil, sólo se considera dos dimensiones; las filas y las columnas. Otra característica de la invención es que se puede considerar una cadena de ADN inorgánico como una fila o como una columna, es decir, el sistema que administra la memoria (IAM) , puede estipular como estarían almacenadas las cadenas de ADN en la memoria, ya sean por filas o por columnas. Este sistema de memoria

(IAM) se diferencia por el carácter genético que tiene, debido a que mediante materiales inorgánicos se pueden almacenar información del ADN orgánico. Por lo tanto, las memorias volátiles o RAM existentes, además de ser distintas por el tipo de acceso, también lo son por la unidad básica de almacenamiento, los bits o grupos de bits para el caso de las RAM ¹ S y, los nucleótidos o grupos de nucleótidos para el caso de nuestra memoria IAM. Estas memorias pueden integrarse en los sistemas o dispositivos actuales que demandan memoria, por la simple razón que se pueden fabricar con semiconductores e integrarse en un circuito mediante micro-tecnología o nano-tecnología.

Debido a esto estas memorias también se pueden agrupar en módulos 21 con diferentes conectores . Estos conectores varían respecto a los dispositivos o placas electrónicas donde estuvieran conectadas las memorias. De esta forma se creara con esta estructura una memoria genética inorgánica basada en la estructura que posee la misma naturaleza, por esta razón, el acceso de memoria es mucho más interesante acceder a hebras completas que a un par de nucleótidos concretos, debido esencialmente por la forma de unión, separación, etc, de la propia naturaleza del ADN orgánico. Como se puede observar en la figura 15, el sistema de memoria está formado por cadenas de ADN inorgánico 12, que su vez están formadas por dos hebras, una principal y otra complementaria. Estas hebras de la memoria se dividen en nucleótidos, que representan las unidades básicas 1 de almacenamiento de estas memorias. Así de este modo, cuando queramos localizar un nucleótido o grupo de nucleótidos, primero debemos de localizar la cadena de ADN inorgánico, para luego determinar en qué hebra esta la información, para más tarde establecer que nucleótido o nucleótidos dentro de la hebra queremos acceder. En la figura 13 se muestra un esquema de una de estas unidades TnChroSil, la cual contiene dos nucleótidos, que son complementarios. Finalmente indicar, que debido a sus características genéticas se podrían utilizar estas memorias (IAM) , para el cálculo de operaciones intermedias o finales, pero siempre de carácter temporal, como es el caso del cálculo del trayectorias o resolución de grafos ponderados (caminos hamiltonianos, disjktra, euler, etc.), aunque podría ser ampliado a cualquier tipo de información que necesite de información mediante codificación genética, es decir, mediante la representación de cadenas de ADN. Una segunda memoria se ha implementado para la invención son las memorias no volátiles, la cuales se denominan en la invención JnChroSil Read OnIy Memory (IROM) . Este tipo de

memorias no volátiles, la información que contiene es de sólo lectura y al igual que las memorias IAM, descritas anteriormente, su unidad básica de almacenamiento son los nucleótidos, por lo tanto, su acceso es estructurado como en las IAM.

Las memorias no volátiles tiene la peculiaridad de que son memorias que sólo son de lectura. Las memorias IROM o memorias de sólo lectura con JnChroSil al igual que las memorias IAM explicadas anteriormente, poseen la misma estructuración que en la figura 15 y, también la misma estructura de acceso explicada antes para las memorias IAM, factor que la diferencia también de las memorias ROM o no volátiles existentes en la actualidad. Pero esta memoria tiene la propiedad de que su información es sólo de lectura, por lo tanto se puede implementar mediante fusibles u otro sistema que nos permitiera crear la información estática, de tal modo, que cuando se quemará o creará un nucleótido en este sistemas, el método inverso, que se ha descrito en la sección anterior, permite quemar o crear el nucleótido complementario, de este modo, seguiríamos un funcionamiento indicado en la figura 14. En esta figura la referencia 5 representa la información primaria, la referencia 6 la inversión de dicha información primaria, la referencia 7 la información secundaria que se obtiene y la referencia 8 los controles aplicados para conseguir el correcto funcionamiento.

Finalmente indicar, que este tipo de memorias tienen una gran utilidad, debido a que pueden almacenar información que quisiéramos que se mantuviera estática, como por ejemplo, la secuenciación de nuestro ADN orgánico, es decir, existen investigaciones donde intentan guardar el ADN orgánico en algún tubo o dispositivo, pero al ser un material orgánico es difícil de conservar, con la memoria no volátil de la invención se puede almacenar la información de forma permanente e incluso ser accedida

desde un ordenador o sistema informático. Otras aplicaciones, podría ser el conformar base de datos de ADN mediante memoria IROM, existen base de datos que almacenan de forma convencional el ADN, mediante software, la memoria de la invención permite el almacenamiento directo de esta información genética. En definitiva, la utilidad o funcionalidad de esta memoria IROM, puede ser muy variada y para diversos fines, dependiendo de la utilidad en que se desee emplear. La configuración descrita permite efectuar la resolución de problemas de rutas, flujos y redes abordándolos desde la perspectiva de la teoría de grafos .

Los problemas de encaminamiento, suelen ser resueltos mediante algoritmos deterministas (tiempo razonable) y, utilizando software, en vez de hardware. Esto hace que los sistemas opten por dispositivos que realizan modelos predictivos, no reales, sobre una posible solución aproximada, es decir, no existe en el mercado, ningún dispositivo que pueda decirle a un distribuidor de bebidas, por ejemplo, cual es el camino por el cual pasaría una única vez por cada bar o restaurante de una ciudad y, de forma óptima. Este problema es irresoluble con los dispositivos que en la actualidad existen, software de rutas, encaminamiento, etc. En cambio, si se pudiera resolver, para la compañía de bebidas y el propio distribuidor, serían unas ganancias y ahorro de tiempo respectivamente. Otro ejemplo, son la detección de averías o anomalías, por parte de las compañías de gas, electricidad, agua y teléfono. Existen en el mercado dispositivos de posicionamiento, mediante PLC, sensores, GIS, GPS, etc. Pero a nivel de localización y encaminamiento, se realiza mediante software, en algunos casos y, en otros es totalmente manual, donde el operario mediante una referencia posicional de la área geográfica, tiene que encontrar la posible avería. Por ese motivo, la

utilización de un dispositivo en tiempo real, que determine la posición y, calcule el camino más corto posible hasta llegar al punto de averías, es crucial para los intereses de la compañía, ya que en menos tiempo, puede resolver el problema. También en la organización industrial, donde se podría optimizar, a nivel de producción, la maquinaria de unos procesos y máquinas industriales, ya que lo podríamos representar como en un grafo la información y distribución de la maquinaría de la planta industrial. En definitiva, todo sistema que pueda ser reducido o esquematizado a una representación en forma de grafo, pueden aplicarse técnicas y metodológicas para resolver problemas en este campo, además si se considera que con la codificación del grafo en ADN y con la utilización de la tecnología JnChroSil, se pueden resolver de forma óptima, problemas que anteriormente no podían ser resueltos, además de poseer de un dispositivo que puede ser integrado en los sistemas actuales y, su reutilización es total, como se ha comentado en secciones anteriores . A continuación se tratan tres problemas que son la piedra angular en el cálculo de muchos de los problemas anteriormente mencionados .

• Encontrar la ruta más corta ó más óptima entre dos puntos . • Resolver problemas de los llamados del viajante bajo.

• La obtención de caminos eulerianos.

Encontrar la ruta más corta ó más óptima entre dos puntos.

Un problema típico de teoría de grafo, es encontrar la ruta más corta u óptima desde un punto inicial hasta un punto final. El planteamiento que se presenta a este problema ^• es considerar un grafo dirigido, ponderado (positivo o negativo) y, utilizar las características del

ADN, mediante tecnología InChroSil. De este modo, mediante un dispositivo basado en tecnología JnChroSil, se puede encontrar el camino más corto u óptimo. Pongamos un ejemplo, supongamos que se desea resolver el problema de la figura 16 mediante las listas de adyacencias y la teoría de conjunto.

En el grafo de la figura 16 se puede representar como una lista de adyacencias, donde la nomenclatura sería la siguiente; (vértice origen, arista, vértice destino) , por lo tanto, el grafo quedaría de la siguiente forma.

Nodo(s) : { (s,xl,u) , (s,x2,v) }

Nθdo(u): { (u,x3,w) , (u,x7,v) }

Nodo (v): {(v,x5,t)} Nθdo(w) : { (w,x4,v) , (w,x6,t) }

Cabe resaltar que, en la teoría de grafos se define la estructura de datos, lista de adyacencia, como una estructura que permite asociar a cada vértice i del grafo, una lista que contenga todos aquellos vértices j, que sean adyacentes a él. De este modo, se ahorra en espacio en su representación y, además el grafo, se puede representar por medio de un vector de n componentes (si |v|=n), donde cada componente va a ser una lista de adyacencia correspondiente a cada uno de los vértices del grafo. Además, cada elemento de la lista consta de un campo indicando el vértice adyacente. Por otra parte, si el grafo fuera etiquetado, habrá que añadir un segundo campo para mostrar el valor de la etiqueta.

Utilizando la teoría de conjuntos, podríamos formar un conjunto con todos los elementos de las listas de adyacencia, es decir, los elementos (vértice, arista, vértice) . Este conjunto que hemos formado tendría unas premisas que se enumeran a continuación.

• Si existen dos elementos pertenecientes al conjunto, tales como e _x y e ₂ , se observa que el componente final de βi es igual al componente inicial de e ₂ , ambos elementos reaccionan, creando un nuevo elemento, el cual pertenecerá al conjunto.

• Si existen elementos que pertenecen al conjunto, que contienen componentes que son iniciales y finales, no reaccionan con el resto, debido a que serian ya solución.

• Dos elementos que reaccionen tienen una relación positiva o 1, en cambio dos elementos que no reaccionen tienen una relación negativa o 0.

• Los elementos con componentes iniciales y que pertenecen a las listas de adyacencia, una vez reaccionados no vuelve a reaccionar.

Si se sabe que E es el conjunto de elementos y, C es el conjunto de componentes, podemos decir que la reacción es la siguiente operación:

V xe C I 3 yax, xbz eE tal que yax λ xbz ≡ yaxbz siendo y, a, x, b e C y yaxbz e E.

En este caso, tenemos un conjunto de elementos pertenecientes a las listas de adyacencias, los cuales los denotaremos como Elemento [i], por lo tanto, el conjunto inicialmente quedaría de la siguiente forma.

Elementol: { (s, xl, u) } Elemento2: { (s, x2, v) }

Elemento3 : { (u, x3, w) }

Elemento4: { (u, x7, v) }

Elementoδ: { (w, x4 , v) }

Elemento6: { (w, x6, t) } Elemento7: { (v, x5 , t) }

Con este conjunto inicial, se puede analizar sus elementos y ver cómo podrían cumplir las premisas asociadas al conjunto y, crear nuevos elementos. En este caso, se ve que Elementol reaccionaría con Elemento3 y Elemento4, formando Elementoδ y Elemento9 respectivamente. También se ve que Elemento2 reacciona con Elemento7 para formar Elementólo, el cual es ya solución. Después de esto el conjunto quedaría de la siguiente forma.

Elementol { (s, xl, u) } [no reacciona] premisa 4 Elemento2 { (s, x2, v) } [no reacciona] premisa 4 Elemento3 { (u, x3, w) } Elemento4 { (u, x7, v) } Elemento5 { (w, x4, v) } Elementoβ { (w, x6, t)} Elemento7 { (v, x5, t)} Elementos { (s, xl, u, x3, w) } Elemento9 { (s, xl, u, x7, v) }

ElementolO: {(s, x2 , v, x5 , t) }

En una siguiente ronda, se observa que Elementos puede reaccionar con Elementos formando Elementoll y, que también

Elementos puede reaccionar con Elementoβ para formar Elementol2, finalmente, Elemento9 reacciona con Elemento7 formando Elementol3. En esta ronda el conjunto quedaría.

Elementol: {(s, xl, u) } [no reacciona] premisa 4

Elemento2 : { (s, x2, v) } [no reacciona] premisa 4 Elemento3 : { (u, x3 , w) }

Elemento4 : { (u, x7, v) }

Elementos: { (w, x4 , v) }

Elemento6: { (w, x6, t) }

Elemento7: { (v, x5, t) }

Elementoδ: { (s, xl, u, x3, w) }

Elemento9: {(s, xl, u, x7, v) } Elementólo: {(s, x2 , v, x5, t) } Elementoll: {(s, xl, u, x3 , w, x4 , v) } Elementol2 : {(s, xl, u, x3 , w, x6 , t) } Elementol3 : {(s, xl, u, x7, v, x5 , t) }

Observando el conjunto se ve que existe una única reacción, la del Elementoll que reacciona con Elemento7 para formar Elementol4. Con esta última reacción, el conjunto quedaría de la siguiente forma.

Elementol { (s, xl, u) } [no reacciona] premisa 4 Elemento2 { (s, x2 , v) } [no reacciona] premisa 4 Elemento3 { (u, x3, w) } Elemento4 {(u, x7, v)} Elementoδ { (w, x4, v) } Elementoβ {(w, x6, t)} Elemento7 {(v, x5, t)} Elementoδ {(s, xl, u, x3, w) } Elemento9 { (s, xl, u, x7, v) }

Elementólo: { (s, x2, v, x5, t) }

Elementoll: { (s, xl, u, x3 , w, x4 , v) }

Elementol2: { (s, xl, u, x3 , w, x6 , t) }

Elementol3 : { (s, xl, u, x7, v, x5 , t) } Elementol4 : { (s, xl, u, x3 , w, x4 , v, x5, t) }

Se puede ver que los resultados son Elementólo, Elementol2, Elementol3 y finalmente Elementol4 , debido a que poseen componentes iniciales y finales. El funcionamiento del planteamiento anterior, para encontrar las soluciones o caminos, se realiza de forma secuencial. Pero en el circuito de la invención, se realiza de forma paralela, es decir, la invención ha considerado dos conjuntos; el primer conjunto Ci está formado por los elementos que contienen componentes iniciales y los

elementos que no contienen componentes finales. El segundo conjunto C ₂ está formado por los elementos que contienen componentes finales y los elementos que no contienen componentes iniciales. Ambos conjuntos son codificados mediante Cod- InChroSil y, almacenados en sendas hebras 10 respectivamente. Estas hebras unen sus componentes mediante una circuitería que contiene comparadores 9 formando una matriz como se observa en la figura 17 de esta forma reaccionan de forma paralela, obteniendo un conjunto de reacciones codificadas como positivas (1) o negativas (0) . Estas reacciones forman una matriz de 0's y l's. Por lo tanto, existen dos conjuntos Ci y C ₂ , que representan a los dos anteriores conjuntos mencionados y los cuales están codificados en hebras de InChroSil. Por otra parte, tenemos un conjunto C _r que esta formado por las reacciones entre los elementos de los conjunto Ci y C ₂ , de este modo se redefine la reacción como la operación donde si e ₂ e C ₂ y ei € Ci, entonces ei1Re ₂ e C _r , siendo 9? la reacción y los valores que puede tomar son 0 o 1. Como se observa, en la reacción ya no se crea un nuevo elemento que deberá de reaccionar, sino que reaccionan todos a la vez y se indica en una matriz, con un 1 si ha habido reacción o la reacción es positiva y, por el contrario con un cero si no habido reacción o la reacción ha sido negativa. Una vez obtenida la matriz con las reacciones de todos los elementos con todos, se pasa esta información a un buffer y, mediante software o circuitería se le aplica algoritmos de recuperación de caminos, los cuales no tienen un coste muy elevado y de orden polinomial. Si se consideran grafos ponderados, los pesos estarían almacenados en una memoria (Mera-InChroSil u otro tipo de memoria) , por lo tanto, las aristas del grafo anterior contienen la dirección y no el valor del peso, el motivo es por que se pueden utilizar cantidades grandes para los pesos y las direcciones tienen una longitud determinada.

Una vez encontrados las aristas del camino, sólo hay que sumar los costes de cada arista, para obtener el coste total del camino. Luego con los costes totales, se pueden ordenar los .caminos según un criterio de ordenación, todo esto se puede realizar mediante circuitería o módulos software, que se conectarían con el dispositivo. Con este circuito se resuelven los problemas planteados en los algoritmos de Dijkstra, Floyd-Warshall y Bellman-Ford, Ford-Fulkenson, al poder considerar costes negativos, etc. La ventaja que presentan estos sistemas es la fácil incorporación a los sistemas hardware existentes, ya que ambos se fundamentan en la electrónica y los circuitos integrados. Por otra parte, resulta una alternativa hardware para los sistemas de cálculo que existen, debido a que con los sistemas software, necesitan de otro entorno (sistema operativo, máquinas virtuales, etc.) para funcionar y, en cambio este dispositivo se conectaría directamente a la circuitería del dispositivo anfitrión.

Resolver el problema del camino Hamiltoniano.

Los sistemas de computación actuales se basan en una tecnología secuencial establecida por John Von Neumann a mediados del siglo pasado. Estos computadores secuenciales son buenos en la solución de problemas matemáticos, pero tienen dificultades en problemas denominados de llave en mano, donde se tiene que buscar todas las posibles soluciones hasta encontrar la solución adecuada. Esto hace que el tiempo de computación de los problemas pase a orden exponencial o logarítmico. Se han intentado paliar estos problemas con la construcción de computadores paralelos que puedan reducir el tiempo de computación. Estas soluciones consumen muchos recursos en comunicaciones y numero de nodos conectados entre sí. Por ese motivo ha mediado de 1994, Adleman presentó una nueva alternativa para programar con ADN

orgánico, este sistema orgánico presento un masivo paralelismo en la realización de las operaciones y por tanto en la obtención de los resultados finales, pero con las limitaciones comentadas anteriormente. Diseñó un sistema para resolver el problema del camino Hamiltoniano con programación con ADN orgánico y, por lo tanto demostrar que se podían resolver problemas NP-Completos en un tiempo computacional cercano al polinomial . A partir de este momento nació toda una nueva filosofía de programación con este material orgánico, la cual se denomino computación con ADN o programación molecular. Pero a lo largo de los años y debido a sus características del material, que principalmente es perecedero, los diferentes experimentos para traspasar la tecnología orgánica al mundo comercial fueron infructuosos. Para solucionar estos problemas, en este documento se presenta una solución con tecnología electrónica, en concreto con la tecnología JnChroSil, una propuesta artificial que emula el comportamiento de los sistemas orgánicos. Existen implementaciones paralelas para la solución del problema del camino Hamiltoniano pero necesitan un gran volumen de recursos y comunicaciones entre los nodos conectados. La ventaja que presenta el ADN inorgánico frente a las tecnologías secuenciales es el gran paralelismo en la realización de las operaciones, por ese motivo la invención resuelve de forma electrónica el problema del camino Hamiltoniano. Basándose en las características anteriormente expuestas, se codificó cada ciudad, los caminos y unas secuencias complementarias que servían para unir los caminos con hebras de ADN mediante la codificación expuesta en este documento véase figura 19 donde podemos ver el grafo 11 que representa el problema de Hamilton, donde los vértices están numerados del 0 al 6.

Este problema es de gran dificultad para problemas deterministas con orden polinomial, ya que es un problema

NP-Completo, pero se puede formular un algoritmo no determinista para la solución de este problema. El algoritmo no determinista se presenta en las siguientes líneas:

Entradas: Grafo, Vi _n y V _out

• Se generan de forma aleatoria todos los caminos existentes en el Grafo. • Se eliminan todos los caminos que cumpla con las entradas .

• También se eliminan todos aquellos caminos que no posean los vértices requeridos .

• Para cada vértice, se rechazan los caminos que no incluyan al propio vértice.

Salidas: SI (Existen caminos) NO (en caso contrario)

Por lo tanto en un ordenador convencional el tiempo de computación no puede ser polinomial, ya que se tiene que comparar todas las ciudades una por una para encontrar el camino desde una ciudad inicial V _in hasta una ciudad final

Vouf

El dispositivo electrónico que se explica a continuación, se planteó a partir del grafo de 7 vértices

11 de la figura 19. En ella se representa un grafo dirigido que poseerá un número determinado de aristas. El primer paso es la codificación de grafo de la figura 19 para ello se utilizó la codificación Cod- InChroSil (explicado en este documento) y se estableció que cada ciudad (vértice) tuviera un determinado número de nucleótidos, por ejemplo, 20 nucleótidos, y que las aristas estén compuestas por el mismo número, 20 nucleótidos, los cuales se corresponden con los 10 nucleótido últimos de un vértice o ciudad origen y los 10 nucleótidos iniciales del

vértice o ciudad destino. Por lo tanto, utilizando la tecnología InChroSil se creará una hebra en la cual se albergarán todas las aristas representadas en dicho grafo. Por otro lado, la hebra debe de poder codificar todas las aristas de un grafo completo de 7 vértices 11, por lo tanto, para dar versatilidad al experimento, dicha hebra ofrecería la posibilidad, que en el peor de los casos comparar un grafo completo (un Grafo completo es en Teoría de grafos, en un grafo cuyo conjunto de aristas contiene todas las aristas posibles, G= (V, VxV) , siendo V el conjunto que contiene todos los vértices del grafo) y, en el mejor de los casos, por ejemplo, el grafo expuesto en la figura 19. Esto permite al programador del circuito electrónico que realice la codificación, elegir tantas aristas como desease dentro del rango establecido por el propio grafo, es decir, para el grafo del ejemplo, existirá una hebra de 5040 pares nucleótidos (factorial de 7 si se consideran 7 ciudades) , de tal modo que, el programador solo exigirá la activación de la parte complementaria de la hebra en las aristas necesarias para el grafo a analizar. En este caso, solo se exigirá complementariedad con las partes de la hebra que correspondiesen a los estados que poseen arista del grafo de la figura 19. Por otra parte, a la codificación del grafo de la figura 19, se la denomina ¹ G ¹ 17 (Grafo) y que puede ver en la figura 20, en la que AO,

Al representan las aristas del grafo que une a los estados (Ei), y en la que EO, El son los estados o las ciudades del problema planteado.

De forma gráfica se puede ver en la figura 21 como están conectados los estados mediante aristas y en la figura 22 se detalla esta codificación utilizando cod- inchrosil. En la figura 21 un estado está formado por 20 nucleótidos y una arista se compone de los 10 nucleótidos finales de un estado y los 10 nucleótidos iniciales del estado siguiente.

El siguiente paso, consiste en poder disponer de todos los posibles caminos hamiltonianos existentes en un grafo de 7 vértices completo, por lo que se creó un conjunto de 5040 cadenas de ADN, por supuesto con la tecnología InChroSil, estas hebras estarán compuestas por 140 pares de nucleótidos (puestos que existen 7 vértices y cada uno de ellos debe estar representado por 20 pares de nucleótidos, se exigiría una longitud de hebra de la multiplicación de 7 por 20) . Estas hebras se dispusieron de forma matricial porque resultaba más cómodo para poder plantear un chip tridimensional, y seguir en la línea de poder emular la naturaleza orgánica. A esta codificación, de igual modo que con el grafo ejemplo, se denominó 'CG ¹ 18 (Conjunto de Grafos) . La teoría de conjuntos se utiliza especialmente para delimitar el alcance de una proposición, lo que fuerza al objeto de la proposición a quedar en cierta medida concretizado. Esto es deseable pues permite operar con la proposición formada, al principio como mínimo a nivel de cierto o falso y en un nivel máximo, de acuerdo a como corresponda la parametrización de las proposiciones establecidas, es decir un conjunto S está definido si, dado un objeto cualquiera α, se sabe con seguridad si pertenece o no al conjunto. Por lo que, esta teoría aplicada a este proyecto, permite comparar cada arista de ¹ CG ¹ de la figura 23 de un conjunto de hebras; que representan a todas las combinaciones posibles de los estados,- con cada arista especificada en el grafo ¹ G ¹ de la figura 20, de forma totalmente paralela, y determinando de este modo si dicha arista del grafo ¹ CG' pertenece o no al conjunto de aristas codificadas en el grafo ¹ G', por tanto las aristas del grafo ¹ G' se convierten en conjuntos y a su vez las aristas del grafo 'CG' se convierten en objetos de los cuales se debe saber con seguridad si pertenecían o no al conjunto expuesto por el programador, es decir, al grafo ¹ G', ya que

¹ CG ¹ son plantillas de posibles soluciones. Para poder realizar estas comparaciones, se aprovechó la filosofía de los semisumadores lógicos, sumadores sin propagación de acarreo (CSA) y árboles de Wallace. Estas tecnologías ampliamente reconocidas en el campo de la estructura de computadores, ofrecieron la posibilidad de crear modificaciones en los diseños para obtener el paralelismo exigido por el problema y de este modo obtener los resultados deseados. Por otra parte, como se observa en la figura 24, se puede apreciar la estructura interna de un semisumador lógico estándar.

Una modificación que se presenta en este documento es la eliminación del acarreo quedando solo la suma directa de las dos entradas, si se tiene en consideración la tabla de verdad de una puerta XOR, se puede apreciar que si los dos bits son iguales el resultado lógico es 0, por lo que en este proyecto se optó por negar dicha salida de este modo se trabajaría con lógica directa y no inversa. Debido a este planteamiento se desarrollo comparadores 12 mediante puertas XNOR 12a para la solución del problema. Por otro lado, el hecho de juntar 40 puertas XNOR 12a (puesto que, las aristas son de 20 pares nucleótidos, esto supone 40 bits por cada arista y por tanto 80 entradas, ya que se comparará dos a dos) , surgió de la idea de poder crear CSA (sumador sin programación de acarreo, el cual permite realizar sumas obteniendo como resultado la suma de los datos y el acarreo) , es decir la unión de puertas XNOR 12a dando un resultado único de 40 bits.

Pero estas puertas ofrecían un resultado de 40 bits, lo cual no era óptimo, por lo que se plantearon las siguientes preguntas ¿son todos los bits iguales? ¿Son la misma arista?, para ello se utilizo una puerta AND 12b de 40 entradas y 1 solo bit de respuesta, obteniendo en un solo dato la contestación a nuestras preguntas. Ya que si

esta puerta AND 12b, da como resultado lógico un ¹ I ¹ , significa que son iguales las aristas y, por tanto dicha arista perteneciente al grafo ¹ CG ¹ , y por lo tanto pertenecía al conjunto de aristas perteneciente al grafo 1G ¹ . En caso contrario, si el valor es ¹ O ¹ , significa que las aristas mencionadas no son iguales, pero no garantizan que no pertenecieran al conjunto programado, lo cual era un dato a resolver. Por tanto, se creó al igual que los CSA, un encapsulamiento del circuito, creando de este modo el comparador 12 mostrado en la figura 25.

Para poder resolver este problema, los comparadores 12 se establecen creando una matriz y comparando las aristas 13 y 14, dos a dos, de ambos grafos ( ¹ G ¹ y ¹ CG ¹ ) de forma paralela. Pero surge una nueva cuestión, ¿Cómo establecer si es camino o no?, para poder dar respuesta a esta pregunta se plantearon los ya conocidos árboles de Wallace, aunque no se utilizó su estructura si su filosofía de funcionamiento, la cual es crear diferentes niveles de exigencia para poder encontrar de forma totalmente paralela el resultado requerido.

Por lo tanto, se planteó que si se exigía que cada comparador en columnas de dicha matriz de comparadores, su resultado 12 de igualdad se dirigiera hacia una puerta OR 15, de tal modo, si cualquiera de los comparadores respondiese un 'I ¹ lógico, dicha puerta lógica 15 correspondiente a la columna, confirmaría de forma paralela la pertenencia de dicha arista al conjunto de las aristas programadas. De este modo se crean los mencionados niveles de los árboles de Wallace. Por último, todas estas puertas lógicas OR 15, que en este caso son tantas como columnas o aristas existentes en las hebras de ADN JnChroSil, pertenecientes al grafo ¹ CG ¹ , es decir, 6 puertas lógicas OR 15. De este modo si todas las aristas confirman la pertenencias al conjunto representan un camino Hamiltoniano, esto se consigue

dirigiendo todas las salidas hacia una puerta lógica AND 16, de esta forma se obtien definitivamente la respuesta ansiada, se ha creado así el último nivel de exigencias.

Finalmente, el resultado de la puerta AND 16 se almacena en un vector de Resultados no representado, de tal modo que este vector tendrán 5040, es decir, tantas como hebras de ADN InChroSil, han sido codificadas, por lo que las posiciones en las que se vea reflejado un ¹ I' lógico, reflejaría que la hebra codificada en dicha posición del vector es camino Hamiltoniano del grafo presentado, en la figura 26 en la que se muestra un esquema simplificado del circuito, y en la figura 27 podemos ver el circuito completo.

Resolver problemas de los llamados del viajante bajo.

El problema del viajante (traveling salesman problem TSP) , es uno de los problemas más famosos y mejor estudiados en el campo de la optimización computacional . A pesar de la aparente sencillez de sus planteamiento, el problema es uno de los más difíciles de resolver, debido a que es considerado de complejidad NP-Completo. La invención resuelve el problema del viajante con un sistema electrónico (sección anterior) , con un coste temporal del orden polinomial. En este sistema se tiene un grafo ponderado y dirigido, donde se obtienen todos los caminos hamiltonianos existentes en el grafo. Por lo tanto, en el caso más favorable, sólo existía un camino, pero en el caso contrario o polo opuesto, en el caso desfavorable, es decir, cuando se tiene un grafo completo, podemos tener todos los caminos hamiltonianos. Como ya se comentó anteriormente, el cálculo de todos los caminos se realizan de forma paralela, pero lo que no contemplaba el circuito de la sección anterior era el peso de las aristas, para resolver los problemas de Hamilton ponderado. La idea que

se plantea en este documento para dar solución a los problemas de Hamilton ponderado, es sencilla. Utilizando la misma infraestructura electrónica prevista para el cálculo de los caminos hamiltonianos, pero además teniendo en cuenta dos implementaciones; la primera implementación en la figura 28 es transferir esta información (caminos encontrados) a un sistema software 23, 26 que determina la correspondencia entre peso-arista. Este sistema, una vez obtenido el coste individual, calcula el coste total de cada camino. Para finalmente, cuando estén calculados todos los costes de todos los caminos hamiltonianos, ordenarlos según un determinado criterio (de menor a mayor, de mayor a menor, etc.) . Todas estas operaciones se tiene que tener en cuenta que la información esta codificada en Cod- JnChroSil y, que la asignación de pesos a las aristas y posterior cálculo de costes, no es un trabajo costoso a nivel computacional, ya que tiene tiempos polinomiales . Por último, el usuario o un sistema tendrá una colección de caminos ordenados, y entonces dependerá de esté, para la elección del mejor camino. En esta figura 28, la referencia 21 representa el circuito de obtención del camino Hamiltoniano, la 22 el interface de conexión con interface 25 de un módulo de tratamiento de datos 23, la referencia 24 es una base de datos y la 26 un módulo de cálculo de costes y ordenación. La referencia 27 representa un dispositivo externo de demanda de datos.

Por otra parte en la base de datos de la invención están almacenados los datos intermedios, es decir los pesos de las aristas, etc. Por lo que sirve de apoyo a los cálculos que se van a realizar o realizados.

Otra implementación se muestra en la figura 29, es la utilización de memorias 28 (Mein- JnChroSil u otro tipo de memoria) , la idea es que cuando se codifiquen los vértices JnChroSil y, por lo tanto se establezca el valor de las aristas que los unen, el sistema almacenara en esa

dirección de memoria (valor de la arista) , el valor del peso de esa arista en el grafo, es decir, se almacena en la arista no su valor o peso, sino la dirección de memoria donde está su valor, debido a que este valor puede ser un número muy grande y las direcciones tienen un tamaño establecido. Cuando se determinen los caminos hamiltonianos, mediante el circuito 21 anterior, se busca el valor de las aristas en la memoria 28, ya que como sabemos su dirección, sabremos su valor. Estos costes se sumaran y buscaran por mediación de circuitería, es decir un bus 32 y sumadores 30, para obtener el coste total de cada camino que puede ser almacenado en la memoria 28 con direcciones consecutivas. Al igual que en la anterior implementación, el usuario o el sistema que recibe de entrada esta información elige con que camino se queda, mediante criterios de elección, ajenos a los dispositivos descritos en este documento. En este ejemplo la referencia 22 representa el interface de conexión con un interface 25a del módulo de tratamiento de datos 23a, la referencia 29 el módulo de ordenación, la 31 un interface de conexión del módulo 23a con un dispositivo externo de demanda de datos 27.

Finalmente, indicar que también se pueden resolver problemas de ciclos hamiltonianos, para lo que habría que considerar la premisa que el vértice de salida es igual al vértice destino.

La Obtención de caminos eulerianos

Los caminos eulerianos son aquellos caminos que recorren todos los vértices de un grafo pasando una sola vez por cada arista del grafo, siendo una de las condiciones fundamentales que regrese al vértice inicial o de salida, por lo tanto, un camino euleriano es un ciclo que contiene todas las aristas de un grafo una sola vez.

Este problema fue planteado y resuelto por el propio Leonhard Euler en 1736 en un problema que tiene el nombre de los siete puentes de la ciudad de Kónigsberg. El problema se enuncia de la siguiente forma: Dos islas en el río Pregel, en Kónigsberg se unen entre ellas y con la tierra firme mediante siete puentes. ¿Es posible dar un paseo empezando por una cualquiera de las cuatro partes de tierra firme, cruzando cada uno de los puentes una sola vez?. Euler enfocó el problema representando cada parte de tierra por un punto y cada puente, por una línea, uniendo los puntos que se corresponden. Entonces, el problema anterior se puede trasladar a la siguiente pregunta: ¿se puede recorrer la representación sin repetir las líneas?, euler demostró que no era posible puesto que el número de líneas que inciden en cada punto no es par (condición necesaria para entrar y salir de cada punto) . Por lo tanto, este problema plantea preguntas como las siguientes; ¿Cómo se puede recorrer el cable de esta red eléctrica sin repetir tramos de red?, ¿Cómo se puede realizar este recorrido, pasando por unas calles concretas?, etc.

Como se ha visto, existe una complejidad en la resolución de estos problemas, por ese motivo se podría plantear el problema de forma inversa, es decir, lo que eran vértices se convierten en aristas y, las aristas se convierten en vértices. Con esta conversión, podemos aplicar o calcular los caminos hamiltonianos, puesto que ahora los vértices representan las aristas y, se quiere saber que secuencia de vértices debemos de seguir para poder pasar por todas las aristas. Supongamos el grafo dirigido y no ponderado de la figura 18, el cual sería un multigrafo, es decir, un autómata no determinista.

También se puede representar el grafo de la figura 18 de la siguiente forma, donde V ₁ es el conjunto de vértices y, Ei es el conjunto de aristas.

G ₁ =(F ₁ E ₁ ) siendo V ₁ = (vi,v _2# v ₃ ) y E ₁ = U ₁ , a ₂ , a ₃ , a ₄ , a _5/ a ₆ )

Además, tenemos las siguientes uniones de vértices, por medio de aristas;

U={ (V ₁ , V ₂ , ai) , (v ₁ ,v _2/ a ₂ ) , (Vi,v ₂ ,a ₃ ) , (v ₂ ,v ₃ ,a ₄ ) , (v ₂ ,v ₃ ,a ₅ ) , (v ₂ ,v _3/ a ₆ ) , (v ₃ ,v ₁ ,a ₆ ) }

Donde la nomenclatura utilizada para estas uniones es

(vértice origen, vértice destino, arista) . Si se realiza la inversión comentada y, se consideran las aristas como vértices y, los vértices como aristas, el grafo que se obtendría es el siguiente.

G ₂ = (V _{2 /} E ₂ ) siendo V ₂ = (a _α , a _{2 /} a ₃ , a ₄ , a ₅ , a ₆ ) y E ₂ =

( (V ₁ , V ₂ ) , (V ₂ ,V ₃ ) , (V ₃ , Vi) )

Además, se tienen las siguientes uniones de vértices, por medio de aristas,-

W = {(ai, vi, v2, v2, v3, a4) }

Por lo tanto el grafo tendrá la forma que se muestra en la figura 18. Por consiguiente si se obtiene el camino hamiltoniano del anterior grafo G ₂ , se puede afirmar que existe una solución o camino euleriano G ₁ . También si se considera que el grafo es ponderado, se puede calcular el coste total de cada uno de los caminos y, por lo tanto ordenarlos por coste, aunque los caminos eulerianos no poseen peso, podrían plantearse nuevos problemas de optimización en los caminos eulerianos. En conclusión, si existe camino hamiltoniano en el grafo G ₂ , se puede afirmar que existe un camino euleriano en el grafo G ₁ . Por último, se puede afirmar que se pueden resolver ciclos eulerianos,

para lo cual, en la codificación de la base de hebras o bancos de hebras, se establecía que el nodo inicial fuese el mismo que el final. De este modo, mediante la invención se pueden resolver problemas de ciclos.