Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kodomo.cmm.msu.ru/~pavel_s/term2/task6.html
Дата изменения: Sun Feb 25 12:37:04 2007
Дата индексирования: Tue Oct 2 07:55:55 2012
Кодировка: Windows-1251
task6

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

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

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

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

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

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

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

	ME-TY
	KESTI

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

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

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

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

©Семенюк Павел