Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kodomo.cmm.msu.ru/~mikhail88/term2/needle_water.html
Дата изменения: Tue Apr 4 16:36:02 2006
Дата индексирования: Tue Oct 2 14:14:45 2012
Кодировка: Windows-1251
Матрицы переходов

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

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


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

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