Смит–Вотерманов алгоритам

рамка|Анимиран пример на Смит-Вотермановиот алгоритам кој ги прикажува чекорите при изведување на алгоритмот.|алт=
**Смит–Вотермановиот алгоритам** е алгоритам кој служи за локално порамнување на низи, т.е., за утврдување на слични региони меѓу две нуклеотидни или аминокиселински низи. Со овој метод не се врши споредување на целосната низа, туку се споредуваат сегменти со произволна должина и се оптимизира коефициентот на сличност.

Алгоритмот бил предложен од страна на Темпл Ф. Смит и Мајкл С. Вотерман во 1981 година. Тој е варијација на Нидлман–Вуншовиот алгоритам и како него претставува алгоритам на динамичко програмирање. Како таков, тој гарантира пронаоѓање на оптимално локално порамнување на низи со системот за бодување кој се користи (како што се матрицата на замена и системот за бодување на празнини). Главната разлика со Нидлман–Вуншовиот алгоритам е што ќелиите со негативни бодови се заменуваат со вредност нула, што прави да позитивно бодуваните локални порамнувања станат видливи. Постапката на следење наназад кон потеклото започнува со ќелијата на матрицата која е највисоко бодувана и продолжува до ќелијата со бод нула, што го дава највисоко бодуваното локално порамнување. Поради својата квадратна комплексност во времето и просторот, овој алгоритам често не може практично да биде применет за поголеми проблеми, па е заменет со помалку општи, но пресметковно поефикасни алтернативи, како што се (Гото, 1982), (Алтшул и Ериксон, 1986), и (Маерс и Милер, 1988).

## Историја
Во 1970 година, Саул Б. Нидлман и Кристијан Д, Вунш, предложиле евристички хомолошки алгоритам за порамнување на низи, исто така познат како Нидлман–Вуншов алгоритам. Станува збор за алгоритам за глобално порамнување на низи, за кого се потребни O(mn) пресметковни чекори (m и n се должините на двете низи кои треба да се порамнат). Алгоритмот користи итеративна пресметка на матрица за прикажување на глобално порамнување на низите. Во текот на наредната деценија, Санков, Рајчерт, Бејер и другите формулирале алтернативни евристички алгоритми за анализа на генски низи. Селерс вовел систем за мерење на низна дистанца. Во 1976 година, Вотерман et al. го додале концептот на празнини во оригиналниот мерен систем. Во 1981 година, Смит и Вотерман го објавиле нивниот Смит–Вотерманов алгоритам за пресметување на локално порамнување на низи.

Смит–Вотермановиот алгоритам изискува прилично долго време: за да се порамнат две низи со должини m и n, потребно е O(mn) време. Гото и Алтшул го оптимизирале алгоритмот на O(mn) чекори. Просторната сложеност била оптимизирана од страна на Маерс и Милер од O(mn) на O(n) (линеарна), каде n е должината на пократката низа, за случајот кога е потребно само едно од многуте можни оптимални порамнувања.

## Мотивација
Во текот на изминатите три децении, проектите за секвенционирање на геномите на различни организми создадоа огромна количина на податоци за генски и белковински низи, за кои е потребна пресметковна анализа. Порамнувањата на низите ги покажува односите помеѓу гените или белковините (белковините), што доведува до подобро разбирање на нивната хомологија и функционалност. Порамнувањето на низите исто така може да открие сочувани домени и сочувани низни мотиви.

Една мотивација за локално порамнување на низи е потешкотијата во добивањето на точни порамнувања во регионите со ниско ниво на сличност помеѓу далечно сродните биолошки низи, бидејќи мутациите во текот на еволуцијата имаат создадено премногу „шум“ за да може да се изврши споредба на овие региони. Локалното порамнување потполно ги избегнува таквите региони и се фокусира само на оние со позитивни бодови, односно оние со еволутивно сочуван сигнал за сличност. Предуслов за локалното порамнување е негативен очекуван бод. Очекуваниот бод е дефиниран како просечен бод кој системот за бодување (матрицата на замена и системот за бодување на празнини) ќе даде случајна низа.

Друга мотивација за користење на локалните порамнувања е што постои сигурен статистички модел (развиен од Карлин и Алтшул) за оптимални локални порамнувања. Порамнувањето на несродните низи има тенденција да создаде оптимални бодови за локално порамнување кои следат екстремна дистрибуција на вредности. Ова својство им овозможува на програмите да создадат очекувана вредност за оптимално локално порамнување на две низи, што е мерка за тоа колку често две несродни низи ќе создадат оптимално локално порамнување чиј бод е поголем или еднаков на набљудуваниот бод. Многу ниска очекувана вредност означува дека двете низи за кои станува збор може да бидат хомологни, што значи дека тие може да споделуваат заеднички предок.

