Сравнение исходных текстов программ путем выравнивания…
3
тельно следующих в одинаковом порядке в обеих последовательно-
стях [5]. Отличительной особенностью такого алгоритма является
возможность обнаружения наиболее похожих подпоследователь-
ностей. При этом не исключаются случаи многократного вхождения
одной подпоследовательности в какую-нибудь из последовательно-
стей. К другим достоинствам данного алгоритма относится возмож-
ность найти похожие фрагменты последовательностей и получить вы-
равнивание за единственный проход по заполненной таблице, что
позволяет сократить время вычислений.
В биоинформатике выравнивание обычно предусматривает разры-
вы (делеции) более короткой последовательности в пределах консер-
вативных фрагментов, что обусловлено особенностями исследуемых
объектов. Например, делеция в выравнивании может быть результатом
мутации, не приводящей к существенным изменениям в структуре и
свойствах белка. В противоположность этому применительно к исход-
ному коду вставка или удаление токена из последовательности в ти-
пичном случае приводит к изменению смысла программы или к оши-
бочному коду. Поэтому мы сочли необходимым искать
непрерывные
непересекающиеся сходные подпоследовательности. Исходя из этой
необходимости, можно предложить следующую модификацию алго-
ритма.
Пусть
A
и
B
— последовательности длиной
m
и
n
символов соот-
ветственно. Тогда для выравнивания этих последовательностей потре-
буется таблица
T
размером
h
=
n
+ 1 строк на
w
=
m
+ 1 столбцов. Обо-
значим индекс столбца как
i
,
индекс строки как
j
и будем нумеровать
столбцы и строки таблицы, начиная с 0, а символы в последовательно-
стях, начиная с 1. Тогда значение в ячейке таблицы
T
(
i
,
j
) при
i
> 0 и
j
> 0 будет содержать оценку сходства для пары символов:
i
-го симво-
ла последовательности
A
и
j
-го символа последовательности
В
.
Заполнение таблицы
T
начинается с верхнего левого угла:
(0, 0) 0,
T
(1)
а дальнейшее заполнение осуществляется по столбцам слева направо,
т. е. при заполнении таблицы индекс столбца
i
принимает значения от
0 до
w
. Каждый столбец заполняется сверху вниз, т. е. при заполнении
столбца индекс строки
j
принимает значения от 0 до
h
. Правила запол-
нения таблицы могут быть выражены следующими формулами:
1,0 ;
, 0 max
1,
,
1, ;
T i
T i
T i
j t j
h
(2)
