Back to the second term
Алгоритм Нидельмана-Вунша используется для построения глобального выравнивания двух белковых или нуклеотидных последовательностей.
Биоинформатикам он известен с 70-ых годов прошлого века, именно тогда, в 1970 году, он был предложен в совместной работе Саула
Нидельмана и Кристиана Вунша "A general method applicable to the search for similarities in the amino acid sequence of two proteins", J Mol Biol. 48(3):443-53 в качестве инструмета для выравнивания последовательностей.
Выравнивание производилось с помощью программы Excel по алгоритму Нидельмана-Вунша. Были взяты две короткие последовательности: MNEQ, VNKDQ - первая из которых представляет собой четыре первых аминокислотных остатка белка CAPP_ECOLI, вторая же является модифицированной первой посредством двух замен (метионин на валин, глутаминовая кислота на лизин) и одной вставки (аспарагиновая кислота между лизином и глутамином). Теперь несколько слов о самой сути алгоритма.
Цель постороения такой матрицы - выявить наиболее выгодное выравнивание с максимально высоким весом, проследить направление переходов выравнивания, то есть проще говоря, путь. С помощью такой матрицы можно составлять выравнивания без помощи таких программ, как GENDOC, в которых нет однозначной гарантии правильности построенного выравнивания, что обуславливает работу вручную, которой думаю, любому биоинформатику хотелось бы избежать.
Для этого мы должны составить матрицу, в которой первый верхний элемент мы берём равным нулю. Все остальные элементы являются аминокислотными остатками двух последовательностей - по горизонтали последовательность MNEQ, а по вертикали соответственно VNKDQ.
Поскольку мы используем матрицу, то будем оперировать соответствующими обозначениями: любой элемент матрицы обозначим через A i, j , где i, j - строка и столбец, в которых находится элемент A.
Таким образом, чтобы посчитать значения эелементов первых строки и столбца матрицы, мы берём формулы:где t принимает два значения: либо m, либо r, в зависимости совпадают ли аминокислотные остатки на пересечении i-ой строки и j-ого столбца или же составляют вместе замену, в первом случае t = m, во втором соответственно t = r.
NB: Применяя эту формулу, мы уже не рассматриваем первые строку и столбец, то есть i, j > 1.
Далее, посчитав все элементы матрицы, мы определяем направление перехода. Это сделать не составляет никакого труда. Осуществляется это так: если в вышеприведённой формуле (2) максимальным значением оказалось A i – 1, j + g, то в элемент A i, j мы переходим из A i – 1, j , если максимально A i, j – 1 + g, то из A i, j – 1 , если же A i – 1, j – 1 + t, то A i – 1, j – 1 .
Собственно прилагающийся ко всему вышесказанному документ с проделанной в Excel работой можно найти здесь.
Нужная матрица находится на листе global. Стрелками обозначено направление переходов, оранжевым цветом выделен путь нашего выравнивания.
| M | N | – | E | Q |
| V | N | K | D | Q |
| –1 | 2 | –2 | –1 | 2 |
Вес этого выравниания по итогам вычислений равен нулю. Стоит отметить такую важную вещь, как то, что вес такого выравнивания не зависит ни от специфики сделанных замен, ни от природы вставленной аминокислоты, ни даже от самих последовательностей, потому что если к примеру провести контрольное выравнивание с любыми другими комбинациями аминокислот, но с тем же количеством замен и вставок, а также с теми же значениями параметров совпадения, замены и штрафа за гэп, то получится в любом случае нуль, как бы мы ни старались получить что-либо иное, конечно, если мы сразу же лишим себя права на ошибку.
Этот похожий алгоритм появился позднее и предназначался, и предназначается до сих пор для построения также выравниваний, но уже локальных. Локальное выравнивание отличается от глобального принципиально тем только, что все несовпадающие участки с низкой гомологичностью опускаются и по сути локальное выравнивание представляет собой выборку наилучших частей глобального выравнивания. Чисто техническое, но не менее важное отличие двух выравниваний состоит в том, что в локальном вес получается как правило положительным, NB: и если мы проводим выравнивание двух близких родственных белков, то вес может получиться не только положительным, что и так понятно, но и неприлично огромным, поэтому вес локального выравнивания обычно пересчитывают в биты, домножая на коэффициент, который получают исходя из параметров соответствующей матрицы, в этом случае число остаётся положительным, но уже не так велико.
С помощью такого метода мы сразу видим места гомологии, но при этом полностью теряем общую картину, мы, к примеру, теперь не сможем судить о взаимном расположении этих "удавшихся кусков" последовательностей, конечно, мы можем сопоставлять номера аминокислотных остатков в уме, но никто, надеюсь, спорить не будет, что намного эффективней получить, так сказать, визуализированное взаиморасположение гомологий.
Алгоритм появился спустя 11 лет после Нидельмана-Вунша, в работе Тэмпла Смита и Михаэля Ватермана "Identification of Common Molecular Subsequences", Journal of Molecular Biology, 147:195-197, 1981.
Чтобы понять принцип действия алгоритма, стоит понять принцип вышеизложенного алгоритма. Мы берём за основу Нидельмана-Вунша и как только при построении мaтрицы мы встречаем на пути отрицательное значение веса для некой абстрактной ячейки, то мы сразу же ставим в ней нуль, то есть значение имеют только положительные веса. Направление в нулевых ячейках не ставится и обрывается при встрече с последними.Для чего вообще нам нужен такой алгоритм? Почему бы не удовлетвориться уже имеющимся алгоритмом Нидельмана-Вунша?!. Всё оттого, что далеко не все белки, а если говорить совсем точно, то подавляющее большиство белков не являются близкими в плане вторичной структуры и обладают маленьким числом сходных участков, поэтому строить глобальное выравнивание становится просто некорректным и ненаглядным, в то время как локальное позволяет максимально сфокусироваться на участках гомологии.
Чтобы продемонстрировать работу алгоритма, применим его к тем же двум последовательностям, что и в случае алгоритма Нидельмана-Вунша.
Итак, суть та же. Составляется матрица переходов. Первый верхний элемент матрицы берётся равный нулю.
где t принимает два значения: либо m, либо r, в зависимости совпадают ли аминокислотные остатки на пересечении i-ой строки и j-ого столбца или же составляют вместе замену, в первом случае t = m, во втором соответственно t = r; i и j по-прежнему больше единицы. Направление перехода мы определяем для ненулевых A i, j и делаем это аналогичным образом, как это описано выше.
На листе local той же Excel-книги находится заполненная матрица переходов для локального выравнивания тех же последовательностей (MNEQ, VNKDQ).
| N | E |
| N | K |
| 2 | –1 |
Вес равен единице. Нетрудно заметить, что вес локального выравнивания также не зависит только от количества замен и вставок и не меняется при неизменном количестве оных.
Полученная матрица, правда, даёт неоднозначный вариант выравнивания. Видно, что если мы поставим гэп в первой последовательности, то у нас будет ещё одно совпадение Q — Q и тогда наше выравнивание будет иным:
| N | E | – | Q |
| N | K | D | Q |
| 2 | –1 | –2 | 2 |
Видно, что вес не изменился, однако не факт, что при другом расположении заменси вставок вес не будет меняться, напротив..
Так что, как я понимаю, локальное выравнивание неоднозначно, может иметь несколько потенциальных вариантов, из которых мы скорей
всего выберем тот, что обладает большим весом.
© Анна Чебышева,2005