Exemplu de aliniere locală

51

    De exemplu, fie S=abcxdex, T=xxxcde şi un punctaj +2 pentru o potrivire, respectiv -1 pentru o nepotrivire sau spaţiu. Algoritmul de programare dinamică completează tabelul valorilor lui n(i,j) de sus în jos şi de la stânga la dreapta după cum urmează:

Valoarea aliniamentului local optim este n(6,6) = 5. Putem reconstrui aliniamentul optim ca în Secţiunea precedentă prin parcurgerea paşilor înapoi de la caseta cu valoare maximă către orice casetă cu valoare 0.

Aliniamentele locale optimale ce corespund acestor drumuri sunt

 

c	x	d	e		x	-	d	e
c	-	d	e		x	c	d	e

Ambele aliniamente locale au trei coincidente şi un spaţiu, având ca valoare
3·(2)+1·(-1) = 5. Putem vedea deasemenea din diagramă cum valoarea a fost dedusă în acest exemplu folosind Definiţia 3.4, care spune că pentru aceleaşi şiruri S şi T, n(5,5) = 3.

Analiza duratei

Teorema 3.5: Algoritmul de programare dinamică calculează un aliniament optim într-un timp O(nm).

Demonstraţie: Calcularea valorii fiecărei casete dintre cele (n+1)(m+1) necesită cel mult 6 căutări în tabel, 3 adunări şi un maxim cu patru variabile, adică un timp O(nm). Reconstruirea unui singur aliniament poate fi făcută într-un timp O(n+m).

Analiza spaţială

Spaţiul necesar pentru alinierea globală/locală optimală merge deasemenea pătratic cu lungimile şirurilor ce trebuiesc comparate. Aceasta poate deveni foarte neplăcut la compararea secvenţelor lungi de ADN, care este mult mai probabil să apară în contextul aliniamentului local. Există o modificare a algoritmului de programare dinamică care calculează un aliniament optimal într-un spaţiu O(n+m) şi un timp O(nm) care utilizează principiul divide şi cucereşte ([HIR975] şi [MYE988]). O pagină de antrenament pentru aliniamentul local se găseşte aici.

© Cornel Mironel Niculae, 2003-2008

13-Nov-2009