53
|
|
|
|
53 |
Definiţie: Un gap într-un aliniament a lui S şi T este un subşir maxim fie al lui S’ fie al lui T’ ce conţine numai spaţii. (Să ne reamintim din difiniţia 2.3. că S’ şi T’ sunt S şi T cu spaţii inserate aşa cum au fost impuse de aliniament.)
În anumite aplicaţii, poate că nu dorim să avem o penalitate proporţională cu lungimea gap-ului, astfel încât dezvoltăm un nou mod de a mânui gap-urile.
Motivaţii
1. Mutaţiile care determină inserarea sau ştergerea unor mai subşiruri pot fi considerate ca un singur eveniment evoluţionar şi pot asemănătoare cu inserţia sau ştergerea unui singur caracter.
2. Potrivirea cDNA (cDNA matching): Biologii sunt foarte interesaţi să înveţe care gene sunt exprimate (adică traduse în proteine), în ce tip de celule specializate şi unde sunt localizate acele gene în ADN-ul cromozomial. Să ne reamintim din Secţiunea 1.8 că genele eucariote constau adesea din exoni alternând cu introni. mRNA-ul care părăseşte nucleul după transcriere mai are încă secvenţele intronice. Pentru a studia expresia genelor în celulele specializate se procedează după cum urmează:
(a) Se capturează mRNA aşa cum părăseşte nucleul.
(b) se face un ADN complementar (cADN) din mRNA. cADN-ul este astfel o concatenare a exonilor genei.
(c) cDNA este secvenţiat.
(d) Se compară cADN-ul secvenţiat cu ADN-ul cromozomial secvenţiat pentru a găsi regiunea ADN-ului cromozomial din care cADN provine. În acest proces nu dorim să penalizăm foarte mult intronii, care vor genera gap-uri în cADN.
În general, penalizarea gap-ului poate fi o funcţie arbitrară g(q) de lungimea q a gap-ului. Cea mai bună alegere a acestei funcţii, ca şi alegerea celei mai bune funcţii de scor, depinde de aplicaţie. În cazul cDNA prezentat mai înainte, am dori ca penalitatea să reflecte ceea ce este cunoscut despre lungimea obişnuită a intronilor. În sectiunea următoare vom vedea un algoritm a cărui durată este O(nm) pentru cazul în care g(q) este o funcţie afină liniară arbitrară care este adecvată multor aplicaţii. Există programe care utilizează funcţii liniare pe portiuni pentru g(q). Şi acestea sunt mai potrivite aplicaţiei cDNA de mai înainte. Există algoritmi care depind de timp ca O(nmlog m) pentru cazul când g(q) este convexă (is concave downward ([GAL989] şi [MIL988]). Se poate implementa orice fel de funcţie drept funcţie de penalizarea a gap-urilor, dar algoritmul cunoscut pentru ele necesită un timp cubic ([NEE970]) şi desigur un astfel de algoritm nu este utilizabil în practică. În orice aplicaţie de laborator vor exista erori şi indiferent ce funcţie de penalizare a gap-urilor este aleasă ea trebuie să fie suficient de robustă pentru a opera cu astfel de zgomot.
Modelul gap-ului afin
Vom studia un model în care penalizare unui gap are două părţi: o penalizare pentru apariţia gap-ului şi o altă penalizare ce depinde liniar de lungimea gap-ului. Adică, penalizarea de gap este Wg + qWs, unde Wg şi Ws sunt amândouă constante, Wg ł0, Ws ł0 şi gł1 este lungimea gap-ului. Observăm că modelul cu penalitate constantă (indiferent de este de lungimea gap-ului) apare în cazul special Ws=0 .
Vom presupune s(x,-)=s(-,x)=0 deoarece spaţiile vor fi penalizate ca parte a gapului. În această situaţie scopul nostru este de a maximiza
|
l |
σ(S’[i],T’[j])-Wg(#gap-uri)-Ws(#spaţii) |
unde S’ şi T’ sunt S şi T cu spaţii inserate şi |S'|=|T'|=l.
Algoritmul de programare dinamică
Încă o dată, algoritmul procedează la alinierea şirului S[1]…S[i] cu şirul T[1]…T[j]. Pentru aceste prefixe ale lui S şi T, definim următoarele variabile:
1. V(i,j) este valoarea unui aliniament optim al şirului S[1]…S[i] cu şirul T[1]…T[j].
2. G(i,j) este valoarea unui aliniament optim al şirului S[1]…S[i]cu şirul T[1]…T[j]. a cărui ultimă pereche aliniază S[i] cu T[j].
3. F(i,j) este valoarea unui aliniament optim al şirului S[1]…S[i] cu şirul T[1]…T[j]. a cărui ultimă pereche aliniază S[i] cu un spaţiu.
4. E(i,j) este valoarea unui aliniament optim al şirului S[1]…S[i]cu şirul T[1]…T[j] a cărui ultimă pereche aliniază un spaţiu cu T[j].
Valori iniţiale:
V(0,0)=E(0,0)=F(0,0)=0,V(i,0)=E(i,0)=-Wg-iWs, pentru i>0,
V(0,j)=E(0,j)=-Wg-jWs, pentru j>0.
Recurenţă: Pentru i>0 şi j>0,
V(i,j)=max{G(i,j),F(i,j),E(i,j)},
F(i,j)=max{F(i-1,j)-Ws,V(i-1,j)-Wg-Ws},
E(i,j)=max{E(i,j-1)-Ws,V(i,j-1)-Wg-Ws},
G(i,j)=V(i-1,j-1)+σ(S[i],T[j]),
Ecuatia pentru F(i,j) (şi analog pentru E(i,j)) poate fi înţeleasă ca luând maximul a două cazuri: adăugarea unui spaţiu la un gap existent şi iniţierea unui nou gap. Pentru a înţelege iniţierea unui nou gap poate utiliza V(i-1,j) care include posibilitatea unui aliniament care se termină cu un gap, să considerăm V(i-1,j)=max{G(i-1,j),F(i-1,j),E(i-1,j)} astfel încât F(i-1,j)-Wg-Ws este întotdeauna dominat de F(i-1,j)-Ws, astfel că nu va fi ales niciodată ca maxim.
Analiza duratei
Theorema: Un aliniament global optimal cu penalitate de gap afină poate fi calculat în timpul O(mn).
Demonstraţie: Alogoritmul urmează celor care au fost studiate până acum, dar în acest caz sunt trei sau patru tabele de umplut simultan (4 dacă memorăm, respectiv 3 dacă calculăm pe V(i,j)).
Note bibliografice asupra aliniamentelor
Bellman [BEL957] a început studiul sistematic al programării dinamice. Articolul original asupra aliniamentului global este cel al lui Needleman şi Wunsch [NEE970]. Smith şi Waterman [SMI981] au introdus problema aliniamentului local şi algoritmul O(nm) de rezolvare a ei. Câţiva autori au studiat problema construirii unei bune funcţii de scor pentru compararea secvenţelor inclusiv Karlin şi Altschul [KAR990] şi Altschul [ALT993].
© Cornel Mironel Niculae, 2003-2008
13-Nov-2009