Варианты реализации штрафующей функции за пропуски в выравнивании

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

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

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

Приведем пример измененной оценочной функции:

где k ¹ — результат выбора k в предыдущей вершине; g_open и g_ext — штрафы за открытие нового и удлинения уже открытого пропуска. Отметим, что поскольку введение аффинных штрафов за пропуски увеличивает сложность каждого шага алгоритма на константное число операций (посмотреть тип предыдущего шага и сделать выбор в оценочной функции), то оценка вычислительной сложности алгоритма не изменится (О (и²)). Таким образом, реализация аффинных пропусков лишь немного увеличивает вычислительные затраты, но при этом существенно повышает биологическую адекватность модели.

Более сложным случаем является применение штрафов, нелинейно зависящих от длины пропуска. В этом варианте реализации штрафов на каждом шаге алгоритма мы должны пробовать делать пропуски начиная от единичного и до конца одной из последовательностей (рис. 2.10). При этом оценочная функция будет выглядеть следующим образом (в случае глобальных выравниваний вариант к = 4, как обычно, не рассматривается):

где я и, А на каждом этапе «пробегают» от 0 до текущего значения j или / соответственно, а вычислительная сложность алгоритма в результате оценивается как О (я³).

Рис. 2.10. Иллюстрация действий алгоритма в случае применения штрафов за пропуски, нелинейно зависящих от длины пропуска, на каждом шаге выравнивания.