Хирсбергов алгоритам

У свету рачунара, Хирсбергов алгоритам, који је добио име по проналазачу, Дан Хирсцхберг, је алгоритам динамичког програмирања који проналази оптимално поравнавање секвенци између две ниске карактера. Оптималност се мери коришћењем Левенштајновог растојања, који је дефинисан као збир цена операција потребних да се од прве ниске добије друга. Могуце операције су уметања, брисања и замена једног карактера другим. Хирсбергов алгоритам је једноставно описан као подели па владај модификација алгоритма познатог као Нидлмен-Ваншов алгоритам. Хирсбергов алгоритам се најчешће користи у биоинформатици за поравнање секвенци протеина или нуклеотида у ДНК.

Информације о алгоритму

Хирсбергов алгоритам је генерално применљив за проналажење оптималног поравнања секвенци. Нека су X и Y ниске и нека је дужина X једнака н, а дужина Y једнака м. Тада Нидлмен-Ваншов алгоритам проналази оптимално поравнање са временском сложеношћу О(нм) и просторном сложеношћу О(нм). Хирсбергов алгоритам представља паметну модификацију Нидлмен-Ваншовог алгоритма, са истом временском сложеношћу О(нм) али са великом уштедом на просторној сложености која у најгорем случају износи О(мин{н,м}). Поред примене овог алгоритма за проналажење оптималног поравнање секвенци протеина или нуклеотида у ДНК, Хирсбергов алгоритам се може применити за проналажење најдуже заједничке подниске.

Опис алгоритма

$X[i]$ представља и-ти карактер $X-a$, и важи да је $i$ између 1 и дужине ниске $X$. $\operatorname {rev} (X)$ представља обрнуту ниску $X$.

$X$ и $Y$ су улазне секвенце које треба поравнати. Нека је $x$ карактер из ниске $X$, и нека је $y$ карактер из ниске $Y$. Претпоставимо да су $\operatorname {Del} (x)$, $\operatorname {Ins} (y)$ анд $\operatorname {Sub} (x,y)$ добро дефинисане функције. Повратне вредности ових функција представљају цене операција брисања $x$, уметања $y$ и замене карактера $x$ карактером $y$.

Дефинисемо функцију $\operatorname {NWScore}$ која као аргументе прима $X$ и $Y$ а враца последњи ред Нидлмен-Ваншове матрице.

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 ; 
}

Хисбергов алгоритам који користи изнад дефинисану функцију:

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;
}

Пример

Нека су нам улазни подаци следећи: ${\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}}$

Тада је оптимално поравнање:

 W = AGTACGCA
 Z = --TATGC-

Нидлмен-Ваншове матрица је:

         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

Алгоритам запоциње позивом $\operatorname {Hirschberg} (\mathrm {AGTACGCA} ,\mathrm {TATGC} )$. Позив функције $\operatorname {NWScore} (\mathrm {AGTA} ,Y)$ производи следећу матрицу:

        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

Поyив функције $\operatorname {NWScore} (\operatorname {rev} (\mathrm {CGCA} ),\operatorname {rev} (Y))$ производи следећу матрицу:

       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

Последњи редови произведених матрица су:

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

ПартитионY(СцореЛ, СцореР) = 2, тако да су поделе $X=\mathrm {AGTA} +\mathrm {CGCA}$ и $Y=\mathrm {TA} +\mathrm {TGC}$.

Рекурзија Хисберговог алгоритма производи стабло:

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

Листови стабла садрже оптимално поравнање.

Повезани чланци

• Левенштајново растојање
• Динамичко програмирање
• Нидлмен-Ваншов алгоритам
• Најдужа заједничка подниска