Матрицы переходов глобального и локального выравнивания .

Глобальное выравнивание (алгоритм Нидельмана-Вунша)

Создана Excel-книга "matrix.xls"; в ней строю схему переходов глобального выравнивания для следующих 2-х последовательностей:

1. Первые 4-х остатка белка ASPG2_ECOLI.fasta (1);
2. Последовательность из 5 букв, полученная следующим образом: в последовательность первых 4-х остатков белка внесены две замены (F на M, F на W) и после 2ого «исходного» а.о. вставлена буква D – аспарагиновая кислота (2).

   Как считать:

   • Параметры для построения схемы переходов: вес совпадения (S) = 2, вес замены (С) = –1, штраф за гэп (g) = –2.
   • Верхний левый элемент матрицы равен 0, элементы строк p_1,j; p_i,1 равны, соответственно, (p_1,j-1+g); (p_i-1,1+g).
   • Остальные элементы - по формуле р _{i, j} = max {p_{i-1, j} + g; p_{i, j-1} + g; p _{i-1, j-1} + S(or C)}, i,j> 1.
   • Немаловажно сопутствующее расставление стрелок, соответствующих направлению перехода.Подсчет проводился вручную.

   Результат: вес выравнивания оказался равным 0. В принципе, это нетрудно объяснить (заменами «от балды», в первую очередь; в результате получилось, что аминокислоты сильно различаются по свойствам (дала знать о себе замена 2ух фенилаланинов на триптофан и метионин)…
   Получившееся оптимальное выравнивание:

   M  E  F  F  -        (1)
   M  E  D  M  W        (2)

   Наблюдения: выбор пути перехода не влияет на вес выравнивания (если, конечно, эти пути дают одинаковые числовые результаты). В соответствующем файле matrix.xls, лист global «путь» выравнивания выделен зеленым цветом. И приведены 2 матрицы, где пути различны.

   Впечатления: алгоритм Нидельмана – Вунша – очень удобная и интересная штука (и напоминает игру «Сапер»). Важно лишь соблюдать «правила игры», т.е. точно следовать параметрам для построения схемы перехода.

   Локальное выравнивание (алгоритм Смита-Ватермана)

   Полученная матрица представлена в файле matrix.xls, лист local.

   Как считать:

   • Параметры для построения схемы переходов: вес совпадения (S) = 2, вес замены (С) = –1, штраф за гэп (g) = –2.
   • Верхний левый элемент матрицы равен 0; элементы строк p_1,j; p_i,1 также берутся за 0.
   • Остальные элементы - по формуле р _{i, j} = max {p_{i-1, j} + g; p_{i, j-1} + g; p _{i-1, j-1} + S(or C); 0}, i,j> 1.
   • Немаловажно сопутствующее расставление стрелок, соответствующих направлению перехода.Подсчет проводился вручную.

   Результат: для каждой ячейки матрицы расчитано соответствующее значение. Локальному выравниванию соответствует выравнивание с максимальным весом. Таковым является следующее выравнивание с весом 4 (сверху указаны номера аминокислотных остатков):

   1  2  
   M  E       (1)
   M  E       (2)

   Наблюдения: локальных выравниваний можно получить несколько. Как пример - вариант 2 matrix.xls, лист local. Оптимальным, все-таки, считается то, чей вес больше. Неоспоримое преимущество: возможность получить больший вес, чем в глобальном выравнивании. Другой вопрос, насколько каждое из выравниваний (да еще и разные по длине) сохраняет "биологическую суть".

   Впечатления: крайне полезное упражнение. Наводит на всякого рода размышления. Последние (о принципах/плюсах-минусах и др. глобального и локального выравниваний) - в полном объеме представлены здесь.

   ---

   ©NADEZDA TUKHTUBAEVA,2006