А.В. Дубанов
4
1, 0 ;
1, 1
,
;
,
max
,
1 ;
1,
;
i
j
T i
T i
j
s a b
T i j
T i j
g
T i
j g
(3)
1, ,
1, ,
i
w j
h
(4)
где
T
(
i
,
j
) — заполняемая ячейка таблицы (
T
(
i
, 0) соответствует 0-й
ячейке
i
-го столбца);
s
(
a
i
,
b
j
) — оценка сходства (score — счет) между
символами
a
i
и
b
j
;
g
— штраф за разрыв последовательности (деле-
цию);
t
— некоторое пороговое значение, позволяющее отсечь случаи
слабого сходства, если в этом возникнет необходимость.
Выравнивание последовательностей получается путем
поиска
по-
следовательности ячеек в таблице исходя из принципа максимизации
оценки сходства
. Просмотр таблицы осуществляется справа налево,
т. е. индекс столбца
i
изменяется от
w
до 0. Непрерывные сходные
фрагменты представлены в таблице непрерывными последовательно-
стями ячеек с ненулевыми значениями, расположенными по диагонали
(далее диагоналями).
Поиск правого нижнего конца
диагонали
осуществляется путем
поиска максимального значения в очередном,
i
-м столбце таблицы.
Это может быть выражено следующими формулами:
0
0
0
(0, 0), 0,
0;
1 ,
0,
0;
1 ,
0,
0, ( , ) 0;
( , ),
0,
0,
,
0;
i
j
p i
i
j
p i
p i
i
j
T i j
i j
i
j
T i j
(5)
min |
,
max{ , },
0, ,
j
j T i j
T i j
j
h
(6)
где
i
— индекс столбца таблицы;
j
— индекс строки таблицы;
T
(
i
,
j
) —
значение в ячейке таблицы;
0
( )
p i
— функция для вычисления индек-
сов правого нижнего конца очередной диагонали в таблице, располо-
женного в столбце
i
или левее.
Результатом вычисления
0
( )
p i
будет пара (
i
,
j
), такая, что
T
(
i
,
j
)
является правым нижним концом диагонали. Значение
0
( ) (0, 0)
p i
указывает на то, что достигнут верхний левый угол таблицы, новых
похожих
подпоследовательностей
не
найдено.
Аналогично
0
( ) (0, )
p i
j
при любом допустимом
j
указывает на то, что достигнут
