<<

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

Obiectivele fazei

1. Specificaţii executabile pentru P sisteme; studierea strategiilor de aplicare a regulilor.
2. Retele moleculare şi folosirea unor logici temporale pentru descrierea proprietatilor.
3. Verificarea automata exprimată in diferite logici temporale.
4. Text mining pentru identificare de relaţii între proteine.

Sistemele membranare, introduse in [9], constituie o clasa de modele computationale paralele inspirate din biologie, anume din modul de functionare al structurilor celulare complexe. Una din variantele modelului initial descris in [9] este cea a sistemelor cu membrane mobile generalizate („enhanced mobile membranes”). Aceasta a fost introdusa de catre noi in [L3] cu scoput de a modela functionarea sistemului imun. Membranele mobile introduse in [5] au, pe langa regulile de evolutie locala si contextuala, si reguli de evolutie de tip endocitoza si exocitoza. In varianta generalizata acestora le-am adaugat reguli de tip endocitoza fortata si exocitoza fortata, in care obiectele ce determina miscarea membranei  se afla in membrana parinte. Cu ajutorul acestor noi reguli se poate modela modul in care anumite componente ale sistemului imun (celulele dendritice) protejeaza organismul impotriva infectiilor. De asemenea, se studiaza proprietati structurale ale acestui nou tip de sistem membranar.
Am studiat sistemele cu membrane mobile generalizate si din punct de vedere al complexitatii computationale in [L7]. In aceasta lucrare se arata ca, folosind doar regulile de evolutie prin mobilitate, sunt suficiente 12 membrane pentru a obtine puterea computationala a unei masini Turing universale. Un alt rezultat obtinut in [L7] arata ca, pentru sisteme cu 3 membrane, folosirea regulilor de tip endocitoza si exocitoza este echivalenta cu folosirea regulilor de tip endocitoza fortata si exocitoza fortata.
Revenind la sisteme cu membrane mobile, in [L4] am studiat probleme de decidabilitate pentru astfel de sisteme cu replicare utilizand rezultate obtinute in cadrul altui formalism inspirat din biologie, cel al ambientilor mobili [2]. In membrane mobile cu replicare, obiectele sunt impartite in clase, in functie de rolul lor in evolutie; ele pot determina aplicarea regulilor de mobilitate sau pot genera noi obiecte. Pentru  doua astfel de membrane, am demonstrat in [L4], prin reducere la ambienti mobili, ca este decidabil daca una din ele se poate reduce la cealalta. Am aratat de asemenea ca acest lucru nu mai are loc in cazul in care se adauga si posibilitatea de dizolvare a membranelor. Alte rezultate al lucrarii arata ca este decidabil daca un sistem  cu replicare este periodica sau daca este marginit (exista un numar finit de configuratii la care se poate ajunge prin evolutie de la configuratia initiala). Legatura intre ambienti mobili si sisteme membranare este studiata in [L1]. In aceasta lucrare am analizat si translatarea congruentei structurale si a bisimularii contextuale dintr-un formalism in celalalt, ca si diferenta intre descrierea pompei de sodiu-potasiu in sisteme membranare cu cea obtinuta prin translatare in ambienti siguri („safe ambients”).
Lucrarea [L6] prezinta o abordare noua, prin prisma codificarilor posibile, a teoriei multiseturilor,  principalul “ingredient” utilizat de membrane in cadrul proceselor de calcul. Astfel, dupa ce se subliniaza legaturile dintre teoriile clasice privind cuvintele peste un alfabet finit, multiseturile peste acelasi alfabet si vectorii Parikh asociati, este introdus un produs asemanator cu produsul Hadamard din cazul seriilor formale sau matricilor, produs neutilizat inca in teoria multiseturilor. Dupa introducerea unei codificari prin numere prime a multiseturilor, pe care o vom numi in cele ce urmeaza codificare Gödel, putem caracteriza doua multiseturi avand suporturi disjuncte astfel “Doua multiseturi au multimi suport disjuncte daca si numai daca produsul Hadamard este zero sau, echivalent, codificarile Gödel sunt prime intre ele”.
Totodata, o serie de operatii cu multiseturi pot fi transferate spre aritmetica, prin numerele Gödel asociate. De exemplu, daca A si B  sunt doua multiseturi iar a si b sunt numerele Gödel corespunzatoare, A Í B daca si numai daca a/b. Numarul Gödel asociat reuniunii (intersectiei) unei familii finite de multiseturi este egal cu cel mai mic multiplu (cel mai mare divizor) comun al numerelor Gödel asociate multiseturilor din familie. S-a oferit si un exemplu de sistem membranar adaptat lucrului cu numere Gödel asociate multiseturilor.
            Tot aritmetica si teoria numerelor, precum si produsul Hadamard ne-a condus spre considerarea normei unui multiset. Un rezultant important obtinut in aceste conditii se refera la universalitatea, in sens Lagrange, patratului functiei norma pentru multiseturi peste un alfabet cu 4 litere (similar alfabetului ADN) si, chiar mai mult, minimalitatea numarului 4 in ceea ce priveste acest tip de universalitate. Acest rezultat poate fi considerat, alaturi de rezultate similare privind numarul 4 (cum ar fi [10]), posibile explicatii matematice ale faptului ca alfabetul ADN are 4 litere.
                O alta lucrare ce studiaza multiseturi, din punctul de vedere al informatiilor continute, este [L10]. In mod uzual, compresia datelor converteste o secventa de simboluri intr-o secventa de string-uri (descrieri), cele mai scurte descrieri fiind asociate celor mai frecvente simboluri produse de catre sursa de date. Prin contrast, in aceasta lucrare consideram compresia unei secvente de simboluri pana la o secventa de multiseturi. Acest lucru este relevant in cazul in care canalul de comunicare nu pastreaza ordinea (pozitionalitatea) literelor transmise, asa cum se intampla in numeroase contexte biologice; de pilda, daca privim trecerea unui multiset de molecule printr-un vas de sange ca un transfer de informatie. Introducem conceptul nou de cod liber de submultiseturi, corespondent al conceptului existent de cod liber de prefixe. Demonstram si o teorema despre structura codurilor libere de submultiseturi optimale pentru variabile aleatoare discrete uniforme si descriem un algoritm pentru contruirea lor. De asemenea s-a realizat o implementare software pentru simularea unui P sistem pe baza unei specificatii executabile XML in limbajul Ruby, precum si mai multe prototipuri pentru testarea conceptelor teoriei informatiei pe multiseturi.
