Алгоритм Хиршберга - Hirschbergs algorithm - Wikipedia

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

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

Алгоритм Хиршберга - это широко применяемый алгоритм для оптимального выравнивания последовательностей. ВЗРЫВ и FASTA неоптимальны эвристика. Если Икс и у - строки, где длина (Икс) = п и длина (у) = м, то Алгоритм Нидлмана-Вунша находит оптимальное соответствие О (нм) время, используя O (нм) Космос. Алгоритм Хиршберга - это умная модификация алгоритма Нидлмана-Вунша, который по-прежнему требует O (нм) времени, но требуется только O (min {п,м}) и на практике работает намного быстрее.^[2]Одно из применений алгоритма - поиск выравнивания последовательностей ДНК или белков. Это также компактный способ расчета самая длинная общая подпоследовательность между двумя наборами данных, например, с общим разница инструмент.

Алгоритм Хиршберга можно вывести из алгоритма Нидлмана-Вунша, заметив, что:^[3]

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

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

${\displaystyle X_{i}}$ обозначает i-й символ ${\displaystyle X}$, куда ${\displaystyle 1\leqslant i\leqslant \operatorname {length} (X)}$. ${\displaystyle X_{i:j}}$ обозначает подстроку размера ${\displaystyle j-i+1}$, от i-го до j-го символа ${\displaystyle X}$. ${\displaystyle \operatorname {rev} (X)}$ это обратная версия ${\displaystyle X}$.

${\displaystyle X}$ и ${\displaystyle Y}$ представляют собой выравниваемые последовательности. Позволять ${\displaystyle x}$ быть персонажем из ${\displaystyle X}$, и ${\displaystyle y}$ быть персонажем из ${\displaystyle Y}$. Мы предполагаем, что ${\displaystyle \operatorname {Del} (x)}$, ${\displaystyle \operatorname {Ins} (y)}$ и ${\displaystyle \operatorname {Sub} (x,y)}$ - корректно определенные целочисленные функции. Эти функции представляют собой стоимость удаления ${\displaystyle x}$, вставка ${\displaystyle y}$и заменив ${\displaystyle x}$ с ${\displaystyle y}$, соответственно.

Мы определяем ${\displaystyle \operatorname {NWScore} (X,Y)}$, который возвращает последнюю строку матрицы очков Нидлмана-Вунша ${\displaystyle \mathrm {Score} (i,j)}$:

функция NWScore (X, Y) Score (0,0) = 0 // 2 * (длина (Y) + 1) массив за j = 1 к длина (Y) Оценка (0, j) = Оценка (0, j - 1) + Ins (Yj)    за я = 1 к length (X) // Исходный массив Score (1,0) = Score (0, 0) + Del (Xя)        за j = 1 к длина (Y) scoreSub = Score (0, j - 1) + Sub (Xя, Yj) scoreDel = Score (0, j) + Del (Xя) scoreIns = Score (1, j - 1) + Ins (Yj) Score (1, j) = max (scoreSub, scoreDel, scoreIns) конец        // Копируем Score [1] в Score [0] Score (0, :) = Score (1, :) конец    за j = 0 к length (Y) LastLine (j) = Score (1, j) возвращаться Последняя линия

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

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

функция Хиршберг (X, Y) Z = "" W = "" если длина (X) == 0 за я = 1 к длина (Y) Z = Z + '-' W = W + Yя        конец    иначе если длина (Y) == 0 за я = 1 к длина (X) Z = Z + Xя            W = W + '-' конец    иначе если длина (X) == 1 или же длина (Y) == 1 (Z, W) = NeedlemanWunsch (X, Y) еще        xlen = длина (X) xmid = длина (X) / 2 ylen = длина (Y) ScoreL = NWScore (X1: xmid, Y) ScoreR = NWScore (rev (Xxmid + 1: xlen), rev (Y)) ymid = arg max ScoreL + rev (ScoreR) (Z, W) = Хиршберг (X1: xmid, y1: ymid) + Хиршберг (Xxmid + 1: xlen, Yymid + 1: ylen)    конец    возвращаться (Z, W)

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

Пример

Позволять

${\displaystyle {\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-

В самом деле, это можно проверить, проследив соответствующую матрицу Нидлмана-Вунша:

         Т А Т Г С     0  -2  -4  -6  -8 -10 А  -2  -1   0  -2  -4  -6 грамм  -4  -3  -2  -1   0  -2 Т  -6  -2  -4   0  -2  -1 А  -8  -4   0  -2  -1  -3 C -10  -6  -2  -1  -3   1 грамм -12  -8  -4  -3   1  -1 C -14 -10  -6  -5  -1   3 А -16 -12  -8  -7  -3   1

Каждый начинается с призыва на высшем уровне к ${\displaystyle \operatorname {Hirschberg} (\mathrm {AGTACGCA} ,\mathrm {TATGC} )}$, который разбивает первый аргумент пополам: ${\displaystyle X=\mathrm {AGTA} +\mathrm {CGCA} }$. Призыв к ${\displaystyle \operatorname {NWScore} (\mathrm {AGTA} ,Y)}$ производит следующую матрицу:

        Т А Т Г С    0  -2  -4  -6  -8 -10 А -2  -1   0  -2  -4  -6 грамм -4  -3  -2  -1   0  -2 Т -6  -2  -4   0  -2  -1 А -8  -4   0  -2  -1  -3

Так же, ${\displaystyle \operatorname {NWScore} (\operatorname {rev} (\mathrm {CGCA} ),\operatorname {rev} (Y))}$ генерирует следующую матрицу:

       С Г Т А Т    0 -2  -4  -6  -8 -10 А -2 -1  -3  -5  -4  -6 C -4  0  -2  -4  -6  -5 грамм -6 -2   2   0  -2  -4 C -8 -4   0   1  -1  -3

Их последние строки (после изменения последнего) и их сумма соответственно

 ScoreL = [-8-4 0-2-1-3] об. (ScoreR) = [-3-1 1 0-4-8] Сумма = [-11-5 1 -2 -5 -11]

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

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

               (AGTACGCA, TATGC) /  (AGTA, TA) (CGCA, TGC) /  /  (AG,) (TA, TA) (CG, TG) (CA, C) /  /  (T, T) ( А, А) (С, Т) (G, G) 

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

Смотрите также

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

Рекомендации

1. Алгоритм Хиршберга
2. http://www.cs.tau.ac.il/~rshamir/algmb/98/scribe/html/lec02/node10.html
3. Хиршберг, Д.С. (1975). «Алгоритм линейного пространства для вычисления максимальных общих подпоследовательностей». Коммуникации ACM. 18 (6): 341–343. CiteSeerX  10.1.1.348.4774. Дои:10.1145/360825.360861. МИСТЕР  0375829. S2CID  207694727.