Luni, 29 martie, la Facultatea de Matematică și Informatică din
cadrul Universității București a avut loc conferința "Rezultate de
(in)aproximare pentru probleme inspirate din biologie" (detalii
aici). Organizatorul conferinței a fost Prof. Dr. Gheorghe
Ștefănescu, șeful Departamentului de Informatică din cadrul
facultății, căruia doresc să îi mulțumesc pe această cale pentru
invitație. Majoritatea participanților au fost studenți ai
Facultății de Matematică și Informatică. Au fost prezenți și
studenți de la Universitatea Politehnica București, și elevi de
liceu, olimpici la informatică, interesați de problemele din
domeniu. A fost o experiență foarte plăcută pentru mine, cu atât
mai mult cu cât este prima prezentare ținută în limba română în
ultimii 2 ani de zile. Sper că prezentarea a fost pe măsura
organizării și a audienței.
În viața de zi cu zi, ne confruntăm foarte des cu probleme de
optimizare: vrem să aflăm care este cel mai rapid drum spre casă,
cel mai ieftin produs, cea mai avantajoasă bancă etc. O mare parte
din problemele de optimizare, având importante aplicații, sunt
NP-Hard. Informal spus, problemele NP-Hard nu pot fi rezolvate
eficient: calcularea soluției optime pentru aceste probleme este
imposibil de realizat în practică de către orice tip de calculator
(deoarece timpul de calcul este foarte mare).
Două dintre problemele de optimizare NP-Hard cu largi aplicații
în biologie sunt Shortest Common Supersequence ("Cea mai scurtă
supersecvență") și Shortest Common Superstring ("Cel mai scurt
superșir").
Aceste probleme sunt definite astfel: fiind date mai multe
șiruri de caractere vrem să găsim cel mai scurt șir de caractere
care conține toate șirurile ca subsecvență (respectiv subșir).
Spunem că un șir A este subsecvență a unui alt șir B, dacă toate
caracterele lui A apar în B, în aceeași ordine. Dacă aceste
caractere sunt și pe poziții consecutive, spunem că A este subșir
al lui B. De exemplu, "bcd" este subșir al șirului "abcde", iar
"acd" este subsecvență a șirului "abcde", dar nu și subșir al
acestuia.
Shortest Common Superstring este utilizată, printre altele, la
determinarea secvenței ADN. O secvență ADN poate fi văzută ca un
șir foarte lung de nucleotide {A,C,G,T}. Lungimea acestui șir este
de câteva mii de caractere - în cazul unui virus - și de
aproximativ trei miliarde - în cazul unui om. Determinarea
secvenței ADN pentru diferite molecule este un pas important pentru
înțelegerea funcțiilor moleculei.
Cu actualele proceduri de laborator nu se poate determina
întreaga secvență ADN a unei molecule. Molecula este "spartă" în
bucăți ce conțin între 200 și 500 de nucleotide, iar apoi se
determină cel mai scurt superșir al acestor nucleotide.
Shortest Common Supersequence este folosită pentru a determina
gradul de similaritate a două secvențe ADN. Cu cât cea mai scurtă
subsecvență a unor secvențe ADN date are lungimea mai mică, cu atât
aceste secvențe sunt mai apropiate.
Deoarece problemele prezentate mai sus sunt foarte dificile din
punct de vedere computațional (necesită foarte mult timp de calcul
pentru a găsi chiar și o soluție aproximativă rezonabilă)
cercetătorii încearcă să găsească variante mai ușor de rezolvat
(din punct de vedere computațional) ale acestor probleme.
A doua parte a prezentării a fost centrată pe două probleme
înrudite cu cele de mai sus: Permuted Common Supersequence și
Restricted Common Superstring, probleme pe care le studiez în
colaborare cu Zvi Gotthilf și Moshe Lewenstein de la Bar-Ilan
University, Israel, și Raphael Clifford de la University of
Bristol, UK.
În aceste probleme, pe lângă șirurile de caractere date ca input
în problemele precedente dispunem și de un grup de simboluri.
Scopul este găsirea unei ordonări a simbolurilor din grup care să
conțină un număr maxim de șiruri din input ca subsecvențe
(respectiv subșiruri). Din nefericire, aceste probleme nu sunt mai
"ușor" de rezolvat decât Shortest Common Supersequence și Shortest
Common Superstring.