Un algoritm evident pentru alinierea optima

Un algoritm evident pentru alinierea optimă

Cel mai evident algoritm este de a încerca toate alinierile posibile, şi a alege orice aliniere care are valoare maximă. Vom examina această abordare mai în detaliu.

Să presupunem că avem date şirurile S şi T, şi să presupunem pentru moment că |S|=|T|=n. Deasemenea, să considerăm o funcţie de scor arbitrară σ(x,y), supusă unei restricţii rezonabile σ(-,-)≤0. Cu această restricţie, nu există niciodată motiv să aliniezi o pereche de spaţii. Algoritmul evident mai detaliat arată după cum urmează:

for all i,0≤i≤n, do
for all subsecvenţele A ale lui S cu |A|=i do
    for all subsecvenţele B ale lui T cu |B|=i do
      Formează alinierea care identifică A[k] cu B[k], 1≤k≤i,
        şi completează toate nepotrivirile cu spaţii;
      Calculează valoarea alinierii;
      Reţine alinierea cu cea mai mare valoare;
    end;
end;
end;
Listează alinierea obţinută.

Acest algoritm lucrează corect, dar este un bun algoritm? Dacă aţi fi încercat aplicarea acestui algoritm asupra unei perechi de şiruri fiecare de lungime 20 (lungime modestă după standardele biologice), poate aţi fi aflat că este mult prea lent pentru a fi practic. Programul ar rula mai mult de o oră cu astfel de date de intrare, chiar dacă calculatorul ar putea face un miliard de operaţii pe secundă.

Analiza timpului de rulare a acestui algoritm se face în modul următor. Un şir de lungime n are C_nⁱ subşiruri de lungime i (vom folosi în cele ce urmează notaţia utilizată în literatura de limbă engleză . Astfel, există V(i-1,j) perechi de subşiruri (A,B) de aliniat. Să considerăm o astfel de pereche. Întrucât există n caractere în S, numai i dintre ele vor fi aliniate cu caractere din T, vor exista atunci n-i caractere în S care nu sunt aliniate cu caractere din T. Astfel, deoarece pentru fiecare caracter nealiniat dintr-un şir trebuie introdus un spaţiu în celălalt şir, obţinem o lungime totală a secvenţei de caractere aliniate n+(n-i) = 2n-i. Trebuie să căutăm şi să adăugăm punctajul fiecărei perechi din aliniament (secvenţa aliniată pentru comparare), astfel încât numărul total de operaţii este cel puţin

(Egalitatea are o frumoasă explicaţie combinatorială care este dificil de găsit. Ultima inegalitate utilizează aproximaţia Stirling valabilă pentru n mari). Astfel, pentru S = acb, acest algoritm necesită mai mult de 2²ⁿ = 2⁴⁰ >(10³)⁴, adică 10 miliarde, operaţii (am folosit 2¹⁰ =1024~10³).

13-Nov-2009