Hirsbergov algoritam

U svetu računara, Hirsbergov algoritam, koji je dobio ime po pronalazaču, Dan Hirschberg, je algoritam dinamičkog programiranja koji pronalazi optimalno poravnavanje sekvenci između dve niske karaktera. Optimalnost se meri korišćenjem Levenštajnovog rastojanja, koji je definisan kao zbir cena operacija potrebnih da se od prve niske dobije druga. Moguce operacije su umetanja, brisanja i zamena jednog karaktera drugim. Hirsbergov algoritam je jednostavno opisan kao podeli pa vladaj modifikacija algoritma poznatog kao Nidlmen-Vanšov algoritam. Hirsbergov algoritam se najčešće koristi u bioinformatici za poravnanje sekvenci proteina ili nukleotida u DNK.

Informacije o algoritmu

Hirsbergov algoritam je generalno primenljiv za pronalaženje optimalnog poravnanja sekvenci. Neka su X i Y niske i neka je dužina X jednaka n, a dužina Y jednaka m. Tada Nidlmen-Vanšov algoritam pronalazi optimalno poravnanje sa vremenskom složenošću O(nm) i prostornom složenošću O(nm). Hirsbergov algoritam predstavlja pametnu modifikaciju Nidlmen-Vanšovog algoritma, sa istom vremenskom složenošću O(nm) ali sa velikom uštedom na prostornoj složenosti koja u najgorem slučaju iznosi O(min{n,m}). Pored primene ovog algoritma za pronalaženje optimalnog poravnanje sekvenci proteina ili nukleotida u DNK, Hirsbergov algoritam se može primeniti za pronalaženje najduže zajedničke podniske.

Opis algoritma

$X[i]$ predstavlja i-ti karakter $X-a$ , i važi da je $i$ između 1 i dužine niske $X$ . $\operatorname {rev} (X)$ predstavlja obrnutu nisku $X$ .

$X$ i $Y$ su ulazne sekvence koje treba poravnati. Neka je $x$ karakter iz niske $X$ , i neka je $y$ karakter iz niske $Y$ . Pretpostavimo da su $\operatorname {Del} (x)$ , $\operatorname {Ins} (y)$ and $\operatorname {Sub} (x,y)$ dobro definisane funkcije. Povratne vrednosti ovih funkcija predstavljaju cene operacija brisanja $x$ , umetanja $y$ i zamene karaktera $x$ karakterom $y$ .

Definisemo funkciju $\operatorname {NWScore}$ koja kao argumente prima $X$ i $Y$ a vraca poslednji red Nidlmen-Vanšove matrice.

vector<int> NWScore (vector<char> &X, vector<char> &Y )
{
    Score[0][0] = 0;
    int ny = Y.size();
    for (int j=1;j< ny;j++)
        Score[0][j] = Score[0][j-1] + Ins(Y[j]);
    int nx = X.size(); 
    for(int i=1; i< nx;i++){ 
        Score[i][0] = Score[i-1][0] + Del(X[i]);
        for(int j=1; j<ny;j++){
           int scoreSub = Score[i-1][j-1] + Sub(X[i], Y[j]);
           int scoreDel = Score[i-1][j] + Del(X[i]);
           int scoreIns = Score[i][j-1] + Ins(Y[j]);
           Score[i][j] = max(scoreSub, scoreDel, scoreIns);
        }
    }
    for(int j=1; j<ny;j++)
        LastLine[j] = Score[nx][j];
    return LastLine ; 
}

Hisbergov algoritam koji koristi iznad definisanu funkciju:

