А.В. Дубанов
6
Оценка сходства
всех найденных непрерывных подпоследова-
тельностей может быть получена по формуле
max
max | , ,
1, ,
1, .
s
s T i j i
w j
h
(9)
Здесь поиск максимального значения осуществляется среди индексов
символов последовательностей
A
и
B
. Максимальное значение соот-
ветствует нижнему правому концу крайней правой диагонали.
Пример заполнения таблицы
T
для строк ABCxDEFGx и
DEFGoABCo (жирным шрифтом показаны ячейки, образующие диа-
гонали, и соответствующие этим диагоналям похожие (в данном слу-
чае идентичные) подпоследовательности в последовательностях; гори-
зонтальными и вертикальными стрелками показан поиск нижних
правых концов диагоналей, диагональными стрелками — поиск ячеек,
образующих диагональ):
Алгоритм находит соответствие между одинаковыми символами,
подпоследовательностями ABC и подпоследовательностями DEFG в
сравниваемых последовательностях.
В биоинформатике при выравнивании нуклеотидных последова-
тельностей, алфавиты которых включают в себя только четыре симво-
ла, обозначающих нуклеотиды,
( , )
i
j
s a b
принимают равным 1 для сов-
падающих символов и −1 для несовпадающих, штраф за делецию
устанавливается равным 2. При выравнивании аминокислотных по-
следовательностей белков, алфавит которых составляют 20 символов
стандартных аминокислотных остатков, причем замены одних на дру-
