Алгоритм Хиршберга

В информатике , алгоритм Хиршберга , названный в честь его изобретателя Дэна Хиршберга , представляет собой динамического программирования алгоритм который находит оптимальное выравнивание последовательности между двумя строками . Оптимальность измеряется расстоянием Левенштейна , определяемым как сумма затрат на вставки, замены, удаления и нулевые действия, необходимые для замены одной строки на другую. Алгоритм Хиршберга просто описывается как более компактная версия алгоритма Нидлмана-Вунша , который использует разделяй и властвуй . Алгоритм Хиршберга обычно используется в вычислительной биологии для поиска максимального глобального выравнивания последовательностей ДНК и белков .

Информация об алгоритме

Алгоритм Хиршберга является общеприменимым алгоритмом оптимального выравнивания последовательностей. BLAST и FASTA — неоптимальные эвристики . Если $X$ и $Y$ представляют собой строки, где $\operatorname {length} (X)=n$ и $\operatorname {length} (Y)=m$алгоритм Нидлмана-Вунша находит оптимальное выравнивание в $O(nm)$ время, используя $O(nm)$ космос. Алгоритм Хиршберга представляет собой умную модификацию алгоритма Нидлмана-Вунша, который по-прежнему требует $O(nm)$ время, а нужно только $O(\min\{n,m\})$ пространстве и на практике работает намного быстрее. Одним из применений алгоритма является поиск выравниваний последовательностей ДНК или белков. Это также экономичный способ вычисления самой длинной общей подпоследовательности между двумя наборами данных, например, с помощью общего инструмента сравнения .

Алгоритм Хиршберга можно получить из алгоритма Нидлмана – Вунша, если заметить, что:

1. можно вычислить оптимальную оценку выравнивания, сохраняя только текущую и предыдущую строку матрицы оценок Нидлмана – Вунша;
2. если $(Z,W)=\operatorname {NW} (X,Y)$ это оптимальное выравнивание $(X,Y)$, и $X=X^{l}+X^{r}$ является произвольным разбиением $X$, существует раздел $Y^{l}+Y^{r}$ из $Y$ такой, что $\operatorname {NW} (X,Y)=\operatorname {NW} (X^{l},Y^{l})+\operatorname {NW} (X^{r},Y^{r})$.

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

$X_{i}$ обозначает i -й символ $X$, где $1\leqslant i\leqslant \operatorname {length} (X)$. $X_{i:j}$ обозначает подстроку размера $j-i+1$, начиная с i -го и заканчивая j -м символом $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)$, который возвращает последнюю строку матрицы оценок Нидлмана-Вунша $\mathrm {Score} (i,j)$:

function NWScore(X, Y)
    Score(0, 0) = 0 // 2 * (length(Y) + 1) array
    for j = 1 to length(Y)
        Score(0, j) = Score(0, j - 1) + Ins(Yj)
    for i = 1 to length(X) // Init array
        Score(1, 0) = Score(0, 0) + Del(Xi)
        for j = 1 to length(Y)
            scoreSub = Score(0, j - 1) + Sub(Xi, Yj)
            scoreDel = Score(0, j) + Del(Xi)
            scoreIns = Score(1, j - 1) + Ins(Yj)
            Score(1, j) = max(scoreSub, scoreDel, scoreIns)
        end
        // Copy Score[1] to Score[0]
        Score(0, :) = Score(1, :)
    end
    for j = 0 to length(Y)
        LastLine(j) = Score(1, j)
    return LastLine

Обратите внимание, что в любой момент $\operatorname {NWScore}$ требуются только две последние строки матрицы оценок. Таким образом, $\operatorname {NWScore}$ реализуется в $O(\min\{\operatorname {length} (X),\operatorname {length} (Y)\})$ космос.

Алгоритм Хиршберга следующий:

function Hirschberg(X, Y)
    Z = ""
    W = ""
    if length(X) == 0
        for i = 1 to length(Y)
            Z = Z + '-'
            W = W + Yi
        end
    else if length(Y) == 0
        for i = 1 to length(X)
            Z = Z + Xi
            W = W + '-'
        end
    else if length(X) == 1 or length(Y) == 1
        (Z, W) = NeedlemanWunsch(X, Y)
    else
        xlen = length(X)
        xmid = length(X) / 2
        ylen = length(Y)

        ScoreL = NWScore(X1:xmid, Y)
        ScoreR = NWScore(rev(Xxmid+1:xlen), rev(Y))
        ymid = arg max ScoreL + rev(ScoreR)

        (Z,W) = Hirschberg(X1:xmid, y1:ymid) + Hirschberg(Xxmid+1:xlen, Yymid+1:ylen)
    end
    return (Z, W)

В контексте наблюдения (2) предположим, что $X^{l}+X^{r}$ является разделом $X$. Индекс $\mathrm {ymid}$ вычисляется так, что $Y^{l}=Y_{1:\mathrm {ymid} }$ и $Y^{r}=Y_{\mathrm {ymid} +1:\operatorname {length} (Y)}$.

Пример

Позволять

${\begin{aligned}X&={\text{AGTACGCA}},\\Y&={\text{TATGC}},\\\operatorname {Del} (x)&=-2,\\\operatorname {Ins} (y)&=-2,\\\operatorname {Sub} (x,y)&={\begin{cases}+2,&{\text{if }}x=y\\-1,&{\text{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} ({\text{AGTACGCA}},{\text{TATGC}})$, который делит первый аргумент пополам: $X={\text{AGTA}}+{\text{CGCA}}$. Звонок в $\operatorname {NWScore} ({\text{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

Так же, $\operatorname {NWScore} (\operatorname {rev} ({\text{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 ]
 rev(ScoreR) = [ -3 -1  1  0 -4 -8 ]
 Sum         = [-11 -5  1 -2 -5 -11]

Максимум (выделен жирным шрифтом) появляется при ymid = 2, создавая раздел $Y={\text{TA}}+{\text{TGC}}$.

Вся рекурсия Хиршберга (которую мы опускаем для краткости) дает следующее дерево:

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

Листья дерева имеют оптимальное расположение.

См. также

• Самая длинная общая подпоследовательность