<<

Date generale
Obiectivele fazei
Rezumatul fazei
Descrierea stiintifica si tehnica
Concluzii
Bibliografie

Obiectivele fazei

1. Analiza şi studierea unei semantici operaţionale a P sistemelor
2. Legătura cu sisteme de rescriere
3. Asocierea aspectelor probabiliste cu multiseturi şi reguli

Unul din punctele de interes ale cercetării în calculul membranar este gasirea de conexiuni cu alte zone ale informaticii, mai ales în materie de implementări şi specificaţii executabile. Spre realizarea acestui scop a fost introdusă în [L2] o semantică operaţională pentru P sisteme, prin intermediul logicii rescrierilor. Formal, aceasta este definită prin considerarea de evoluţii ale sistemului, date de tranziţii intre configuraţii. Un pas de calcul constă în executarea a trei paşi: fiecare membrană evoluează paralel prin aplicarea regulilor ei în mod maximal, apoi sunt trimise şi primite obiectele marcate din membrane, iar apoi unele membrane sunt eventual dizolvate. În continuare, pentru a transforma aceasta specificare formală, este utilizat un sistem bazat pe logica rescrierilor, numit Maude. Utilizarea sistemului Maude permite unificarea abordării semantice şi a abordării ecuaţionale păstrând avantajele ambelor. În acest mod sunt obţinute doua implementări ale semanticii operaţionale: una ce pune accentul pe acurateţe, este utilă în a investiga aspectele inspirate de biologie, sau în a creşte viteza execuţiilor într-o maşină de calcul paralel; cealaltă implementare, numita fidelă, este utilă în investigarea configuraţiilor sistemului. În plus, primul tip de implementare ne oferă o noua semantică operaţională în care cei trei paşi descrişi anterior nu sunt clar delimitaţi, lucru ce poate conduce la o nouă şi mai bogată clasă de modele descrise de P sisteme. Se demonstrează două rezultate de corespondenţă operaţională care dovedesc corectitudinea şi completitudinea implementărilor. în final, se compară această abordare cu altele în care se folosesc structuri de multiset.
O alta linie de cercetare a sistemelor inspirate din biologie este reprezentată de catre articolul [L8], în care am tratat problema găsirii unor sisteme membranare cât mai realiste din punct de vedere biologic. Până acum, evoluţia sistemelor membranare presupunea condiţii de maximalitate în aplicarea regulilor dintr-o membrană; acest lucru vine din presupunerea că într-un sistem biologic se execută de fiecare dată toate reacţiile pentru care există resurse disponibile – condiţie utilă în demonstrarea unor proprietăţi ca universalitatea şi rezolvarea în timp polinomial a problemelor NP-complete. Acest punct de vedere a fost însă pus sub întrebare datorită restrictivităţii condiţiei şi a lipsei de naturaleţe a presupunerii făcute. În lucrarea [L8] se exprimă un nou punct de vedere prin considerarea unui paralelism minimal în aplicarea regulilor ce guvernează P sistemul: anume, daca resursele disponibile permit acest lucru, măcar una dintre regulile ce guvernează o membrană va fi aplicată. Acest mod de a folosi regulile defineşte un paralelism minimal. Se studiază calculabilitatea a doua tipuri de P sisteme cu paralelism minimal şi se arată faptul că este pastrată universalitatea şi posibilitatea de a rezolva probleme NP-complete în timp polinomial (prin extinderea spaţiului în care se lucrează).
Ambele lucrări [L2,L8] rezumate în acest raport au fost publicate în acest an, în una dintre cele mai prestigioase reviste de informatica: Theoretical Computer Science.
Celelalte lucrări publicate în ultimele luni de către grupul nostru de cercetare contin rezultate relativ la relaţiile dintre diferite formalisme inspirate de biologie [L5,L12,L13,L17], prezintă algoritmii evolutivi distribuiţi de optimizare exprimaţi cu ajutorul P sistemelor [L11], descriu controlul sistemelor membranare prin strategii de rescriere [L1], evidenţiază legăturile între teoria automatelor şi P sisteme [L7,L15], descriu tipuri de P sisteme şi de tranziţii pentru acestea [L3,L6], studiază probleme de complexitate legate de ramificarea evoluţiilor nedeterministe ale sistemelor membranare [L9], precum şi modelare celulară folosind algebre de procese şi P sisteme [L10]. În lucrarea [L14] se incearcă definirea unei teorii a informaţiei bazate pe multiset, iar în lucrarea [L16] se incearcă definirea unei structuri de evenimente pentru calculul membranar.

