Download emulación de chip adn en cellmatrixtm

EMULACIÓN DE CHIP ADN EN CELLMATRIXTM
A. Cubillos, T. Suárez,
Estudiantes Ingeniería Electrónica
A. Delgado
Profesor - Investigador
[email protected]
Departamento de Ingeniería Eléctrica y Electrónica
Universidad Nacional de Colombia, Bogotá
SUMMARY
In this paper we present the design and simulation of a rule based controller using the principle of DNA chips, the system is
illustrated with a mobile robot that has two sensors and two motors. The controller is implemented in the cellmatrixTM
software using a matrix of interconnected cells to perform basic tasks.
RESUMEN
CellmatrixTM es un software que permite diseñar y simular una matriz de células, estas celdas están interconectadas de tal
forma que pueden trabajar de dos modos: modo dato y modo configuración. El programa se divide en un simulador y en un
editor, en el editor se implementan las funciones deseadas del diseño y en el simulador se puede observar el
comportamiento obtenido. En este artículo se describen los diseños y simulaciones en el programa Cellmatrix para un
sistema inspirado en un chip de ADN con el propósito de controlar la navegación de un robot móvil con dos sensores y dos
motores.
EMULACIÓN DE CHIP ADN EN CELLMATRIXTM
A. Cubillos, T. Suárez,
Estudiantes Ingeniería Electrónica
A. Delgado
Profesor - Investigador
[email protected]
Departamento de Ingeniería Eléctrica y Electrónica
Universidad Nacional de Colombia, Bogotá
RESUMEN
Se estudia la emulación de un controlador tipo chip ADN
en el programa CellMatrixTM (CM) utilizando su estructura
de celdas configurables. Esta matriz de celdas es aplicada
en la integración sensorial y evaluación de reglas de un
robot móvil.
1. INTRODUCCION
En la actualidad resulta sencillo emular el comportamiento
biológico de los chips ADN, su principal ventaja es el
paralelismo con que procesa
los datos de entrada. Utilizar
la estructura de los chips
ADN
en un dispositivo
electrónico minimiza los
ciclos de reloj en la ejecución
de un programa, es por ello
que en robótica podemos
emular la operación de los
chips de ADN para tareas
como integración sensorial y
evaluación
de
reglas
explotando el paralelismo de
los circuitos configurables.
En CM se puede emular el
chip ADN, pues es un
programa gráfico para el
diseño de circuitos que utiliza
celdas
bidimensionales
Fig. 1. ADN, las bases
configurables. Cada celda
nitrogenadas siguen una
posee cuatro lados, en cada
secuencia, a lo largo de
lado hay una entrada de datos,
una estructura de fosfatos
una entrada de control, una
y azúcares.
salida de datos, y una salida
de control (en total 8 entradas
y 8 salidas), cada celda tiene una tabla de verdad que
caracteriza su comportamiento.
El artículo se divide en 6 partes, en la primera se explica
brevemente la estructura chip ADN originalmente
desarrollado para estudios en biología molecular, en la
segunda se presenta el funcionamiento del chip ADN
electrónico, en la tercera se presenta el programa CM, en
la cuarta se describen las simulaciones en CM para la
unidad básica del chip de ADN, en la quinta se muestran
las simulaciones para un chip de ADN de 4 reglas, y en la
última sección se presenta el diseño completo del
controlador chip ADN para el funcionamiento de un robot
móvil.
2. CHIPS DE ADN
Toda la información genética de los seres vivos se
encuentra contenida en su genoma, el genoma consiste en
una colección de cadenas largas de Acido
DeoxirriboNucleico (ADN) asociadas con moléculas
proteínicas que se organizan en una estructura biológica
llamada cromosoma. El ADN esta constituido por
azúcares, fosfatos y bases nitrogenadas. Existen cuatro
bases fundamentales en el ADN: la Timina (T), la Adenina
(A), la Citosina (C ), y la Guanina (G); la secuencia
particular de estas bases dentro de la estructura determina
toda la información genética. En una hélice de ADN las
bases se enlazan por pares, a saber Adenina con Timina y
Citosina con Guanina, esto se denomina el complemento
de Watson - Crick. Una estructura de ADN se presenta en
la figura 1.
Un Chip de ADN es un arreglo matricial de cadenas
sencillas de ADN, las cuales han sido implantadas en una
base de vidrio por medio de diferentes técnicas, una de
ellas la fotolitografía.
En el chip ADN hay cadenas sencillas de ADN que al
incubarse con cadenas complementarias fluorescentes,
inyectadas al chip, forman hélices de ADN que se pueden
detectar por medios ópticos o electrónicos. La formación
de una hélice de ADN a partir de dos cadenas sencillas se
conoce como hibridación, el orden de las bases en una
cadena sencilla se denomina secuencia.
En biología los chips ADN se aplican para el diseño de
nuevos fármacos, estudios toxicológicos, e investigaciones
con impacto en la agricultura. En ingeniería se ha
demostrado que los chips ADN se pueden utilizar para
almacenar y evaluar, en paralelo, bases de reglas Boolenas
o difusas [1].
3. CHIP DE ADN ELECTRÓNICO
Para diseñar el chip de ADN electrónico la información de
entrada se codifica como cadenas binarias de L bits
correspondientes a las lecturas de los sensores, un
conversor A/D puede realizar esta tarea. La celda básica de
un chip ADN en electrónica digital se muestra en la figura
2.
La celda tiene dos registros, el primero corresponde al
dato externo (target = objetivo) y el segundo al dato
almacenado (probe = prueba), la similitud entre los datos
se calcula mediante la operación XOR. Únicamente
cuando el dato de entrada y el dato almacenado son
complementarios la bandera se activará (hibridación) [2].
4. CELLMATRIXTM
CM es un programa desarrollado por N. Macias [3] y
consiste en una red bidimensional de células cuadradas
configurables, cada una con cuatro vecinos inmediatos, en
donde cada lado de la célula posee dos líneas de entrada y
dos líneas de salida, una de estas entradas contiene un bit
de Dato (Din) y la otra contiene un bit de Configuración
(Cin), lo mismo ocurre con los bits de salida Dout y Cout.
En modo dato los cuatro bits Din son usados como
dirección en una tabla lógica de 16 x 8 bits. Si al menos
una entrada Cin esta activada entonces la célula cambia a
modo configuración, en este caso la célula puede
modificar la tabla 1ógica y el modo de su célula vecina. Al
interactuar de esta forma con sus vecinos puede llegar el
caso que se reconfigure a sí misma al realimentar
posteriormente las señales. El programa se divide en un
simulador y en un editor, en el editor se implementan las
funciones deseadas del diseño en notación polaca inversa
(RPN) y en el simulador se puede observar el
comportamiento obtenido.
5. UNIDAD BÁSICA DE CHIP ADN
Fig. 2. Celda del chip ADN electrónico. Los datos son
complementarios cuando la bandera se activa en uno.
A partir de la unidad básica se puede elaborar un chip de
ADN de N reglas, en el cual se almacena una matriz entera
de datos de prueba. En la figura 3 se puede observar un
ejemplo de chip ADN de 4 reglas.
La estructura básica del chip ADN, fue implementada
en el programa CM, dejando en claro su funcionamiento.
Para su implementación se llevo a código la estructura
mostrada en la figura 2 en una sola célula, para ello se
realizó una operación XOR entre las entradas Sur y Norte
de las células de la matriz y posteriormente a este resultado
se le efectúo una operación AND con la entrada West que
indica si una cierta pareja de bits de los registros objetivo
y prueba son complementarios. Como la operación se
realiza bit a bit entre estos dos registros entonces si West
es cero deshabilitará automáticamente la bandera, habrá
tantas células programadas de esta forma como bits posean
los registros objetivo (entrada de sensores) y prueba. En
este caso se simuló una celda base de 2 bits, en donde para
poder configurar cada estructura fue necesario llevar las
entradas sur de cada una de las celdas, correspondientes al
registro de 2 bits, a las entradas del lado izquierdo de la
matriz. El diseño en el editor se muestra en figura 4.
Fig. 4. Celda de chip ADN realizada en el editor de CM. Se
compara la señal entregada por los sensores del robot móvil con
un registro de 2 bits del chip de ADN, si las entradas son el
complemento del registro de prueba se activa la bandera.
Fig. 3. Base de reglas para dos entradas [X1 y X2]. Las
banderas de las cuatro reglas permiten seleccionar las
salidas.
La ecuación del bloque principal de la figura 4 es
DE = ( N • S + N • S ) • W , que en RPN es DE= (N~S&
S~N&+)W&. La simulación realizada se muestra en la
figura 5.
Sensores
A11= 00, A21= 01, A31=10, A41 = 11,
= 10, A32 = 01 y A42 = 00.
A12 = 11, A22
Bandera
Registro de
Pruebas
Fig. 5. Simulación de la unidad básica del chip ADN en CM.. El
registro de prueba es [0 1] y el registro objetivo es [1 0], como
son complementarios se activa la bandera por el cumplimiento de
esta regla. La representación de un 1 lógico se muestra como una
flecha gruesa.
6. CHIP DE ADN DE 4 REGLAS
Para el diseño de este circuito se utilizó la unidad básica
del chip de ADN y se implementó la estructura de la figura
3. Se utilizaron celdas de conexión para las entradas de los
registros de prueba, las entradas de los registros objetivo, y
las salidas de las banderas. En la figura 6 aparece el
diagrama de la estructura chip ADN de cuatro reglas
diseñado en el programa editor.
Fig. 7. Simulación de un chip ADN de 4 reglas y 2 bits. El
complemento correspondiente a las entradas de los sensores
X1= 0 1 y X2 = 1 0, es respectivamente A31 = 1 0 y A22 =
01, por lo cual se activa la bandera dos.
7. MAPA DE ENTRADA /SALIDA
Con el chip ADN emulado desea controlar el movimiento
de los motores (y1, y2) de un robot móvil según las
lecturas de los sensores (x1, x2), figura 8.
Fig. 8. Robot móvil con 2 entradas [x1, x2] (sensores) y dos
salidas [y1, y2] (motores). El controlador es una base de reglas,
como chip ADN, que actúa en paralelo produciendo acciones
dependiendo de las lecturas de los sensores.
Fig. 6. Implementación del chip de ADN de cuatro reglas y 2
bits, se indica el lugar en donde se encuentra la salida de las
banderas.
Es preciso aclarar que las entradas Aij son los registros de
prueba, figura 3. En la figura 7 se muestra la simulación
correspondiente para valores de los registros de prueba
Las banderas de la base de reglas del chip activan unos
registros de salida para completar el procesamiento
Entrada/Salida (E/S) sensores → actuadores, el
controlador completo se muestra en la figura 9,
observamos que para ciertas entradas de los sensores (X1,
X2) habrá una salida (Y1,Y2) según la configuración de
los registros de prueba del chip ADN y de las reglas [2].
En nuestro desarrollo los vectores de prueba del chip
ADN ( A11, A21, A31, A41, A12, A22, A32, A42) son de
dos bits y los registros de acción (C11, C21, C31, C41,
C12, C22, C32, C42) son de un bit, por facilidad a cada
motor se le enviará una señal binaria de movimiento
(0 hacia atrás y 1 hacia delante). En general los registros
de prueba y de acción pueden tener cualquier número de
bits según la aplicación [2].
Fig. 10. Primera parte del sistema chip ADN implementado en
CM. Las banderas Fi se decodifican para producir S1 y S0, que
son las líneas de selección del multiplexor.
S1
S0
Fig. 9. Mapa E/S. El vector de banderas selecciona el
consecuente de las reglas activas.
En la figura 10 se presenta la primera parte del sistema
chip ADN implementado en el editor de CM, en ella se
especifican las entradas (X1, X2), los vectores de prueba
Aij y las banderas Fi. Los Fi se decodifican para producir
S1 y S0, que son las entradas de selección del multiplexor.
Fig. 11. Segunda parte del controlador ADN en CM. Se
encuentran los módulos del decodificador, el multiplexor, los
registros de acción Cij, y las salidas de los motores Y1 y Y2.
En la figura 11 se muestran, en CM, los restantes
componentes del controlador, figura 9. Se pueden apreciar
el decodificador, el multiplexor, los registros de acción, y
las salidas de los motores Y1 y Y2.
Hay dos clases de multiplexores para la apropiada
transmisión de los consecuentes Cij, en el primero se
procesan las reglas de acción C1j y C2j, en el segundo se
manejan los datos C3j y C4j, para luego obtener la salida
haciendo una OR entre los resultados de estos. La
simulación correspondiente aparece en la figura 12, para
los datos de la Tabla 1.
X1
A11
A21
A31
A41
C11
C21
C31
C41
00
00
01
10
11
0
1
1
1
X2
A12
A22
A32
A42
C12
C22
C32
C42
11
11
10
01
00
0
0
0
1
Tabla 1. Datos para el controlador con chip ADN.
Los complementos de las entradas X1 = 00 y X2 = 11 son
A41 = 11 y A42 = 00 respectivamente, por ello la bandera
activa es F3, y la decodificación es S1 = 1, S0 = 1. Estos
selectores del multiplexor escogen la salida final C41=1 y
C42 =1, ver figura 12.
9. REFERENCIAS
[1] Delgado, A.: DNA Chips as Lookup Tables for Rule
Based Systems, IEE Computing and Control Journal, 13,
113-119, 2002. Disponible en el sitio web:
www.iee.org/OnComms/pn/material/library.cfm.
[2] Delgado A. Robot Controller Using Electronic DNA
Chip, Memorias Congreso Internacional de Ingeniería
Eléctrica y Electrónica, Bogotá, Marzo, 2003.
[3] Macias Nicholas. “Documentation For The Cell
Matrix™ Layout Editor”. Disponible en el sitio web :
www.cellmatrix. com/ entryway/ core.html.
[4] Wang Bin. “Implementation of a dynamic
programming algorithm for DNA sequence alignment on
the Cellmatrix  αrchitecture”. Disponible en el sitio web
: www.cellmatrix.com/entryway/core.html.
Fig. 12. Simulación del controlador basado en chip ADN. Para
las entradas de los sensores [X1 = 00, X2 = 11] se activa la
bandera F3, y su decodificación determina las reglas de acción
C41 y C42.
8. CONCLUSIONES
El control de un robot móvil se puede lograr mediante un
sistema inspirado en los chips de ADN [2]. El controlador
posee un bloque que recibe las lecturas de los sensores y
dependiendo de las reglas programadas en el chip,
determina las señales que deben tener los motores. El
sistema es útil debido a su paralelismo.
Una herramienta interesante para estudios en robótica
evolutiva es el simulador CM, que debido a su
configuración matricial permite implementar circuitos
donde hay múltiples interacciones entre unidades básicas.
Las simulaciones permiten verificar el diseño y examinar
la forma cómo se transmiten las variables.
La principal dificultad con el CM es que sólo se puede
tener acceso a las entradas de las células periféricas, es por
ello que resulta complicado propagar por medio de células
transmisoras las entradas y salidas desde el perímetro de la
matriz. Es necesario entonces tener un orden estricto para
no confundir las entradas y salidas.