COMISIÓN NACIONAL GE INVESTIGACIÓN W CIENTÍFICA Y …

tCoNICyT COMISIÓN NACIONAL GE INVESTIGACIÓN

W CIENTÍFICA Y TECNOLÓGICA En GOBIERNO DECHILE

COMISION NACIONAL DE INVESTIGACION CIENCIA Y TECNOLOGIA

VERSION OFICIAL

FECHA: 22/03/20 10

PROYECTO REGULAR N°1070022

INVESTIGADOR RESPONSABLE: ERIC ANTONIO GOLES CUACC

FONDO NACIONAL DE DESARROLLO CIENTIFICO Y TECNOLOGICO (FONDECYT) Bernarda Morin 551, Providencia - casilla 297-y, Santiago 21

Telefono: 435 43 50 FAX 365 4435

Email: informes.fondccytconicyt.cI

INFORME FINAL

PROYECTO FONDECYT REGULAR

N° PROYECTO: 1070022 DURACIÓN: 3 a6os AÑO ETAPA: 2009 TÍTULO PROYECTO: COMPLEX SYSTEMS: STRUCTURE, DYNAMICS AND APPLICATIONS IN BIOENGINEERING

l)ISCIPLINA PRINCIPAL: INGENIERIA EN COMPUTACION

GRUPO DE ESTUDIO: INGENIERIA 2

INVESTIGADOR(A) RESPONSABLE: ERIC ANTONIO GOLES CHACC DIRECCIÓN: LUZ 2965, DEPTO-302

COMUNA: Las Condes

CIUDAD: SANTIAGO

REGIÓN: METROPOLITANA

FONO: 3693660

EMAIL : [email protected]

INFORME

OBJETIVOS

Cumplimiento de los Objetivos planteados en el Proyecto. Recuerde que los objetivos del proyecto no se refieren a listar actividades desarrolladas sino a los obietivos desarrollados

No OBJETIVOS CUMPLIMIENTO FUNDAMENTO Se pretendia obtener avances en el inodelamiento TOTAL

de redes de interacción génico metabólico ( redes

boolcanas tyratadas mediante diferentes tipos de

iteración): Esto se logró a cabalidad, llegando a

obtener una clasificación ( con resultados

exactos) del tipo de iteraciones que para una red

dada producte tal ocual comportamiento, generaqndo clases de equivalencia de comportamientos similares. 'I'ainbiéii, descde el

punto de vista de complejidad en procesos

discretos se lograron avances

importantes

Otro(s) aspecto(s) que Ud. considere importante(s) en la evaluación del cumplimiento de objetivos planteados en la propuesta

original o en las modificaciones autorizadas por los Consejos.

