На главную страницу
На главную страницу второго семестра

Глобальное и локальное выравнивание

Для построения наилучшего выравнивания можно перебрать все возможные выравнивания и выбрать из них выравнивание с наибольшим весом. Однако для реальных последовательностей (белков) это слишком долгий процесс. Поэтому используют косвенные методы. Здесь рассмотрены два алгоритма для построения глобального и локального выравнивания – алгоритмы Нидельмана - Вунша и Смита-Ватерманна соответственно.

Глобальное выравнивание

Суть алгоритма Нидельмана - Вунша: рисуют таблицу, в первых строке и столбце – две последовательности. Далее ячейки заполняют по реккурентной формуле:
P_i,j = max(P_i,j-1 + gap; P_i-1,j + gap; P_i-1,j-1 + S_a1,a2),
где P_i,j – значение ячейки "i,j",
gap – штраф за гэп (точнее, его модуль – он обычко отрицателен),
S_ai,aj – вес замены остатка a_i на остаток a_j.
Затем стрелками указывают ячейку, из которой был достигнут этот максимум. Полученный путь и есть лучшее выравнивание.
(подробнее – файл matrix.xls, полученный с помощью MsExcel).

При подсчете использованы значения:
за совпадение = 2
за несовпадение = -1
штраф за гэп = -2.

Полученное выравнивание:

	ME-TY
	KESTI

Вес этого выравнивания равен 0.

Локальное выравнивание

В алгоритме Смита-Ватерманна используется формула
P_i,j = max(P_i,j-1 + gap; P_i-1,j + gap; P_i-1,j-1 + S_a1,a2; 0),
то есть все значения неотрицательны. В остальном он схож с алгоритмом Нидельмана - Вунша. Расчет приведен в файле matrix.xls (лист Local).
Полученное локальное выравнивание:
E-T EST

Его вес равен 2.