## Алгоритам
рамка|Метод на бодување кај Смит–Вотермановиот алгоритам|алт=
Нека A=a_1a_2...a_n и B=b_1b_2...b_m се низи кои треба да бидат порамнети, каде n и m се должините на A и B, соодветно.

# Одреди ги матрицата на замена и системот за бодување на празнини.
#* s(a,b) - бод на сличност на елементите кои ги сочинуваат двете низи
#* W_k - Казнен бод за празнина со должина k
# Конструирај матрица на бодување H и иницијализирај ги првиот ред и првата колона. Димензијата на матрицата за бодување е (n+1) * (m+1). Индексирањето е засновано на нула.
#: H_{k0}=H_{0l}=0 \quad for \quad 0\le k\le n \quad and \quad 0\le l\le m
# Пополни ја матрицата на бодување со користење на следната формула:
#:
H_{ij} = \max\begin{cases} 
H_{i-1,j-1} + s(a_i,b_j), \\
\max_{k \ge 1} \{ H_{i-k,j} - W_k \}, \\
\max_{l \ge 1} \{ H_{i,j-l} - W_l \}, \\
0
\end{cases} \qquad (1\le i\le n, 1\le j\le m)

#: каде
#: H_{i-1,j-1} + s(a_i,b_j) е бодот на порамнување на a_i и b_j,
#: H_{i-k,j} - W_k е бодот ако a_i е крајот на празнина со должина k,
#: H_{i,j-l} - W_l е бодот ако b_j е крајот на празнина со должина l,
#: 0 значи дека нема сличност до a_i и b_j.
# Следење назад кон потеклото. Почни со највисокиот бод во матрицата за бодување H и следи сѐ до ќелија на матрицата со бод нула.

## Објаснување
Смит–Вотермановиот алгоритам порамнува две низи со совпаѓања/несовпаѓања (исто така познати како супституции), вметнувања и бришења. Вметнувањате и бришењате се операции кои означуваат празнини, кои се претставени со цртички. Смит–Вотермановиот алгоритам се состои од неколку чекори:

# **Одредување на матрицата на замена и системот за бодување на празнини**. Матрицата на замена доделува бод на секој пар на азотни бази или аминокиселини за совпаѓање или несовпаѓање. Обично совпаѓањата добиваат позитивни бодови, додека несовпаѓањата добиваат ниски бодови. Функцијата за казнени бодови за празнина ги одредува казнените бодови за отворање или екстензија на празнини.
# **Иницијализирање на матрицата на бодување**. Димензиите на матрицата на бодување се 1+должина во однос на секоја низа соодветно. Сите елементи на првиот ред и првата колона имаат вредност нула. Дополнителните прв ред и прва колона овозможуваат да се порамнат две низи во која било позиција, а давањето на вредност нула прави да терминалната празнина не добие казнени бодови.
# **Бодување**. Бодувањето се врши на секој елемент од лево надесно и од горе надолу во матрицата. Потоа се разгледуваат резултатите на супституции (дијагонални бодови) или празнини (хоризонтални и вертикални бодови). Доколку ниту еден од бодовите не е позитивен, елементот добива вредност нула. Потоа се забележува највисокиот бод и неговиот извор.
# **Следење назад кон потеклото**. Почнувајќи со елементот со највисокиот бод, следењето назад кон потеклото се врши од изворот на секој бод рекурзивно, додека не се дојде до бод со вредност нула. Оние сегменти кои имаат најголеми бодови за сличност, врз основа на дадениот систем за бодување, се добиваат во текот на овој процес. За да го добие второто најдобро локално порамнување, процесот на следењето назад кон потеклото почнува од вториот највисок бод.

### Споредба со Нидлман–Вуншовиот алгоритам
мини|338x338px|Глобално и локално порамнување на низи|алт=
Разликата помеѓу Смит–Вотермановиот алгоритам и Нидлман–Вуншовиот алгоритам е што првиот служи за пронаоѓање на оние сегменти во две дадени низи кои имаат сличности, додека вториот целосно ги порамнува двете низи. Сличностите се што и двата алгоритми ги користат концептите на матрица на замена, функција за казнени бодови за празнини, матрица на бодување и процест на следењо назад кон потеклото. Три главни разлики се:

Една од најважните разлики помеѓу двата алгоритма е што во системот на бодување кај Смит–Вотермановиот алгоритам не се даваат негативни бодови. Кога некој елемент има бод помал од нула, тоа значи дека низите до таа позиција немаат никаква сличност; затоа овој елемент се поставува на вредност нула, за да се елиминира влијанието од претходното порамнување. На овој начин, може да се продолжи со пронаоѓање на порамнување во било која позиција која следи потоа.

Првичната матрица на бодување на Смит–Вотермановиот алгоритам овозможува порамнување на кој било сегмент од едната низа со произволна позиција во другата низа. Кај Нидлман–Вуншовиот алгоритам треба да се земе предвид и казнениот бод за последната празнина за целосно да се порамнат низите.

### Матрица на замена
Секоја супституција на азотна база или аминокиселина добива одреден бод. Во принцип, совпаѓањата добиваат позитивни бодови, а несовпаѓањата добиваат релативно ниски бодови. На пример, за РНК-низите, ако совпаѓањата добиваат +1, несовпаѓањата добиваат -1, па тогаш матрицата на замена е:

Оваа матрица на замена може да се опише како: s(a_i,b_j) = \begin{cases}+1, \quad a_i=b_j \\ -1, \quad a_i\ne b_j\end{cases}

Различните супституции на азотни бази или аминокиселини може да имаат различни бодови. Матрицата на замена за аминокиселините обично е покомплицирана од онаа за азотните бази.

### Казнени бодови за празнина
Казнените бодови за празнина се однесуваат на бодовите за вметнувања и бришења. Едноставна стратегија за казнени бодови за празнини е да се користат фиксни бодови за секоја празнина. Во биологијата, сепак, бодовите треба да бидат различни од практични причини. Од една страна, делумната сличност помеѓу две низи е честа појава; од друга страна, една генска мутација може да резултира со вметнување на една долга празнина. Затоа, долгите празнини обично повеќе се фаворизирани од повеќе расфрлани, кратки празнини. За да се земе предвид оваа разлика, во системот на бодување додадени се концептите на отворање на празнина и екстензија (проширување) на празнина. Бодот за отворање на празнина е обично поголем од бодот за проширување на празнина. На пример, основните параметри во EMBOSS Water се: отворање на празнина = 10, проширување на празнина = 0.5.

Овде ќе стане збор за две чести стратегии за казнени бодови за празнина. Нека W_k биде функцијата за казнени бодови за празнина со должина k:

#### Линеарна
Поедноставен Смит–Вотерманов алгоритам, каде се користи линеарна функција за казнени бодови за празнина.|алт=|мини
Линеарната стратегија за казнени бодови за празнина ги има истите бодови за отворање и проширување на празнината:

W_k=kW_1,

каде W_1 е цената за една празнина.

Казнените бодови за празнина директно се пропорционални со должината на празнината. Кога се користи линеарната стратегија за казнени бодови за празнина, Смит–Вотермановиот алгоритам може да биде поедноставен во следната форма:


H_{ij}=\max\begin{cases}
H_{i-1,j-1}+s(a_i,b_j),\\
H_{i-1,j}-W_1,\\
H_{i,j-1}-W_1,\\
0
\end{cases}


Поедноставениот алгоритам користи O(mn) чекори. Кога некој елемент се бодува, треба да се земат предвид само казнените бодови од елементите кои се во негова непосредна близина.

#### Афина
Афината стратегија за казнени бодови за празнина одделно ги бодува отворањето на празнина и екстензијата на празнина:

W_k=uk+v \quad (u>0, v>0),

каде v е казната за отворање на празнина, а u е казната за екстензија на празнина. На пример, казната за празнина со должина 2 е 2u+v.

Во оригиналниот Смит–Вотерманов алгоритам бил користен произволен систем за казнени бодови за празнина. Овој систем користи O(m^2n) чекори, поради што е прилично долготраен. Гото ги оптимизирал чекорите за афин систем за казнени бодови за празнина на O(mn), но оптимизираниот алгоритам е способен да пронајде само едно оптимално порамнување, кое не е загарантирано да се пронајде. Алтшул го има изменето алгоритмот на Гото за да можат да бидат пронајдени сите оптимални порамнувања. Подоцна, Маерс и Милер покажале дека алгоритмот на Гото и Алтшул може дополнително да биде изменет врз основа на методот објавен од страна на Хиршберг во 1975 година.  Алгоритмот на Маерс и Милер може да порамни две низи со употреба на O(n) простор, каде n е должината на пократката низа.

