Сравнение исходных текстов программ путем выравнивания…
5
крайний левый столбец таблицы и новых сходных подпоследователь-
ностей не может быть найдено. В случае если
i
-й символ не входит в
подпоследовательность последовательности
A
, которой соответствует
похожая на нее подпоследовательность в последовательности
B
, пер-
вое в столбце (при просмотре ячеек сверху вниз) максимальное значе-
ние будет найдено в ячейке с индексом
j
= 0. В этом случае поиск
нижнего правого конца непрерывной диагонали продолжается в
столбце с индексом
i
− 1.
После нахождения правого нижнего конца диагонали осуществля-
ется
поиск входящих в диагональ ячеек
, который продолжается до тех
пор, пока не будет встречено нулевое значение в ячейке с индексами
i
> 0 и
j
> 0. При этом правый нижний конец диагонали включается в
последовательность пар символов, входящих в похожие последователь-
ности
A
и
B
. В противном случае осуществляется поиск новой диагона-
ли. Поиск завершается по достижении крайнего левого столбца табли-
цы, где
p
(
i
,
j
) принимает значение ( ) (пустая последовательность).
Такой поиск может быть описан следующей рекурсивной формулой:
0
0
( ),
0;
(
)( 1),
0,
0;
( , )
(
)( 1),
0,
0,
,
0;
( , ) , ( 1, 1) ,
0,
0,
,
0,
i
p p i
i
j
p i j
p p i
i
j
T i j
i j p i
j
i
j
T i j
(7)
где
p
(
i
,
j
) — функция вычисления очередной пары в выравнива-
нии, следующей за парой (
i
,
j
) в общей последовательности
( , ) , ( 1, 1)
i j p i
j
(показана в виде вложенных пар, в программе реа-
лизована в виде списка), соответствующей парам символов
a
i
и
b
j
, вхо-
дящих в состав сходных подпоследовательностей последовательно-
стей
A
и
B
.
Как было отмечено, поиск диагоналей в таблице осуществляется
справа налево. Поскольку первая диагональ может быть найдена по
формулам (5) и (6), то последовательность всех пар символов, входя-
щих в непересекающиеся наиболее похожие подпоследовательности,
двух последовательностей может быть задана формулой
0
,
P p p w
(8)
где
P
— последовательность пар индексов (
i
,
j
), которая и является ис-
комым выравниванием.
Таким образом удается найти непрерывные непересекающиеся
сходные подпоследовательности в двух последовательностях.
