Căutarea similarităţilor locale

49

    În continuare vom discuta câteva variante ale abordării programării dinamice la alinierea şirurilor. Vom face asta pentru a demonstra versatilitatea acestei abordări şi deoarece variantele apar în aplicaţiile biologice.

    La varianta numită similaritate locală, noi căutăm regiuni de similaritate între două şiruri în contextul în care ele pot să nu semene. Un exemplu în care acest fapt apare este dacă avem două lungi secvenţe de ADN care fiecare conţine o genă dată, sau poate gene înrudite apropiat, desigur, aliniamentul global al definiţiilor anterioare nu va identifica aceste gene.

Putem formula această problemă ca problema aliniamentului local: Fiind date două şiruri S şi T, cu |S|=n şi |T|=m, găsiţi subşirurile (adică secvenţele continue) A al lui S şi B al lui T astfel încât aliniamentul optim (global) a lui A şi B să aibă cea mai mare valoare dintre toate subşirurile A şi B. Cu alte cuvinte, aliniamentul optim a lui A şi B trebuie să aibă cel puţin aceeaşi valoare ca aliniamentul optim al oricăror altor subşiruri A’ al lui S şi B’ al lui T.

Un algoritm de aliniere locală evident

for all subşirurile A ale lui S do
  for all subşirurile B ale T do

1. Găseşte un aliniament optim al lui A şi B utilizând programarea dinamică;
2. Reţine subşirurile A şi B cu cea mai mare valoare a aliniamentului, şi aliniamentul lor;

  end;
end ;
Listează şirurile reţinute A, B şi aliniamentul lor; 

    Există posibilităţi de alegere a subşirului A şi pentru B. Folosind Teorema 2.6 nu este dificil de arătat că timpul necesar acestui algoritm este O(n³m³). Vom vedea în capitolul următor că este totuşi posibilă determinarea unui aliniament optim local într-un timp O(nm), adică cam acelaşi timp ca pentru aliniamentul optim global.

© Cornel Mironel Niculae, 2003-2008

13-Nov-2009