🧬 Вирівнювач Послідовностей ДНК — Сміт-Уотерман Наживо

Сміт-Уотерман — це алгоритм динамічного програмування для пошуку оптимального локального вирівнювання між двома послідовностями. На відміну від алгоритму Нідлмана-Вунша, який вирівнює послідовності від кінця до кінця, Сміт-Уотерман дозволяє вирівнюванню починатися й закінчуватися будь-де, що робить його ідеальним для пошуку короткого відповідного регіону — наприклад, прочитання секвенування чи фрагмента гена — всередині довшої, у решті непов'язаної послідовності.

Кожна клітинка H(i,j) представляє найкращий бал локального вирівнювання, що закінчується на позиції i референсу й позиції j прочитання. Вона бере максимум із чотирьох варіантів: почати абсолютно нове вирівнювання тут (бал 0), продовжити діагональний збіг чи невідповідність від H(i-1,j-1), продовжити розрив у прочитанні від H(i-1,j), або продовжити розрив у референсі від H(i,j-1). Оскільки бали обмежені знизу нулем, будь-яка серія поганих збігів просто скидає локальне вирівнювання, а не тягне весь бал у мінус.

Бал збігу винагороджує вирівнювання ідентичних основ одна з одною; штраф невідповідності віднімається, коли дві різні основи змушені вирівнюватися; штраф розриву віднімається щоразу, коли алгоритм відкриває розрив (вставку чи делецію) у будь-якій послідовності. Підвищення штрафу розриву відносно штрафу невідповідності змушує вирівнювач надавати перевагу замінам над вставками/делеціями, і навпаки.

Реальні прочитання секвенування рідко вирівнюються край у край з референсом — вони зазвичай містять регіон інтересу, вбудований у послідовність адаптера, помилки секвенування чи сусідній геномний контекст. Доповнення мутованого ядра випадковою сміттєвою ДНК з обох боків демонструє ключову силу Сміта-Уотермана: він знаходить і оцінює лише найкращий відповідний локальний регіон, повністю ігноруючи непов'язані фланги.

Відсоток ідентичності — це частка стовпців у відстеженому локальному вирівнюванні, де основи референсу й прочитання ідентичні. Він обчислюється безпосередньо зі шляху відстеження, а не оцінюється, тож точно відображає те вирівнювання, яке алгоритм повідомляє як оптимальне для поточної схеми оцінювання.

Так. Рекурентне співвідношення оцінювання, правило обмеження нулем, вибір клітинки з максимальним балом і відстеження реалізовані точно як в оригінальній формулюванні Сміта й Уотермана (1981) з лінійним штрафом розриву. Вона опускає афінне оцінювання розриву (окрема вартість відкриття й продовження розриву) і матриці замін амінокислот, які реальні вирівнювачі на кшталт BLAST чи BWA додають поверх цієї самої основної рекурсії.