Lucrarea [L8] analizeaza caile de a specifica sistemele membranare cu pastrarea concurentei maximale. Logica rescrierii [7] este o logica de nivel inalt utilizata pentru specificarea sistemelor. Logica ecuationala [8] este utilizata ca subramura a logicii rescrierii pentru specificarea algebrica a sistemelor. Specificarea unui sistem membranar ∏ se realizeaza prin asocierea unei teorii de rescriere R(∏). Scopul lucrarii este compararea gradului de concurenta al sistemului ∏ cu cel al teoriei (sistemului) R(∏). Pentru a realiza aceasta comparatie, se asociaza cate o logica de tip Henessy‑Milner pentru fiecare dintre cele doua sisteme, notate cu L∏ si, respectiv, LR(∏). Compararea celor doua grade de concurenta se poate realiza prin compararea formulei φ  L∏, ce caracterizeaza s ⇒ s’ cu formula ψ(φ)  LR(∏), ce caracterizeaza ψ(s) → ψ(s’). Rezultatul lucrarii [L8] arata ca daca φ descrie concurenta maximala a tranzitiei de rescriere maximala paralela s ⇒ s’, atunci ψ(φ) exprima concurenta fara interblocaj pentru ψ(s) → ψ(s’). Motivul principal pentru pierderea concurentei maximale este localitatea regulilor de evolutie. Concurenta interactiunilor dintre membrane este pastrata doar partial.
Faptul ca semantica data cu ajutorul logicii rescrierii descrie concurenta maximala doar prin concurenta fara interblocaj nu este neaparat ceva negativ. Aceasta semantica este utila atunci cand se doreste analizarea comportamentului sistemelor membranare sau verificarea unor proprietati. Totusi, daca se urmareste utilizarea unui model-checker pentru verificarea unor proprietati, atunci semantica este mai putin eficienta.
Pentru specificarea unui sistem membranar, regulile de evolutie, precum si interactiunile dintre membrane (comunicare, dizolvare) sunt implementate fara dificultati ca reguli de rescriere peste o structura algebrica. Pe de alta parte, nivelul inalt de paralelism si nedeterminismul sistemelor membranare, localitatea regulilor de evolutie si aplicarea unor constrangerilor (promotori, inhibitori) nu pot fi specificate cu usurinta doar prin tehnici standard de specificare in cadrul logicii rescrierii. Problema specificarii de sisteme membranare cu promoteri si inhibitori este studiata in lucrarea [L2], prezentata pe larg in sectiunea de descriere stiintifica si tehnica a acestui raport.
Semantica sistemelor membranare poate fi definita cu ajutorul strategiilor de rescriere. Lipsa de expresivitate a strategiilor de rescriere care descriu mecanisme de control al membranelor au determinat definirea unui nou concept de strategii, mult mai general. In lucrarea [L5] am introdus mecanisme de control al evolutiei sistemelor membranare, pe baza carora s-a construit o semantica algebrica pentru aceste sisteme.
Scopul lucrarii este identificarea unui framework pentru specificarea dinamicii sistemelor similare cu sistemele membranare, unde evolutia este este data de aplicarea regulilor de rescriere. Una dintre solutii se bazeaza pe combinarea teoriilor de rescriere cu strategiile si mecanismele de control al strategiilor. Mecanismul de control decide care strategie urmeaza a fi aplicata la pasul urmator. In lucrare este prezentata implementarea Maude a limbajului de strategii pentru sistemele membranare, introdus cu ajutorul teoriilor MEL (Membership Equational Logic). S-a ales sistemul Maude datorita faptului ca acesta pune la dispozitie un limbaj de strategii de rescriere si permite lucrul la meta-nivel. De asemenea, in lucrare este descrisa modalitatea in care sistemele membranare sunt interpretate ca teorii de rescriere controlate prin intermediul strategiilor.
Abordarea la nivel de strategie de calcul si nu la nivel de regula reprezinta un stimulent in directia studiului si analizei formale a sistemelor biologice, ramanand in continuare un subiect deschis.
Lucrarea [L11] este un raport tehnic depus in iunie 2008 la Facultatea de Informatica, Universitatea „Al. I. Cuza”, Iasi, Romania ce studiaza mecanisme de identificare ale noi secvente de MicroRNA. MicroRNA-urile constituie o clasa importanta de RNA-uri non-functionale, implicate in fenomenul cunoscut sub numele de interferenta RNA-mediata. Efectul acestui fenomen este blocarea formarii de proteine prin actiunare directa asupra RNA-ului mesager. Fenomenul a fost pus in evidenta de biologi in 1993 si a fost explicat in detaliu de profesorii americani Craig Mello si Andrew Fire [4], care au primit premiul Nobel pentru medicina in 2006. MicroRNA-urile care au fost identificate sau validate pe cale experimentala, precum si secvente omoloage cu acestea, sunt inregistrate in baza de date miRbase [6]. Ultima versiune a miRbase contine peste 6000 de inregistrari. Lungimea acestor secvente este de 19-27 nucleotide, iar structura lor secundara este in general sub forma de agrafa de par („hairpin”, format din „stem” si „loop”).
Din punct de vedere informatic, exista doua probleme legate de microRNA-uri:
1. identificarea de noi secvente microRNA pornind de la cele deja cunoscute;
2. identificarea siturilor din secvente mRNA (messenger RNA) asupra carora actioneaza o secventa microRNA data.
In prezentul raport tehnic avem de a face cu prima dintre aceste doua probleme. Pentru identificarea de noi secvente microRNA, studiile bazate pe homologie, adica folosind alinieri de secvente, nu au condus la rezultate foarte bune, dat fiind faptul ca structura primara a RNA-urilor in general nu este bine conservata. Structura secundara este cea care se conserva in general. Actualmente, cea mai buna abordare pentru identificarea de microRNA-uri se bazeaza pe metode de invatare automata, iar dintre acestea, cel mai adesea se folosesc SVM-urile (Support Vector Machines). Exista o „explozie” de articole care descriu SVM-uri pentru identificare de microRNA-uri, care au fost publicate in cursul ultimilor 2-3 ani. Scopul prezentului raport tehnic este de a prezenta aceste SVM-uri, cu accent deosebit pe identificarea si compararea diverselor trasaturi folosite, precum si a efectului lor asupra performatelor de clasificare.
Raportul prezinta 10 SVM-uri, dintre care cele mai reprezentative sunt: Triplet-SVM (2005), miR-abela (2005), MiPred (2007) si miPred (2007). Cele mai importante clase de trasaturi folosite pentru clasificarea microRNA-urilor sunt: tresaturi ce tin de structura primara (lungimea secventei, frecventele nucleotidelor, ale dinucleotidelor, etc), tresaturi ce tin de structura secundara (dimensiunea stem-ului, dimensiunea hairloop-ului, numarul de bucle interne, cuvinte de lungime fixa in cadrul adnotarii de tip dot-pair, si in particular trasaturi topologice – descrierea diferitelor componente ale structurii secundare precum si a conectivitatii lor), si trasaturi termodinamice (nivelul minim de energie la pliere, precum si forme derivate ale acestei energii).
Lucrarea [L12] se incadreaza in aria preocuparilor noastre de a gasi cai de optimizare/eficientizare in tratarea volumului mare de date ce apar in analiza genomurilor, in special in cazul organismelor superioare. Scrisa de Stefan Ciobaca (Ecole Normale Supérieure, Cachan, France) in colaboare cu Liviu Ciortuz (Facultatea de Informatica, Universitatea „Al. I. Cuza”, Iasi, Romania), a fost trimisa la simpozionul SYNASC 2008, care urmeaza sa aiba loc la Timisoara. Lucrarea are ca scop invatarea automata a factorilor de unrolling pentru bucle de program, in vederea optimizarii compilarii cu gcc (Gnu C Compiler) pe arhitecturi de tipul x86. Algoritmii de invatare automata pe care i-am folosit sunt: cel mai apropiat vecin (nearest neighbour), si arborii de decizie. Antrenarea are loc pe benchmark-ul pentru probleme de calcul numeric SciMark2. Concluzia lucrarii este ca acesti factori pentru unrolling-ul buclelor de program, invatati in mod automat, conduc la un spor de rapiditate (speed-up factor) care este comparabil, sau chiar usor mai bun decat cel obtinut prin tehnicile native de optimizare (euristici) ale gcc. Avantajul folosirii tehnicilor de invatare automata in acest domeniu este eliberarea implementatorilor compilatorului de partea consumatoare de timp a optimizarii pe diferite arhitecturi, pe diferite clase de probleme, etc.

