Problema alinierii şirurilor

42

    Vom introduce acum problema similarităţii şirurilor, unde un şir este o secvenţă de caractere dintr-un anumit alfabet. Fiind date două şiruri acbcdb şi cadbd, cum trebuie măsurat cât de asemănătoare sunt ele? Similaritatea este dovedită prin găsirea unei “bune” alinieri între cele două şiruri. Aici există o singură aliniere a acestor două şiruri.

    Caracterul special - reprezintă inserarea unui spaţiu. Putem evalua cât este de bună o astfel de aliniere utilizând o funcţie de scor (scoring function). De exemplu, dacă o potrivire a două caractere o punctăm cu +2, şi fiecare nepotrivire sau inserţie a unui spaţiu este puntat cu -1, atunci alinierea de mai sus are punctajul

3·(2) + 5·(-1) = 1.

    Acest exemplu arată numai o aliniere posibilă pentru şirurile date. Pentru fiecare pereche de şiruri şi funcţie de scor, există multe posibilităţi de aliniere. Următoarele definiţii generalizează acest exemplu.

Definiţie: dacă x şi y sunt fie un caracter sau spaţiu, atunci σ(x,y) denotă scorul alinierii a lui x şi y.

 În exemplul de mai sus, σ(c,c)=+2, şi σ(c,a)=σ(c,-)=σ(-,c)=-1.

Definiţie: Fie şirurile S şi T. O aliniere A transformă şirurile S şi T în şirurile S’ şi T’ care pot conţine spaţii suplimentare, unde

1. |S’|=|T’| (au acelaşi număr de caractere) şi

2. eliminarea tuturor spaţiilor din S’ şi T’ reconstruieşte şirurile S şi T.

Valoarea alinierii A este

    unde l=|S’|=|T’| (lungimea şirului)

În exemplul de mai sus, dacă S=acbdb şi T=cadbd, atunci S’=ac--bcdb şi T’=-cadb-d-.

Definiţie: O aliniere optimă (optimală) a lui S şi T este una dintre alinierile posibile care are cea mai mare valoare pentru aceste două şiruri.

    Pentru cele două şiruri din exemplul anterior, este prezentată alinierea optimală? Vom prezenta în continuare câţiva algoritmi pentru calculul alinierilor optime, care ne vor permite să răspundem la această întrebare.

© Cornel Mironel Niculae, 2003-2008

13-Nov-2009