În [L16], am studiat structuri de evenimente [6,7]  pentru sisteme membranare, luînd în calcul atât relaţiile de cauzalitate cît şi relaţiile de conflict. Sistemele membranare [5] descriu un mecanism computaţional inspirat din biologia moleculară.
Structurile de evenimente sunt modele formale definite pentru sisteme paralele şi nedeterminste. Folosirea acestor structuri ne permite să stabilim în manieră formală cînd şi unde anume apar paralelismul şi nedeterminismul în sistemele mebranare.
Am investigat modul în care o structură de evenimente poate fi pusă în corespondenţă cu un pas din procesul de evoluţie paralelă. Concluzia noastră este că semnificaţia unui eveniment depinde de structurile algebrice folosite pentru exprimarea conţinutului membranelor: şiruri sau multiseturi. În cazul folsirii multiseturilor, comutatitvitatea introduce anumite cauzalităţi "false" care trebuiesc înlăturate pentru a se putea exprima paralelismul din sistemele de mebrane.
Construcţia structurilor de evenimente pentru cazurile de priorităţi şi promotori poate fi redusă la cazul rescrierii paralele maximale.
În [L15] am introdus reţelele de automate multiset Mealy, arătînd că în ce priveşte puterea lor computaţională, ele sunt complete, întrucât o reţea multiset Mealy este capabilă să simuleze o maşină Turing.
Cercetările recente [1] folosesc teoria automatelor ca un mijloc eficient de descriere şi control a activităţii genelor. O secvenţă ADN este modelată ca un mic automat care apoi este folosit pentru controlul logic al exprimării genei reprezentată de secvenţa respectivă.
În [2] am prezentat o modalitate de interacţiune dintre gene şi proteine (şi anume procesul producerii proteinelor) în termeni de automate Mealy, semigrupuri de transformare şi operaţii abstracte. Automatul Mealy propus ca model formal pentru traducerea mesajului genetic este unul minimal, acceptând mesajele mARN şi terminând procesul de traducere.
Totuşi biologia moleculară are de a face nu doar cu secvenţe ci şi cu multiseturi. [4] introduce şi studiază automate multiset, maşini care lucrează asemenea automatelor dar generează-recunosc nu secvenţe ci multiseturi. Un automat multiset Mealy poate fi văzut în mod corespunzător ca o maşină Mealy.
Pentru a defini reţelele de automate multiset Mealy conectăm aceste automate în diverse moduri, folosind atât conexiuni paralele cât şi conexiuni seriale. În [3] am definit produsul direct restricţionat de automate multiset Mealy pentru cazul paralel, precum şi produsul în cascadă pentru conexiuni seriale.
Pentru a obţine puterea de calcul a unei reţele de automate multiset Mealy, facem corespondenţa cu sisteme neuronale P, demonstrând că aceste reţele sunt complete din punct de vedere computaţional.
În [L18] am prezentat implementarea unui demonstrator automat circular coinductiv numit CIRC [9,10], ca extensie a limbajului/sistemului Maude [11,12], folosind posibilităţile de meta-programare ale acestuia. Principalul motor al demonstratorului CIRC constă dintr-un set de reguli de rescriere care implementează principiul circularităţii. Puterea demonstratorului poate fi extinsă prin adăugarea unor alte componente care pot fi implementate de asemenea folosind reguli de rescriere. Am demonstrat corectitudinea demonstratorului coinductiv şi am arătat modul în care strategiile de rescriere, exprimate ca expresii regulate, pot fi folosite pentru specificarea de tactici de demonstrare pentru CIRC. Am exemplificat această metodă definind o tactică de demonstrare care combină coinducţia circulară cu o formă particulară de simplificare pentru demonstrarea echivalenţei proceselor independente de context. Strategiile regulate fac posibilă folosirea de tactici de demonstrare care combină coinducţia cu inducţia; acest fapt putea fi realizat pînă acum doar în mod asistat [13,14,15].
Lucrarea de disertaţie [L19] elaborată de masterandul Sebastian Tudorie sub îndrumarea lui Liviu Ciortuz,  reflectă în mod direct preocuparea existentă în cadrul cercetărilor recente privind eficientizarea algoritmilor si implementarilor folosite pe de o parte în extragerea de informaţii din texte sau de pe internet iar pe de altă parte analiza în secvenţelor genetice. Aspectul eficienţei menţionat este critic datorită cantităţii foarte mare de informaţii de care se dispune la ora actuală în aceste domenii. Autorul a realizat implementari pentru algoritmi de căutare fie a unui singur pattern fie a unor pattern-uri multiple. A fost de asemenea tratat cazul pattern-urilor extinse. Algoritmii implementaţi au fost testati si portaţi pe mai multe compilatoare (între care GNU gcc, Visual Studio). Un raport tehnic asupra acestei biblioteci este in curs de elaborare.
           Estimăm ca biblioteca aceasta va fi extinsă (cu funcţii de căutare indexată pe şiruri) şi va putea servi pentru aplicaţii atât în domeniul analizei de secvenţe genetice cât şi în extragerea de informaţii din texte de limbaj natural, în special din rezumate de articole din domeniul bio-medical (a se vedea fazele următoare ale proiectului).
