Алгоритм Хиршберга - Hirschberg's algorithm

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

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

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

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

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-й символ в , где . обозначает подстроку размера от i-го до j-го символа . это обратная версия . ${\ displaystyle X}$${\ Displaystyle 1 \ leqslant я \ leqslant \ OperatorName {длина} (X)}$${\ displaystyle X_ {i: j}}$${\ displaystyle j-i + 1}$${\ 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)}$

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

Обратите внимание, что в любой момент требуются только две самые последние строки матрицы оценок. Таким образом, реализовано в космосе. ${\ displaystyle \ operatorname {NWScore}}$${\ displaystyle \ operatorname {NWScore}}$${\ Displaystyle О (\ мин \ {\ имя оператора {длина} (Х), \ имя оператора {длина} (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) предположим, что это разделение . Индекс вычисляется таким образом, что и . ${\ 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 {align} X & = {\ text {AGTACGCA}}, \\ Y & = {\ text {TATGC}}, \\\ имя оператора {Del} (x) & = - 2, \\\ имя оператора {Ins} (y) & = - 2, \\\ operatorname {Sub} (x, y) & = {\ begin {cases} +2, & {\ text {if}} x = y \\ - 1, & {\ text {if}} x \ neq y. \ end {case}} \ end {выровнены}}}$

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

 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

Один начинается с вызова верхнего уровня к , который разделяет первый аргумент пополам: . Обращение к производит следующую матрицу: ${\ displaystyle \ operatorname {Hirschberg} ({\ text {AGTACGCA}}, {\ text {TATGC}})}$${\ displaystyle X = {\ text {AGTA}} + {\ text {CGCA}}}$${\ displaystyle \ 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

Таким же образом создается следующая матрица: ${\ displaystyle \ 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, создавая раздел . ${\ displaystyle 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) 

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

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

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

использованная литература