Алгоритм Нідлмана — Вунша

Алгоритм Нідлмана — Вунша (англ. Needleman–Wunsch algorithm) — один із алгоритмів вирівнювання послідовностей, який належить до динамічного програмування, та є глобальним вирівнюванням.

Складається цей алгоритм із трьох послідовних етапів:

1. Побудова ініціюючої матриці

Для цього дві порівнювані послідовності розташовують як верхній рядок і як нижні, тобто вони є заголовками матриці. Крім того перед кожною послідовністю виставляють пропуск. І заповнюють перший стовпчик і перший рядок. Заповнення відбувається за допомогою штафу за пенальті (так як найперше значення в рядку і стовпчику — це пропуск, отже, і перший рядок із стовпичок будуть заповнені від'ємними значеннями). [1] [Архівовано 13 серпня 2016 у Wayback Machine.]

2. Заповнення таблиці

Заповнення комірки відбувається за такою математичною формулою:

$F_{ij}=\max(F_{i}-1,j-1+S(A_{i},B_{j}),F_{i},j-1+d,F_{i}-1,j+d)$

де — $F_{ij}$ значення в певній комірці, — $S(A_{i},B_{j})$ очки за збіжність амінокислоти x та амінокислоти y в певних рядках, d — штаф пенальті (заданий).[2] [Архівовано 13 серпня 2016 у Wayback Machine.]

На основі цієї матриці будується матриця локалізації. Слідкують за тим, як відбувалося заповнення, тобто з якої комірки було отримано максимальне значення для наступної комірки. [3] [Архівовано 5 березня 2016 у Wayback Machine.]

3. Пошук максимального вирівнювання

Пошук починають із останньої кутової комірки, а завершують завжди найпершою коміркою. Вирівнювання відбувається таким чином: необхідно на основі матриці локалізації створити шлях, який ґрунтується на «вказівках» кожної комірки. Буква D — діагональ, тобто необхідно перейти на комірку, що розташована по діагоналі, T — вершина, треба перейти на 1 комірку вгору (біологічно це означає, що у горизонтальній послідовності була делеція, або у вертикальній — інсерція), L — вліво, треба перейти до комірки, розташованої праворуч (біологічний сенс обернений до попереднього). Якщо комірка має два значення, то можливі два напрямки руху, три — три.[4] [Архівовано 5 березня 2016 у Wayback Machine.]

Червона стрілка позначає вирівнювання, після якого послідовності розташовуються в два ряди разом із вирахуваними пропусками. Якщо є кілька маршрутів вирівнювання, то і вирівнювань буде стільки ж.

Посилання

• http://technology66.blogspot.com/2008/08/sequence-alignment-techniques.html [Архівовано 4 березня 2016 у Wayback Machine.]