pair<vector<char>,vector<char> > Hirschberg(vector<char> &X, vector<char> &Y ){
	vector<char> Z;
	vector<char> W;
	pair<vector<char>,vector<char> > result;
	int ny = Y.size();
	int nx = X.size();
	if( nx == 0)
	{
	 for(int i=0;i<ny;i++){
		Z.push_back('-');
		W.push_back(Y[i]);
	 }
	}
	else if (ny == 0){
	 for(int i=0;i<ny;i++){
		Z.push_back(X[i]);
		W.push_back('-');
             }
	}
	else if (nx == 1 || ny == 1){
	 result = NeedlemanWunsch(X, Y);
	}
	else{
	 int xlen = X.size();
	 int xmid = X.size()/2;
	 int ylen = Y.size();
	 vector<char> Xleft, Xright;
	 copy(X.begin(), X.begin() + xmid, back_inserter(Xleft));
             copy(X.begin()+xmid + 1, X.end(), back_inserter(Xright));
	 ScoreL = NWScore(Xleft, Y);
             ScoreR = NWScore(rev(Xright), rev(Y));
	 int ymid = PartitionY(ScoreL, ScoreR);
	 vector<char> Yleft, Yright;
             copy(Y.begin(), Y.begin() + ymid, back_inserter(Yleft));
	 copy(Y.begin()+ymid + 1, Y.end(), back_inserter(Yright));
		
	 pair<vector<char>,vector<char> > resultLeft = Hirschberg(Xleft, Yleft);
             pair<vector<char>,vector<char> > resultRight = Hirschberg(Xright, Yright);
		
	 result.first = resultLeft.first;
             result.second = resultLeft.second;
		
	 copy((resultRight.first).begin(), (resultRight.first).end(), back_inserter(result.first));
	 copy((resultRight.second).begin(), (resultRight.second).end(), back_inserter(result.second));
	}
	return result;
}

Primer

Neka su nam ulazni podaci sledeći: ${\begin{aligned}X&=\mathrm {AGTACGCA} ,\\Y&=\mathrm {TATGC} ,\\\operatorname {Del} (x)&=-2,\\\operatorname {Ins} (y)&=-2,\\\operatorname {Sub} (x,y)&={\begin{cases}+2,&{\mbox{if }}x=y\\-1,&{\mbox{if }}x\neq y.\end{cases}}\end{aligned}}$

Tada je optimalno poravnanje:

 W = AGTACGCA
 Z = --TATGC-

Nidlmen-Vanšove matrica je:

         T   A   T   G   C
     0  -2  -4  -6  -8 -10
 A  -2  -1   0  -2  -4  -6
 G  -4  -3  -2  -1   0  -2
 T  -6  -2  -4   0  -2  -1
 A  -8  -4   0  -2  -1  -3
 C -10  -6  -2  -1  -3   1
 G -12  -8  -4  -3   1  -1
 C -14 -10  -6  -5  -1   3
 A -16 -12  -8  -7  -3   1

Algoritam zapocinje pozivom $\operatorname {Hirschberg} (\mathrm {AGTACGCA} ,\mathrm {TATGC} )$ . Poziv funkcije $\operatorname {NWScore} (\mathrm {AGTA} ,Y)$ proizvodi sledeću matricu:

        T   A   T   G   C
    0  -2  -4  -6  -8 -10
 A -2  -1   0  -2  -4  -6
 G -4  -3  -2  -1   0  -2
 T -6  -2  -4   0  -2  -1
 A -8  -4   0  -2  -1  -3

Poyiv funkcije $\operatorname {NWScore} (\operatorname {rev} (\mathrm {CGCA} ),\operatorname {rev} (Y))$ proizvodi sledeću matricu:

       C   G   T   A   T
    0 -2  -4  -6  -8 -10
 A -2 -1  -3  -5  -4  -6
 C -4  0  -2  -4  -6  -5
 G -6 -2   2   0  -2  -4
 C -8 -4   0   1  -1  -3

Poslednji redovi proizvedenih matrica su:

 ScoreL = [ -8 -4  0 -2 -1 -3 ]
 ScoreR = [ -8 -4  0  1 -1 -3 ]

PartitionY(ScoreL, ScoreR) = 2, tako da su podele $X=\mathrm {AGTA} +\mathrm {CGCA}$ i $Y=\mathrm {TA} +\mathrm {TGC}$ .

Rekurzija Hisbergovog algoritma proizvodi stablo:

               (AGTACGCA,TATGC)
               /              \
        (AGTA,TA)            (CGCA,TGC)
         /     \              /      \
     (AG,)   (TA,TA)      (CG,TG)  (CA,C)
              /   \        /   \
           (T,T) (A,A)  (C,T) (G,G)

Listovi stabla sadrže optimalno poravnanje.