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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

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

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]

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

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

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

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

Посилання[ред.ред. код]