Lista publicaţiilor:
 
Lucrari ISI:

[L1] G. Ciobanu, B. Aman. On the Relationship between Membranes and Ambients, Biosystems vol.91(3), 515-530, 2008.

Lucrari in alte publicatii internationale:

[L2] O. Agrigoroaiei, G. Ciobanu. Rewriting Logic Specification of Membrane Systems with Promoters and Inhibitors. Proceedings of WRLA 2008 (Workshop on Rewriting Logic and its Applications), 1-16, 2008.

[L3] B. Aman, G. Ciobanu. Describing the Immune System Using Enhanced Mobile Membranes. Electronic Notes in Theoretical Computer Science, vol. 194, 5-18, 2008.

[L4] B. Aman, G. Ciobanu. Decidability Results for Mobile Membranes derived from Mobile Ambients. Proceedings of CiE 2008 (4th Conference on Computability in Europe), 15 – 25, 2008.

[L5] O. Andrei, D. Lucanu, „Strategy-Based Proof Calculus for Membrane Systems”, Proceedings of WRLA 2008 (Workshop on Rewriting Logic and its Applications), 17-34, 2008.

[L6] G. Ciobanu, M. Gontineac, „Multisets and their Encodings”, Proceedings of Prague International Workshop on Membrane Computing, 1-10, 2008.

