Материал: Учебное пособие Немирко Манило

Алгоритм расчета оптимального выравнивания основан на вычислении расстояния редактирования между префиксами слов U и V длины i и j использованием значения расстояний редактирования для более коротких префиксов. Обозначим через Wδ (i, j), 0 ≤ i ≤ m, 0 ≤ j ≤ n стоимость оптималь-

ного выравнивания (u1, u2, , ui ) и (v1, v2, , v j ). На каждом шаге процедуры выравнивания используются следующие рекуррентные соотношения:

равнивания для пар последовательностей меньшей длины. Оно выполнено на предыдущих шагах процедуры выравнивания.

Собственно выравнивание строится в процессе последовательного продвижения по узлам сети в направлении от истока к стоку. На каждом шаге выравнивания производится условная оптимизация управления, задаваемого

набором возможных операций: замена δ(ui+1 → v j+1 ), вставка δ(ε → v j+1 ) или удаление δ(ui+1 → ε) последнего символа анализируемого фрагмента

слова U . Как следует из (2.4), стоимость выравнивания пустых слов задается равной нулю. Выражение (2.5) оценивает суммарные затраты при движении по узлам, расположенным на верхней горизонтали сети. Соответственно, выражение (2.6) связано с оценкой затрат при движении по левой вертикали сети. Соотношение (2.7) используется для условной оптимизации во всех остальных узлах ориентированного графа: выбирается то шаговое управление, которое обеспечивает минимум суммарных затрат.

Возвращаясь к задаче временного выравнивания последовательностей символов T1 и T2 , следует отметить, что стоимость δ(ui+1 → v j+1 ) здесь принимается равной 0, так как эта операция допустима лишь в случае совпаде-

61

ния указанных символов (хотя в некоторых случаях может быть введена и стоимость операции замены). Стоимости операций удаления δ(ui+1 → ε) и

вставки символа δ(ε → v j+1 ) заданы равными 1.

Используя рекуррентные соотношения (2.4)–(2.7) в процедуре оптимального выравнивания T1 и T2 , которая строится последовательно от вершины S0 к вершине Sk , получим результат условной оптимизации, представленный на рис. 2.18. Здесь для каждого узла сетки (i, j), соответствующего промежуточному состоянию Si, j , стрелками указаны траектории (по-

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

последующие два символа сохраняются, а последний символ b также подлежит удалению.

Напротив, в цепочке a a вначале добавляется символ a , последующие два символа сохраняются, а в конце цепочки вставлен символ b. После выравнивания соответствующие префиксы принимают вид T1 (−, a, a, −) и

T2 (a, a, a, b).

62

Рис. 2.18

Здесь тире обозначает пустые символы, а запятые являются разделителями и введены для удобства сравнения символов, стоящих в одинаковых позициях. Суммарные затраты такого выравнивания составляют 2 единицы, что отмечено в кружке конечной для префикса вершины S4,2 . Как следует из ри-

сунка, оптимальная траектория для сравниваемых префиксов оказалась не единственной, но все эквивалентные пути выравнивания требуют одинаковых затрат.

Затем в соответствии со схемой решения задач динамического программирования строится траектория из S0 в Sk , которая обеспечивает выравнивание полных слова T1 и T2 с минимальными затратами. Результат такой безусловной оптимизации показан на рис. 2.19.

63

Таблица 2.6

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

64

столбец содержит упорядоченные последовательности символов, которые получены в результате трансформации исходных слов T1 = a a a b b c a a и

T2 = a a b c b .

Выравнивание слова T1 в соответствии с верхней траекторией ориентированного графа предполагает выполнение следующей последовательности шагов (рис. 2.20):

1) удаление символа a :

(a → ε); S0,0 → S1,0 ; T1 = (−); W (T1, T2 )=1;

2)сохранение символа a :

(a → a); S1,0 → S2,1 ; T1 = (−, a); W (T1, T2 )=1;

3)сохранение символа a :

(a → a); S2,1 → S3,2 ; T1 = (−, a, a); W (T1, T2 )=1;

4)удаление символа b:

(b → ε); S3,2 → S4,2 ; T1 = (−, a, a, −); W (T1, T2 )= 2 ;

5)сохранение символа b:

(b → b); S4,2 → S5,3; T1 = (−, a, a, −, b); W (T1, T2 )= 2 ;

6)сохранение символа с:

(c → c); S5,3 → S6,4 ; T1 = (−, a, a, −, b, c), W (T1, T2 )= 2 ;

7)удаление символа a :

(a → ε); S6,4 → S7,4 ; T1 = (−, a, a, −, b, c, −), W (T1, T2 )= 3;

8)удаление символа a :

(a → ε); S7,4 → S8,4 ; T1 = (−, a, a, −, b, c, −, −), W (T1, T2 )= 4 ;

9)вставка символа b:

(ε → b); S8,4 → S8,5 ; T1 = (−, a, a, −, b, c, −, −, b), W (T1, T2 )= 5.

65