Lucrarea de disertaţie [L20] elaborată de Marta Gîrdea sub îndrumarea lui Liviu Ciortuz abordează învăţarea automată de funcţii kernel pentru Maşini cu Vectori Suport (SVM) propunând ca  metodă utilizarea programării genetice în elaborarea unui algoritm de boosting. Boosting-ul este o metoda de învăţare automată care elaborează ipoteze specializate pe diferite cazuri de dificultate. Folosind programarea genetică sunt elaborate şi testate combinaţii aditive şi multiplicative de funcţii nucleu de tip linear, polinomial şi funcţii cu bază radială (RBF). Analiza facută de autoare demonstrează că într-adevăr funcţiile astfel învăţate sunt funcţii kernel, şi la fiecare iteraţie făcută de boosting eroarea de antrenament scade. Testînd metoda elaborată pe un set de date netrivial, se obţin rezultate superioare faţă de funcţii kernel uzuale şi faţă de funcţii învăţate doar prin programare genetică (adică fără boosting).
Liviu Ciortuz a fost invitat de către Prof. Dr. Mihaela Zavolan să facă o vizită în perioada 26-30 mai 2007, la Biozentrum, Swiss Institute for Bioinformatics, University of Basel, Elveţia. Liviu Ciortuz a avut discuţii cu cercetătorii Mihaela Zavolan, Erik van Nimwegen şi Torsten Schwede. Scopul acestor discuţii a fost prezenarea de către cercetătorii elveţieni a modalităţilor specifice în care tehnicile de învăţare automată sunt aplicate în cercetările lor legate de analiza secvenţelor genetice. O atenţie deosebită a fost acordată subiectului clasificării secvenţelor ARN în funcţie de caracterul lor codant sau non-codant. Cercetătorii elveţieni au indicat faptul că lucrări recente (J. Liu, J. Gough, B. Rost, Distinguishing protein-coding from non-coding RNA through Support Vector Machines, PloS Genetics 2:4, 2006) au arătat că această problemă de clasificare este rezolvabilă prin învăţare automată, rămânând ca în viitor să fie explorate modalităţi de clasificare a diverselor categorii de secvenţe ARN non-codante. Au fost discutate posibile modalităţi de colaborare (eventual în cadrul unui proiect comun) a membrilor echipei ForMol de la Facultatea de Informatică din Iaşi cu  cercetătorii de la Biozentrum, Basel.

Lista publicaţiilor:
 
Lucrări ISI:

[L1] O.Andrei, G.Ciobanu, D.Luncanu. Expressing Control Mechanisms of Membranes by Rewriting Strategies. In H.J.Hoogeboom et al.(Eds.): WMC 7, Lecture Notes in Computer Science vol.4361, Springer, 154-169, 2006.
[L2] O.Andrei, G.Ciobanu, D.Lucanu. A rewriting logic framework for operational semantics of membrane systems. Theoretical Computer Science vol.373, 163-181, Elsevier, 2007.
[L3] C. Bonchis, C. Izbasa, G. Ciobanu. Compositional asynchronous membrane systems, Progress in Natural Science vol.17(4), 411-416, 2007.
[L4] G.Ciobanu (Guest Editor). International Journal of Computer Mathematics vol.83(7), Special Issue Theory and Applications of P Systems, 2006.
[L5] G.Ciobanu, B.Aman. On the Relationship Between Membranes and Ambients, BioSystems, to appear, 2007.
[L6] G.Ciobanu, L.Cornacel. Probabilistic transitions for P systems. Progress in Natural Science vol.17(4):432-441, 2007.
[L7] G.Ciobanu, V.M.Gontineac. P Machines: An Automata Approach to Membrane Computing. In H.J.Hoogeboom et al.(Eds.): WMC 7, Lecture Notes in Computer Science vol.4361, Springer, 314-329, 2006.
[L8] G.Ciobanu, Linqiang Pan, Gh.Paun, M.Perez-Jimenez. P Systems with Minimal Parallelism. Theoretical Computer Science vol.378, 117-130, 2007.
[L9] G.Ciobanu, Gh.Paun, M.J. Perez-Jimenez. On the branching complexity of P systems, Fundamenta Informaticae vol.73, 27-36, 2006.
[L10] F.J. Romero-Campero, M. Gheorghe, G. Ciobanu, J.M. Auld, M.J. Perez-Jimenez. Cellular modelling using P systems and process algebra. Progress in Natural Science vol.17(4), 375-383, 2007.
[L11] D.Zaharie, G.Ciobanu. Distributed Evolutionary Algorithms Inspired by Membranes in Solving Continuous Optimization Problems. In H.J.Hoogeboom et al.(Eds.): WMC7, Lecture Notes in Computer Science vol.4361, Springer, 154-169, 2006.

Lucrări in alte publicaţii internaţionale:

[L12] B.Aman, G.Ciobanu: Mobile Ambients and Mobile Membranes, Proceedings CiE,  2007.
[L13] B.Aman, G.Ciobanu: Reachability Problem in Mobile Membranes, Proceedings WMC8, 2007.
[L14] C.Bonchis, C.Izbasa, G.Ciobanu: Information Theory over Multisets, Proceedings WMC8, 2007.
[L15] G.Ciobanu, M.Gontineac: Networks of Mealy Multiset Automata, Proceedings WMC8, 2007.
[L16] G.Ciobanu, D.Lucanu: Event Structures for Membrane Systems, Proceedings WMC8, 2007.

Lucrări trimise spre evaluare la conferinţe internaţionale:

[L17] B.Aman, G.Ciobanu:  Structural Properties and Observability in Membrane Systems

[L18] D. Lucanu, G. Roşu, Gh. Grigoraş, Regular Strategies as Proof Tactics for CIRC Prover,  articol acceptat pentru publicare în Proceedings of The 7th International Workshop on Reduction Strategies in Rewriting and Programming, 2007, parte a RDP'07, Federated Conference on Rewriting, Deduction, and Programming, ENTCS (Electronic Notes in Theoretical Computer Science).

Lucrari de disertatie:

[L19] S. Tudorie, L. Ciortuz. Bibliotecă de funcţii de pattern matching pe şiruri de caractere. Disertaţie. Facultatea de Informatică. Universitatea "Al.I.Cuza", Iaşi. 2007.

[L20] M. Gardea, L. Ciortuz. Hybrid genetic programming and boosting technique for learning kernel functions from training data. Disertaţie. Facultatea de Informatică. Universitatea "Al.I.Cuza", Iaşi. 2007.

Descrierea stiintifica si tehnica

Bibligrafie