[L7] S. N. Krishna, G. Ciobanu: On the Computational Power of Enhanced Mobile Membranes. CiE 2008 (4th Conference on Computability in Europe), Lecture Notes in Computer Science, vol. 5028, 326-335, 2008.

[L8] D. Lucanu, „Rewriting Logic-based Semantics of Membrane Systems and the Maximal Concurrency”, Proceedings of Prague International Workshop on Membrane Computing, 23-34, 2008.

Lucrari in curs de aparitie:

[L9] O. Agrigoroaiei, G. Ciobanu. Rewriting Logic Specification of Membrane Systems with Promoters and Inhibitors. Va apare in Electronic Notes in Theoretical Computer Science.

[L10] C. Bonchis, G. Ciobanu, G. Ghergu, C. Izbasa. Data compression on multisets. Submultiset-free codes. Submisa la 2ICMCTA (2nd International Castle Meeting On Coding Theory and Applications), 15-19 septembrie, Valladolid, Spania.

Rapoarte tehnice:

[L11] L. Ciortuz. Support Vector Machines for microRNA identification, Technical Report, Department of Computer Science, „Al.I.Cuza” University, Iasi, 2008.

Lucrari trimise spre evaluare:

[L12] St. Ciobaca, L. Ciortuz. Learning to unroll loops optimally, trimisa la SYNASC 2008.

