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

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

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

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

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

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

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

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

де — значення в певній комірці, — очки за збіжність амінокислоти x та амінокислоти y в певних рядках, d — штаф пенальті (заданий).[2]

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

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

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

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

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


Сигма Це незавершена стаття з математики.
Ви можете допомогти проекту, виправивши або дописавши її.