Главная страница > Второй семестр > Матрицы переходов глобального и локального выравнивания

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

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

Глобальное выравнивание двух коротких аминокислотных последовательностей (MCGI и LTGIK) реализовано с помощью электронной таблицы Excel. Выравнивание осуществлялось по алгоритму Нидельмана-Вунша. Верхний левый элемент матрицы считался равным нулю, для вычисления значений прочих элементов верхней строки M_{1, j} и левого столбца M_{i, 1} использовались, соответственно, следующие формулы:
M_{1, j} = M_{1, j – 1} + g,
M_{i, 1} = M_{i – 1, 1} + g,
где g — число, прибавляемое к весу выравнивания за каждый из гэпов (g = –2).
Значение каждого из остальных элементов M_{i, j} i-й строки j-го столбца матрицы переходов вычислялось по формуле:
M_{i, j} = max {M_{i – 1, j} + g; M_{i, j – 1} + g; M_{i – 1, j – 1} + w}, i, j > 1,
где g = –2, w принимает различные значения в зависимости от того, совпадают ли соответствующие элементу M_{i, j} аминокислотные остатки последовательностей (в случае совпадения w = 2, в случае несовпадения w = –1).
Если M_{i, j} = M_{i – 1, j} + g, то переход в элемент M_{i, j} осуществляется из элемента M_{i – 1, j}; если M_{i, j} = M_{i, j – 1} + g — из элемента M_{i, j – 1} + g; если M_{i, j} = M_{i – 1, j – 1} + w — из элемента M_{i – 1, j – 1}.
Лист "global" книги matrix.xls включает в себя следующие таблицы: "Матрица переходов", "Направления переходов", "Веса замен аминокислотных остатков". Таблица "Веса замен аминокислотных остатков" предназначена для вычисления значений w для каждой пары амнокислотных остатков выравниваемых последовательностей. Таблица "Матрица переходов" позволяет найти числовые значения каждого из элементов матрицы по приведенным выше формулам, используя вычисленные значения w; таблица "Направления переходов" позволяет найти направления переходов (исходными данными служат элементы двух предыдущих таблиц). Для удобства направления переходов были перенесены в таблицу "Матрица переходов"; путь, соответствующий искомому выравниванию, обозначен красной стрелкой.
В результате проведеных вычислений было получено следующее глобальное выравнивание (вес выравнивания равен 0):
M C G I —
L T G I K

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

Для реализации локального выравнивания аминокислотных последовательностей MCGI и LTGIK использовался лист "local" книги matrix.xls, представляющий собой модифицированный вариант листа "global". Выравнивание осуществлялось по алгоритму Смита-Ватермана.
Значения элементов верхней строки и левого столбца матрицы переходов считались равными нулю. Значение каждого из остальных элементов M_{i, j} i-й строки j-го столбца матрицы переходов вычислялось по формуле:
M_{i, j} = max {M_{i – 1, j} + g; M_{i, j – 1} + g; M_{i – 1, j – 1} + w; 0}, i, j > 1,
где g = –2, w принимает различные значения в зависимости от того, совпадают ли соответствующие элементу M_{i, j} аминокислотные остатки последовательностей (в случае совпадения w = 2, в случае несовпадения w = –1).
Для каждого M_{i, j} > 0 направление перехода определялось следующим образом. Если M_{i, j} = M_{i – 1, j} + g, то переход в элемент M_{i, j} осуществляется из элемента M_{i – 1, j}; если M_{i, j} = M_{i, j – 1} + g — из элемента M_{i, j – 1} + g; если M_{i, j} = M_{i – 1, j – 1} + w и M_{i – 1, j – 1} > 0 — из элемента M_{i – 1, j – 1}.
Лист "local" включает в себя те же три таблицы, что и лист "global", которые были модифицированы для реализации алгоритма Смита-Ватермана. В качестве последней пары аминокислотных остатков локального выравнивания была выбрана пара I — I, которой соответствует наибольший из элементов матрицы переходов (его значение равно четырем). Путь, соответствующий выравниванию, показан красной стрелкой.
В результате проведеных вычислений было получено следующее локальное выравнивание (цифрами обозначены номера начального и конечного аминокислотных остатков, вес выравнивания равен 4):
3 G I 4
3 G I 4