LO anterior ( figura como # 1) corresponde al objetivo total del proyecto: esto se lograron via

varios trabajos cientificos (13 entre proccedings y papers publicados y enviados), la formación de un doctor ( Dr. Lilian Salinas),

actual académmca de la U de Concepción y otro en curso ( M. Noual, Ec. Normale Superieure de Lyon. France) y la participación en

diversos workshops, congresos y seminarios nacionales e internacionales.

RESULTADOS DEL PROYECTO

1. Dada una red boolcana de regulación de tamaño n (número de nodos) con circuitos no negativos (cada negación equivale a una entrada lógica -'x) se determinó un algoritmo 0(12 2 ) para construir una nueva red que mantiene invariantes los puntos

fijos y elimina todos los ciclos que aparecen en la dinámica. Por otra parte, es sabido que la determinación de un punto fijo es un problema NP-completo en redes arbitrarias. Como un corolario del resultado anterior, es possible determinar, para redes sin circuitos negativos, al menos un punto fijo en tiempo polinomial. Esta suerte de filtro no sólo tiene un interés teórico, además, al obtenerse datos de laboratorio de expression de genes, a menudo se desea determinar la estructura de la red de regulación con respecto a los atractores que son puntos fijos (la exprcssion de la red), sin que aparezcan ciclos expureos. El algorítmo presentado es entonces una alternativa práctica (Goles, Salinas, Sequen/ial Opera/urs for liering cycles iii Boolean Networks, December 2008).

2. En el contexto más general de redes metabólicas de regulación. Se estudió la relación entrre la componente génica de la dinámica (redes booleanas) y la regulación metabólica propiamente tal. Estos resultados aparecen en el trabajo Discrete ,natheniatical model applied to Gene/fc Regula/ion cuid Metabo lic Networks. (Asenjo, J.A., Ramirez. P., Rapaport, 1., Aracena, J., Goles E., and Andrews, J. of Microbiology and Biotcchnology, 17(3), 496-510, 2007)

3. También para redes booleanas de regulación se demostró, bajo hipótesis razonables, que para diferentes maneras de actualizar la red, en este caso en paralelo y secuencial, los ciclos son necesariamente distintos. Esta constatación que intuitivamente parece simple no lo es. De hecho, desde el inicio de este tipo de estudios en la década del 80 ( Francois Robert, Discrete lterations, Springer, 1983) no se habían obtenido resultados en esta dirección. El primero de ellos es el que aparece en nuestro trabajo Coínparison hetween parallel and serial dvna,nic,v of hoolean networks (Goles, Salinas, Theor. Comp. Sciences 347-53, 2008).

4. Para el caso particular de redes de regulación génica asociadas al modelo de la planta Arabidopsis Thaliana, se demostró que el modelo clásico es equivalente a una red neuronal simétrica. Esto permite asociar una energía a la dinámica paralela o secuencial de la red y entender por qué aparecen sólo puntos fijos y ciclos de período dos. (ver Dernongeot, Goles, Sené, Loss of linearity and synunetrisation in regulato#y networks, in Procc of AINA-IEEE workshop. Bradford, UK, May 2009).

5. En un contexto similar, redes que aceptan una energía, en este caso denominadas neuronales artificiales, se pone en evidencia la relación entre éstas y modelos cognitivos más reales en ci artículo Dynwnical Coniplexi!y in cognitive neural networks, (Goles, Palacios, Biological Researcli 40:38 1-384, 2008).

6. También se analiza la robustez frente a cambios locales en la topología d la red, así corno la complejidad de caracterizar estos cambios, en Attraction has ms as ganges of environinenial rohustness in hiological coinplex systems (Demongeot, Goles, M. Noual, Sené. Enviado, Dec 2009, a la revista electrónica PLOS, Computational Biology).

7. La robustez en relación a diferentes modos de iteración de la red (existe un número exponencial de posibilidades) fue estudiada con bastante profundidad y se

establecieron condiciones para que, dada una red fija, dos modos de iteración diferentes determinen la misma dinámica. Esto llevó a establecer conceptos de robustez, que permiten estudiar lo que se puede cambiar en el orden en que se actualizan los nodos de la red de modo que no se altere el comportamiento dinámico de la misma Estos resultados aparecen en Qn the robustness of update schedules in boolean networks, (Aracena, Goles, Moreira, Salinas, BioSystcms, 97, 2, 1-9, 2009).

8. En el marco de la Complejidad Comunicacional (CC; esencialmente la minima información que deben intercambiar dos individuos de la red para realizar un cálculo), se consolidó en este proyecto una relación original y muy promisoria entrrc CC y Autómatas Celulares, AC. Se establecieron dos resultados que a mi juicio abrieron el tema hacia el interés de la comunidad. El primero de ellos es que existen automatas celulares con CC no evidente: ni la minima (CC constante, independiente del tamaño del mensaje), ni la mayor, Q(n) (esencialmente que no se puede comprimir la información)). Se demostró que existe una clase de complejidad, Iog(n2). (Goles, Rapaport, Little, Undeitanding a non trivial CA bv

finding sirnplesf under/yi ng coinmunicalion protocoles, in Lcctures Notes in Computer Scicnces, 5369, Springer-Verlag, 2008). Por otra parte se estableció una relación entre Universalidad Intrínseca, (i.e. la capacidad de un AC de simular cualquier otro) y CC. Se demostró que si un AC es intrinsicamcnte universal cntonces su complejidad coinunicacional es maxima, Q(n). Esto establece una vía, mediante una cota inferior, para descartar AC en cuanto a su universalidad, convirtiendose así en una herramienta interesante para el análisis del poder de cálculo de AC's. (Goles, Meunier, Rapaport, Theyssicr, Coininunication ConipIexity, and In/rinsic Universalitv in Cellular Autoinata, por aparecer en Thcoretical Computer Sciences.). Finalmente en CC se estableció un nuevo problema de comunicación en AC, Traced Coinminunication y se presentaron los primeros resultados en la conferencia sobre AC en Sao Paulo (Goles, Guillon, Rapaport, Traced comniunication coniplexily ?f cel/ular autoinata, in Automata2009, Sao Paulo, Brasil)

9. Otra aproximación a la capacidad de cálculo, y por ende a la complejidad de procesos discretos, es vía la simulación, en AC bidimensionales de circuitos lógicos mediante aprovechando configuraciones dinámicas del automata. En este contexto, se estudiaron varios casos, demostrando, ya sea la imposibilidad de simular tales circuitos o la P-completitud (la posibilidad de simularlos). (Gajardo, Goles, capítulo de libro, Ce//alar Automata,Circuit Coinplexiy, Universality and relaled topics, Invited paper for the 60's birthd of G. Chaitin, World Scientific, C. Calude (cd), 2007).

10. También se obtuvieron otros resultados en dinámica y complejidad de sistemas discretos: una discusión sobre la complejidad de máquinas de Turing ((Goles, L arrét impossihle, Procc. Colloque de Cerisy, in "Déterminismes et complexités: autour de Henri Atlan", Rccherches, La dccouvertc, pp 77- 82, P. Bourginc et al eds, Paris, 2008); El estudio de recubrimientos del plano bidimensional por un cierto tipo de baldosas (Goles, Salinas, Covering hy squares, in TCS 396, 1 0-

27(2008); el estudio de flujo granular y las puertas de un recinto que permiten que los

agents salgan en tiempo razonable en caso de pánico (Zclenski, Goles, Markus, Maximisation of granular oulJlow by oblique exits and bIv obstacles, in Physics of Fluids 21, 031701, Amer Inst. of Physics, 2009).

FORMACION.

En el curso del 2008 sostuvo su tésis doctoral en Modelamiento Matemático, en la Facultad de Ciencias Físicas y Matemáticas de la la Universidad de Chile , mi alumna Lilian Salinas Ayala. Los temas tratados fueron la comparación de modos de iteración discretos. También hay un capítulo dedicado al embaldosamiento del plano. De su tesis se han escrito varios trabajos, todos aceptados para publicación o ya publicados.

En el curso del año 2009 comenzó a trabajar conmigo la alumna de la Escuela Normale Supericure de Lyon, Francia, Mathilde Noual, la cual realizó una estadía de dos meses en Chile. El tema de trabajo es la robustez de redes booleanas y en la actualidad comienza su doctorado bajo mi co-dirección ( con un colega Francés).

En el proyecto se estudio la dinámica y complejidad de modelos de redes de interacción discreta. La mayoría de ellas relacionadas con redes de interacción génico-inetabólicas. El problema general se puede enunciar de la manera siguiente: Estudiar la dinámica de un conjunto finito de "genes" interconectados entre si, que pueden estar presentes o ausentes ( 1 o O) y cambian de estado (de acuerdo a los estados de los genes con que intcractua) de manera determinista y siguiendo una función lógica (booleana). Los genes se pueden actualizar de muchas maneras: todos al mismo tiempo (en paralelo), uno tras otro (secuencial) o, en general, por bloques (algunos grupos en paralelo, otros secuencialcs, etc). Existe un número exponencial de maneras de actualizarlos y por lo tanto de diícrentes dinámicas de la red. En el proyecto se estudió qué había tienen en cornun distintas actualizaciones, qué pasaba con cambios pequeños en el modo de actualizar la red (robustez). Cambiaba mucho la dinámica, sólo algunos atractores 9 .....Se respondió con profundidad, bajo hipótesis razonables del tipo de funciones lógicas en cada nodo de la red, y se utilizaron los resultados para analizar a red génica de la planta Arabidopsis Thaliana. También se estudió la complejidad en un ámbito más general de redes. Se estudio una relación entre complejidad coniunicacional y complejidad coinputacional. Las complejidad comunicacional es esencialmente la siguiente: dados dos interlocutores, cual es la minima información que uno entrega al otro para llevar a cabo una tarea específica. En cuanto a la complejidad computacional, pensemos que es el costo,dc acuerdo al tamaño del problema, del algoritmo: cuánto se demora. Demostramos en el curso de este proyecto que una gran complejidad computacional implica una también gran complejidad comunicacionaL Esto que parece intuitivo no lo era y abre una vía para el estudio de la complejidad y dinámica de redes, muy en particular en automatas celulares ( redes uniformes con la misma función lógica en cada nodo)

PRODUCTOS

ARTICULOS Para trabajos en Prensa! Aceptados/Enviados adjunte copia de carta de aceptación o de recepción.

N°:

Autor (a)(es/as) : goles E., Salinas,L.

Nombre Completo de la Revista : Theorctical Coniputer Science

Título (Idioma original) : Comparison between parallel and serial dynais of booleati nctworks

Indexación : ISI

ISSN:

Año: 200

Vol. : 396

Páginas : 247-253

Estado de la publicación a la fecha : Publicada

Otras Fuentes de financiamiento, si las hay

Envía documento en papel : no

Archivo Asociado al artículo : ThcorcticalComputerScience2008L.pdf

hltp ¡evalcvl .cohllcvt .ct;i a forlac a rn cadcico/lI1dex.php/Lnvesflgador"t4 articulo/dcscarga/6097 5610700222009/6942

2

Autor (a)(es/as) : Goles, E., Palacios A.

Nombre Completo de la Revista : Biological research

Título (Idioma original) : Dynainical cornplexity in cognitive neural networks

Indexación : ISI ISSN: 0000

Año: 200v-

Vol.: 40

N°: 4

Páginas: 479-485




Archivo Asociado al artículo : Biologicalrcscarch_2007_E.pdf

http:!!cvalcyl conicyt.clÍin6irnic a a1eriicoJiiidw.php/invcstgador/I4 irtictilos/dcscargai6o97 86/1070022/2009/6944

N°:

3

Autor (a)(es/as) : Aracena J, Goles E, Moreira A, Salinas L.

Nombre Completo de la Revista : BioSystenis

Titulo (Idioma original) : On the robustncss of update schedulcs in boolean networks

Indexación : ISI

SSN:

Año: 2009

Vol.: 97

97

Páginas : 1-8




Archivo Asociado al artículo: biosysiems 2009 J.pdí

hIip:/ akylcuntcvl hin íoriiic acaiheniico/indcx.php/in csligadoi/14 articiilosdcscatga/6097 I 56/ 07002212009/69481

N°: 4

Autor (a)(es/as) : Zclinski. B., M Markus, M.,Golcs E.

Nombre Completo de la Revista : Physics of Fluids, Amer lnst of Physics

Título (Idioma original) : Maximisation of granular outflow by oblique cxits and by obstacles

Indexación : ISI

ISSN : 0000

Año: 2009

Vol.: 21

N°: 21

Paginas: 31701-31704




Archivo Asociado al artículo : 2009_B.pdf

hiIip:»caIcytconicvi.cI 'informe acadeiriicoindc. php'invcstigadorif4 arttcuho'descarga'6097 186/1070022/20(19/6954/

N°: 5

Autor (a)(es/as) : Asenjo.J., Rainircz,P.,Rapaport,l.,Araccna, J:,Goles, E., Andrcws,B.A.

Nombre Completo de la Revista: Journal of Microbiology and Biotechnology

Título (Idioma original) : A discreic Mathernatical model applied (o gcnetic tcgulation and rnciabolic nctworks

Indexación : ISI

ISSN: 0000

Año : 2007

Vol.: 17

3

Páginas: 496-510



1 Envía documento en papel : no

Archivo Asociado al artículo : journal_of_microbiologyandbiotechnologyjoo7A.pdf

ttp:i'cvalcyt.conicytcIíinIornie acadeniico/mdexphp/'uivestigidoif4 ai'ticulos/descargaí6097 86/1(170022/2009/6958/

N°:

Autor (a)(es/as)

Nombre Completo de la Revista

Título (Idioma original)

Indexación

ISSN:

Año:

Vol.:

6

Salinas L. Goles E.

Theoretical Cornputer Science

Covering by squares

0000

2008

396

N°: j- 1-5 Páginas : 10-27




Archivo Asociado al artículo : Coveringby_squares.pdf http:/./evalcvt.coiitc\tcl!tnforrne 1cademicohndc. php/invesiigador/f4 articuIo!desc,trg;i:6097 1 S6/1070022/20096959;

7

Autor (a)(es/as) : (Joles,E., Rapaport 1., Little, C.

Nombre Completo de la Revista : Lectures Notes iii Computcr Sciences

Título (Idioma original) : Undcrstanding a non-trivila cellular autoniaton by finding its siinplest underlaying

communication protocol

Indexación : Otras Revistas Especificar : Iii Computer Scicnces Lecures Notes ... ms so

important as and ISI publication. Ini 001 sure if

it 1

ISSN : 0000

Año : 2008

Vol.: 5369

N°: 5369

Páginas: 1-12


Otras Fuentes de linanciamiento, si las hay

EN COMIUTERR SCIENCES, SERF ACEPTADO EN ALGUNAS CONFERENCIAS CON

ESTRICTOS SISTEMAS DE EVALUACIÓN Y ACEPTACIÓN ES AL MENOS EQUIVALENTE A PUBLICAR

EN UNA REVISTA ISI. LAS CONFERENCIAS INDEXADAS ASI NO SON ARBITRARIAS. LA QUE 1)10

ORIGEN A ESTA PUBLICACION ES ISAAC 2008, QUE SE REALIZÓ EN AUSTRALIA.


Archivo Asociado al artículo : C.Complexity218.pdf

http:»e alciconicvt.cI/in lonnc acadeinicoindcxphp/investigador/I4 articulos dcscargaí6097 186 1070()2220()96961

Autor (a)(cs/as)

Nombre Completo de la Revista:

Título (Idioma original):

Indexación

ISSN:

Año:

Vol.:

8

Golcs,E., Salinas,L.

Advances in Applied matliernatics

Sequential Operators for filtering cycles in Boolean networks

'SI

0000

2009

N°:

Páginas:

Estado de la publicación a la fecha : Aceptada



Archivo Asociado al artículo : FILTROS.pdf

htip:/icvakyt.conicyt.cItnforme aca&lemhoIndcx.php/in\csllgadorf4 arlicuIodescarga/6097IS6/1070022!2009.1963'

OTRAS PUBLICACIONES

Autor (a)(es/as)

Dernongeol, J., Goles, E, Sené. S.

Título (Idioma original) : Loss of Iincarity and symmetrisatlon in regulatory nelworks.

Tipo de publicación o producto : Libro

ISBN : 0000

Editor (es) (Libro o Capitulo de libros) AINA-IEEE workshop.eds

Nombre de la editorial /Organización : IEEE

País: REINO UNIDO I)E GB E IRLANDA DEL NORTE

Ciudad : Bradford

Fecha : Mayo - 2009

Año: 2009

Vol.:

Páginas:

Otras Fuentes de tinanciamiento, si las hay

Loss of linearity and symnietrisation in rcgulalory networks, lo appcar in Procc of AINA-IEEE workshop, Bradford,

UK, May 2009. CONGRESO CON COMITÉ DEN EVALUACION


Archivo Asociado al artículo : non-linearitysymmetrisationJDcmongcotEGolcsSScne.pdf

hllp:7caIcvtconlcy1 .cl;inlorrne acaclenhico/IndeN.php/invesugador/f4 olras puhlic ciones/descirga.'OI97 1 86/1070022 209 8 1

CONGRESOS

Sin información ingresada.

TESIS/MEMORIAS

Título de Tesis : Discrete models: structure and dynamics Nombre y Apellidos del(de la) Alumno(a) : Salinas Ayala, L.

Nombre y Apellidos dei(de la) Tutor(a) : Goles, E.

Título Grado : Doctorado institución : UNiversidad de Chile, Facultad de Ciencias Físicas y Matemáticas

País: CHILE

Ciudad : Santiago Estado de Tesis : Terminada

Fecha Inicio : 01104/2004

Fecha Término : 08/07/2008


Archivo Asociado : tesis_lilian.pdf I1ttp:!/evaICyt.COflICyl.CFII1ItI1te acadcistico!indexphpinvestigador14 tesis mcmoriasidescaraI6097 1 (s'l O7OO22/2O9(I34

ANEXOS

Archivo Asociado: CARTAACEPTAC1ON_FILTROS.pdf htlp:'evalcyt.eonicytcI'infornie acadeniico/inclex.php/invcstigador/fS anexosldescarga/60971 86/I(170022200911732/

2

Archivo Asociado : MAIL.Aceptacion.lNtrinsically.Universality.pdf Itttp:eaIeyt.contcicI'mIorme aetdeitucoiindcxphp/tnvestigador/fS anexos/descargai60971 8('I (J7OO22/2OO/l734!

A continuación se detallan los anexos fisicos/papel que no se incluyen en el informe en formato PDF.

Carta (mail aceptacion) artículo sobre filtros 'Sequential operator for filtering cycles in Boolena Networks"

Carta (Mail aceptación) artículo 'Communication Cotnplexity and lntrinsic universality in cellular automata"

Documents

COMISIÓN NACIONAL GE INVESTIGACIÓN W CIENTÍFICA Y …