1. 1. Z. Benenson, B. Gil, U. Ben­Dor, R. Adar, E. Shapiro. An autonomous molecular computer for logical control gene expression. Nature 429, (2004), 423­429.
2. G. Ciobanu, M. Gontineac. An automata description of the genetic message translation. Fundamenta Informaticae, vol. 64, 93­107, 2005.
3. G. Ciobanu, M. Gontineac. Multiset Mealey automata. International Journal of Foundations of Computer Science, vol. 17(1), 111­126, 2006.
4. E. Csuhaj­Varju, C. Martin+Vide, V. Mitrana. Multiset automata. Multiset Processing, Lecture Notes in Computer Science vol. 2235, Springer, 69­83, 2001.
5. Gh. Păun. Membrane Computing. An Introduction. Springer, 2002.
6. G. Wiskel. Event structures. In Petri Nets: Applications and relationships to Other Models of Concurrency, Lecture Notes in Computer Science vol. 255, 325-392, Springer, 1987.
7. G. Wiskel. An introduction to event structures. In REX School/Workshop on Linear Time, Branching Time and Partial Order in Logics and Models for Concurrency, Lecture Notes in Computer Science vol. 354, 364-397, Springer, 1989.
8. O. Andrei, G. Ciobanu, D. Lucanu. A rewriting logic framework for operational semanitics of membrane szstems. Thoretical Computer Science, 373:163-181, 2007.
9. D. Lucanu, G. Roşu. CIRC: a circular coinductive prover. In 2nd Conference on Algebra and Colagebra in Computer Science (COLCO 2007), Bergen, Norway, 2007, to appear in Lecture Notes in Computer Science.
10. D. Lucanu, G. Roşu. The CIRC Prover, http://fsl.cs.uiuc.edu/index.php/Circ.
11. M. Clavel et al. Maude: Specification and programming in rewriting logic. Journal of Theoretical Computer Science 285 (2002), 187-243.
12. M. Clavel, F. Durán, S. Eker, J. Messeguer. Building Equational prooving tools bz reflection in rewriting logic. In Cafe: An Industrial-Strength Algebraic Formal Method, Elsevier 2000.
13. J. Goguen, K. Lin, G. Roşu. Circular coinductive rewriting. In Proceeedings of Automated Software Engineering, 2000, 123-131.
14. G. Roşu. Hidden Logic. PhD thesis, University of California at San Diego. 2000.
15. D. Haussmann, T. Mossakowski, L. Schröder. Iterative circular coinduction for CoCASL in Isabelle-HOL. In Fundamental Approaches to Software Engineering 2005, Lecture Notes in Computer Science vol. 3442, 341-356. 2005.

Concluzii

Tinand cont de toate aceste realizari, putem spune ca activitatea de cercetare din cadrul proiectului ForMol a fost bogata, iar obiectivele pentru prima jumatate a anului 2007 au fost indeplinite.

1. In perioda raportata au fost elaborate o serie de studii, articole si prototipuri conform planului de realizare a proiectului.
2. Obiectivele etapei au fost realizate.
3. S-au adus contributii originale la cercetarea fundamentala si aplicativa a acestui domeniu, prezentate la conferinte nationale si internationale, publicate in jurnale nationale si internationale de specialitate. S-au publicat  11 articole ISI in aceasta a doua jumatate a anului.
4. Rezultatele obtinute au fost prezentate si discutate in cadrul seminariilor stiintifice la Institutul de Informatica Teoretica, publicate in rapoarte de cercetare ale Institutul de Informatica Teoretica al Academiei Romana. S-a organizat un atelier de lucru, cu scopul de a discuta eventuale colaborari in domeniul sistemelor mebranare.
5. S-a  contribuit la cresterea vizibilitatii cercetarii romanesti in comunitatea stiintifica internationala prin participarea la conferinte, comunicarea rezultatelor proiectului la conferinte nationale si internationale cu impact stiintific mare si colaborarea cu diversi cecetatori din tara sau strainatate din domeniul sistemelor membranare ;

Rezultatele etapei se concretizeaza in:

• lucrari publicate sau pregatite pentru publicare la conferinte nationale si internationale;