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

редактировать

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

СОДЕРЖАНИЕ

1 Информация об алгоритме
2 Описание алгоритма
3 Пример
4 См. Также
5 ссылки

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

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

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

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

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

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

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

Мы определяем, который возвращает последнюю строку матрицы очков Нидлмана – Вунша: ${\ displaystyle \ operatorname {NWScore} (X, Y)}$ $\ operatorname {NWScore} (X, Y)$ ${\ displaystyle \ mathrm {Score} (i, j)}$ ${\ 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}}$ $\ operatorname {NWScore}$ ${\ displaystyle \ operatorname {NWScore}}$ $\ operatorname {NWScore}$ ${\ Displaystyle О (\ мин \ {\ имя оператора {длина} (Х), \ имя оператора {длина} (Y) \})}$ ${\ 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}}$ $X ^ {l} + X ^ {r}$ ${\ displaystyle X}$ $Икс$ ${\ displaystyle \ mathrm {ymid}}$ ${\ mathrm {ymid}}$ ${\ displaystyle Y ^ {l} = Y_ {1: \ mathrm {ymid}}}$ $Y ^ {l} = Y _ {{1: {\ mathrm {ymid}}}}$ ${\ displaystyle Y ^ {r} = Y _ {\ mathrm {ymid} +1: \ operatorname {length} (Y)}}$ $Y ^ {r} = Y _ {{\ mathrm {ymid}} + 1: \ operatorname {length} (Y)}}$

Пример

Позволять

${\ displaystyle {\ begin {align} X amp; = {\ text {AGTACGCA}}, \\ Y amp; = {\ text {TATGC}}, \\\ имя оператора {Del} (x) amp; = - 2, \\\ имя оператора {Ins} (y) amp; = - 2, \\\ operatorname {Sub} (x, y) amp; = {\ begin {cases} +2, amp; {\ text {if}} x = y \\ - 1, amp; {\ text {if}} x \ neq y. \ end {case}} \ end {выровнены}}}$ ${\ displaystyle {\ begin {align} X amp; = {\ text {AGTACGCA}}, \\ Y amp; = {\ text {TATGC}}, \\\ имя оператора {Del} (x) amp; = - 2, \\\ имя оператора {Ins} (y) amp; = - 2, \\\ operatorname {Sub} (x, y) amp; = {\ begin {cases} +2, amp; {\ text {if}} x = y \\ - 1, amp; {\ 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 \ operatorname {Hirschberg} ({\ text {AGTACGCA}}, {\ text {TATGC}})}$ ${\ displaystyle X = {\ text {AGTA}} + {\ text {CGCA}}}$ ${\ displaystyle X = {\ text {AGTA}} + {\ text {CGCA}}}$ ${\ displaystyle \ operatorname {NWScore} ({\ text {AGTA}}, Y)}$ ${\ 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))}$ ${\ 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}}}$ ${\ 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)

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

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

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

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