Разработка алгоритма

Для оценки сходства между строками X и Y имеется конкретное числовое опре- деление: это минимальная стоимость выравнивания между X и Y. Чем ниже эта стоимость, тем более похожими объявляются строки. Теперь обратимся к задаче вычисления этой минимальной стоимости и оптимального выравнивания, которое обеспечивает эту стоимость для заданной пары строк X и Y.

Для решения этой задачи можно попытаться применить динамическое про- граммирование, руководствуясь следующей базовой дихотомией.

♦ В оптимальном выравнивании M либо (m, n) M, либо (m, n) ⅜M. (То есть два

последних символа двух строк либо сопоставляются друг с другом, либо нет.)

Самого по себе этого факта недостаточно для того, чтобы предоставить решение методом динамического программирования. Однако предположим, что он допол- няется следующим базовым фактом:

(6.14) Пусть M — произвольное выравнивание X и Y. Если (m, n) ⅜ M, то либо m-я позиция X, либо n-я позиция Y не имеют сочетания в M.

Доказательство. Действуя от обратного, предположим, что (m, n) ⅜ M и суще- ствуют числа i < m и j < n, для которых (m, j) M и (i, n) M. Но это противо-

речит нашему определению выравнивания: имеем (i, n), (m, j) Mс i < m, но n > i, поэтому пары (i, n) и (m, j) пересекаются. ■

Существует эквивалентный вариант записи (6.14) с тремя альтернативными возможностями, приводящий напрямую к формулировке рекуррентного отноше- ния.

(6.15) В оптимальном выравнивании M истинно хотя бы одно из следующих трех условий:

♦ (i) (m, n) e M; или

♦ (ii) m-я позиция X не имеет сочетания; или

♦ (iii) n-я позиция Y не имеет сочетания.

Теперь пусть ОРТ(/',у) обозначает минимальную стоимость выравнивания между хрс, — х. и vtv, — yf Если выполняется условие (i) из (6.15), мы платим a⅛J5 и вы- равниваем x1x2 ··· xm1 сy1y2 ··· yn1 настолько хорошо, насколько это возможно; полу- чаем ОРТ(w/, n) = нл⅛>.

+ ОРТ(w; - 1, n - 1). Если выполняется условие (ii), мы платим

штраф за разрыв δ, потому что m-я позиция X не имеет сочетания, и выравниваем x1x2 ··· xm1 с y1y2 ··· yn1 настолько хорошо, насколько это возможно. В этом случае получаем OPT(m, n) = δ + OPT(m - 1, n). Аналогичным образом для случая (iii) полу- чаем OPT(m, n) = δ + OPT(m, n - 1).

Используя аналогичные рассуждения для подзадачи нахождения выравнива- ния с минимальной стоимостью для x1x2 ··· X. и y1y2 ··· y,, приходим к следующему факту:

(6.16) Стоимости минимального выравнивания удовлетворяют следующему рекуррентному отношению для i > 1 и j> 1:

Кроме того, (i, j) принадлежит оптимальному выравниванию M для этой под- задачи в том и только в том случае, если минимум достигается на первом из этих значений.

Мы добрались до точки, в которой алгоритм динамического программирования стал ясен: мы строим значения OPT(i, j), используя рекуррентное отношение в (6.16). Существуют только O(mn) подзадач, и OPT(m, n) дает искомое значение.

Теперь определим алгоритм для вычисления значения оптимального вырав- нивания. Для выполнения инициализации заметим, что OPT(i, 0) = OPT(О, i) = ίδ для всех i, так как совместить i-буквенное слово с 0-буквенным словом возможно только с использованием i разрывов.

Alignment(X, Y)

Массив A[0...m, 0...n]

Инициализировать A[i, 0] = і5 для всех i Инициализировать A[0, j] = ,δ для всех j

For j = 1.......... n

For i = 1.......... m

Использовать рекуррентное отношение из (6.16) для вычисления A[i, j]

Конец For Конец For Вернуть A[m, n]

Как и в случае с предыдущими алгоритмами динамического программирования, построение самого выравнивания осуществляется обратным отслеживанием по массиву A с использованием второй части факта (6.16).

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Разработка алгоритма:

  1. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  2. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  3. АЛГОРИТМ
  4. АЛГОРИТМ УДАЧИ
  5. Алгоритм исцеления:
  6. Алгоритм избавления от боли
  7. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  8. Алгоритм обработки результатов.
  9. 2. Специфика и алгоритмы работы с источниками.
  10. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.