Алгоритм Нидлмана-Вунша
Одним из наиболее распространенных алгоритмов выравнивания является алгоритм Нидлмана и Вунша ( Needleman & Wunsch, 1970 ) Суть алгоритма в следующем. По матрице расстояний между аминокислотами (или, соответственно, между нуклеотидами) итеративным образом рассчитывается матрица всех возможных маршрутов *Sij*: Sij=Dij+max(Si-1,j-1,max k<j-1 (Si-1,k - G),max k<i-1 (Sk,j-1-S)) где Sij - элемент i-й строки j-го столбца, Dij - расстояние между i-й и j-й аминокислотами (или нуклеотидами), а G - штраф на делецию. Затем осуществляется проход по матрице в обратном направлении, по максимальным элементам. Полученный маршрут соответствует оптимальному выравниванию. В качестве матрицы минимальных расстояний между аминокислотами обычно используется матрица минимальных мутационных расстояний по генетическому коду между аминокислотами, но могут использоваться и другие меры. В качестве примера приведем выравнивание двух нуклеотидных последовательностей. Исходя из следующей матрицы расстояний между нуклеотидами
A T G C
┌─────────┐
A│ 1 0 0 0 │
T│ 0 1 0 0 │
G│ 0 0 1 0 │
C│ 0 0 0 1 │
└─────────┘
и штрафа на делецию G = 0, по формуле (1) насчитываем матрицу возможных
маршрутов, и осуществляем обратный проход (маршрут обведен одинарной
линией):
╔════════════════════════════════╗
║ ┌───┐
║
A ║ 1 2 2 3 3 5 │ 6 │ 5 ║
║
┌───┼───┘ ║
A ║ 1 2 2 3 3 │ 5 │ 5 4 ║
║
┌───┼───┘
║ Выровненные
T ║ 0 1 3 3 │ 4 │ 3 3 3 ║
последовательности:
║
┌───┬───┴───┘
║
T ║ 0 1 │ 3 │ 2 3 2 2 2 ║
AATGTAAC
║
┌───┼───┘
║ AAT-TAA-
A ║ 1 │ 2 │ 1 1 1 2 2 1 ║
║┌───┼───┘
║
A ║│ 1 │ 1 0 0 0 1 1 0 ║
║└───┘
║
╚════════════════════════════════╝
A A T G T A A C
Для более подробного знакомства с алгоритмом смотрите книгу "Проблемы
теории молекулярной эволюции", Новосибирск: Наука, 1985, стр.84.
или
статью Нидлмана и Вунша.(Needleman & Wunsch,
1970
)