Descrierea stiintifica si tehnica

Bibligrafie

[1] P. Bottoni, C. Martin-Vide, G. Paun, G. Rozenberg. Membrane systems with promoters/inhibitors.  Acta Informatica, vol. 38(10), 695–720, 2002.

[2] L. Cardelli, A. Gordon. Mobile Ambients. Foundations of Software Science and
Computation Structures, Lecture Notes in Computer Science vol.1378, Springer,
140–155, 1998.

[3] M. Clavel et al. Maude: Specification and programming in rewriting logic. Journal of Theoretical Computer Science 285 (2002), 187-243.

[4] A. Fire, S. Xu, M. Montgomery, S. Kostas, S. Driver, C. Mello. Potent and specific genetic interference by double-stranded RNA in Caenorhabditis elegans. Nature, 391:806-811, 1998.

[5] S.N. Krishna, Gh. Paun. P Systems with Mobile Membranes. Natural Computing, vol.4(3), 255-274, 2005.

 [6] S. Griffiths-Jones, R. Grocock, S. van Dongen, A. Bateman, A. Enright, miRBase: microRNA sequences, targets and gene nomenclature. Nucleic Acids Research, 34:D140-D144, 2006.

[7] N. Marti-Oliet, J. Meseguer. Rewriting logic as a logical and semantical framework. Handbook of Philosophical Logic, 2nd.edn, Kluwer Academic, 1–87, 2002.

[8] J. Meseguer. Membership algebra as a logical framework for equational specification. WADT 1997, Lecture Notes in Computer Science, vol. 1376, 18–61, 1997.

[9] Gh. Paun, Computing with membranes, Journal of Computer and System Sciences
vol.61(1), 108{143, 2000.

[10] A. Salomaa. DNA Complementarity and Paradigms of Computing. In O.H.Ibarra, L.Zhang (Eds.): 8th Int’l Computing and Combinatorics Conference, Lecture Notes in Computer Science vol.2387, Springer, 3-17, 2002.

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 2008 au fost indeplinite.

Rezultatele etapei se concretizeaza in:

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