#### Пример
Да го земеме како пример порамнувањето на ДНК-низите TACGGGCCCGCTAC и TAGCCCTATCGGTCA. Кога се користи линеарна функција за казнени бодови за празнина резултатот е (Порамнувањето е извршено од EMBOSS Water. Матрицата на замена е DNAfull. Казнените бодови за отворање и проширување на празнина се 1.0):
 TACGGGCCCGCTA-C
 ||   | || ||| |
 TA---G-CC-CTATC
Кога се користи афината функција за казнени бодови за празнина, резултатот е (Казнените бодови за отворање и проширување на празнина се 5.0 и 1.0, соодветно):
 TACGGGCCCGCTA
 ||   |||  |||
 TA---GCC—CTA
Овој пример покажува дека афината функција за казнени бодови за празнина може да помогне да се избегнат расфрлани мали празнини.

### Матрица за бодување
Функцијата на матрицата за бодување е да спроведе споредба помеѓу сите компоненти во две низи и да ги евидентира оптималните резултати на порамнувањето. Процесот на бодување го одразува концептот на динамичко програмирање. Конечното оптимално порамнување се наоѓа преку итеративно проширување на растечкото оптимално порамнување. Со други зборови, моменталното оптимално порамнување се генерира со одлучување која патека (совпаѓање/несовпаѓање или внесување на празнина) го дава највисокиот бод од претходното оптимално порамнување. Големината на матрицата е должината на едната низа плус 1 по должината на другата низа плус 1. Дополнителниот прв ред и прва колона служат да се порамни едната низа со било која позиција во другата низа. И на првиот ред и на првата колона им се дава вредност нула, за крајната празнина да не добие казнени бодови. Почетната матрица за бодување е:

## Пример
Да го земеме како пример порамнувањето на ДНК-низите TGTTACGG и GGTTGACTA. Со употреба на следниот систем:

* Матрица на замена: s(a_i,b_j) = \begin{cases}+3, \quad a_i=b_j \\ -3, \quad a_i\ne b_j\end{cases}
* Казнени бодови за празнина: W_k=2k (линеарна функција на казнени бодови за празнина од W_1 = 2)

Се иницијализира и се пополнува матрицата на бодување како што е прикажано подолу. Сликата го прикажува процесот на бодување за трите првите елементи. Жолтата боја ги означува азотните бази кои се разгледуваат. Црвената боја го означува највисокиот можен бод за ќелијата која се бодува.
н|Иницијализација на матрицата на бодување (лево 1) и процесот на бодување на првите три елементи (лево 2-4)|алт=|мини|950x950пкс
Крајната матрица на бодување е прикажана подолу налево. Сината боја го покажува највисокиот бод. Забележете дека еден елемент може да добие бод од повеќе од еден елемент, секој ќе формира поинаква патека ако овој елемент се следи наназад. Во случај на повеќе највисоки бодови, следењето наназад треба да се изврши почнувајќи од секој највисок бод. Процесот на следење наназад кон потеклото е прикажан подолу десно. Најдоброто локално порамнување се генерирана во обратна насока.

Резултатот на порамнувањето на овие две низи е:
 G T T - A C
 | | |   | |
 G T T G A C

## Поврзано

* Биоинформатика
* Порамнување на низи
* Нидлман-Вуншов алгоритам
* Левенштајново растојание
* BLAST
* FASTA

## Наводи


## Надворешни врски

* JAligner &#x2014; Java имплементација на Смит–Вотермановиот алгоритам
* Basic-Algorithms-of-Bioinformatics Applet &#x2014; аплет кој визуелно го објаснува алгоритмот
* FASTA/SSEARCH 
* UGENE Smith-Waterman Search plugin  &#x2014; извор со отворен код SSEARCH компатибилна имплементација на алгоритмот со графички интерфејс, напишан во C++
* Opal &#x2014; SIMD C/C++ библиотека за масовно оптимално порамнување на низи
* diagonalsw &#x2014; C/C++ имплементација со отворен код со SIMD инструкциски сет (особено SSE4.1) под MIT лиценца
* SSW &#x2014; C++ библиотека со отворен код која обезбедување на API за SIMD имплементација на Смит–Вотермановиот алгоритам под MIT лиценца
* мелодично порамнување на низи &#x2014; javascript имплементација за мелодично порамнување на низи

Категорија:Биоинформатика
Категорија:Биоинформатички алгоритми
Категорија:Динамичко програмирање