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

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

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

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

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

  1. можно вычислить оптимальную оценку выравнивания, сохранив только текущую и предыдущую строки матрицы оценок Нидлмана-Вунша;
  2. если оптимальное выравнивание , и является произвольным разбиением , существует раздел из такой, что .

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

обозначает i-й символ , куда . обозначает подстроку размера , от 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) возвращаться Последняя линия

Обратите внимание, что в любой момент требуются только две самые последние строки матрицы оценок. Таким образом, реализуется в Космос

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

функция Хиршберг (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) предположим, что это раздел . Индекс вычисляется так, что и .

Пример

Позволять

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

 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

Каждый начинается с призыва на высшем уровне к , который разбивает первый аргумент пополам: . Призыв к производит следующую матрицу:

        Т А Т Г С    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

Так же, генерирует следующую матрицу:

       С Г Т А Т    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}}}, производя перегородку .

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

               (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.