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

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

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

    Глобальное выравнивание двух коротких аминокислотных последовательностей (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

^© Куравский Михаил Львович, 2006