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

{{Инфокутија Алгоритам|name=<!-- Defaults to article name -->|class=[[Порамнување на низи]]|image=|caption=|data=|time=<math>O(mn)</math>|best-time=|average-time=|space=<math>O(mn)</math>}}
[[Податотека:Smith-Waterman-Algorithm-Example-En.gif|рамка|Анимиран пример на Смит-Вотермановиот алгоритам кој ги прикажува чекорите при изведување на алгоритмот.|алт=]]
'''Смит–Вотермановиот алгоритам''' е алгоритам кој служи за локално [[порамнување на низи]], т.е., за утврдување на слични региони меѓу две [[Нуклеотидна низа|нуклеотидни]] или [[Првична структура на белковините|аминокиселински низи]]. Со овој метод не се врши споредување на целосната низа, туку се споредуваат сегменти со произволна должина и се [[Математичка оптимизација|оптимизира]] [[Коефициент на сличност|коефициентот на сличност]].

Алгоритмот бил предложен од страна на Темпл Ф. Смит и Мајкл С. Вотерман во 1981 година.<ref name="Smith1981">{{Наведено списание|last=Smith, Temple F.|last2=Waterman, Michael S.|last-author-amp=yes|year=1981|title=Identification of Common Molecular Subsequences|url=http://dornsife.usc.edu/assets/sites/516/docs/papers/msw_papers/msw-042.pdf|journal=[[Journal of Molecular Biology]]|volume=147|pages=195–197|doi=10.1016/0022-2836(81)90087-5|pmid=7265238}}</ref> Тој е варијација на [[Нидлман–Вуншов алгоритам|Нидлман–Вуншовиот алгоритам]] и како него претставува алгоритам на [[динамичко програмирање]]. Како таков, тој гарантира пронаоѓање на оптимално локално порамнување на низи со системот за бодување кој се користи (како што се матрицата на замена и системот за бодување на празнини). Главната разлика со [[Нидлман–Вуншов алгоритам|Нидлман–Вуншовиот алгоритам]] е што ќелиите со негативни бодови се заменуваат со вредност нула, што прави да позитивно бодуваните локални порамнувања станат видливи. Постапката на следење наназад кон потеклото започнува со ќелијата на матрицата која е највисоко бодувана и продолжува до ќелијата со бод нула, што го дава највисоко бодуваното локално порамнување. Поради својата квадратна комплексност во времето и просторот, овој алгоритам често не може практично да биде применет за поголеми проблеми, па е заменет со помалку општи, но пресметковно поефикасни алтернативи, како што се (Гото, 1982),<ref name="Gotoh1982">{{Наведено списание|last=Osamu Gotoh|year=1982|title=An improved algorithm for matching biological sequences|journal=[[Journal of Molecular Biology]]|volume=162|pages=705–708|doi=10.1016/0022-2836(82)90398-9}}</ref> (Алтшул и Ериксон, 1986),<ref name="Altschul1986">{{Наведено списание|last=Stephen F. Altschul|last2=Bruce W. Erickson|last-author-amp=yes|year=1986|title=Optimal sequence alignment using affine gap costs|journal=[[Bulletin of Mathematical Biology]]|volume=48|pages=603–616|doi=10.1007/BF02462326}}</ref> и (Маерс и Милер, 1988).<ref name="Myers1988">{{Наведено списание|last=Miller, Webb|last2=Myers, Eugene|year=1988|title=Optimal alignments in linear space|journal=[[Bioinformatics (journal)|Bioinformatics]]|volume=4|pages=11–17|doi=10.1093/bioinformatics/4.1.11}}</ref>

== Историја ==
Во 1970 година, Саул Б. Нидлман и Кристијан Д, Вунш, предложиле евристички хомолошки алгоритам за порамнување на низи, исто така познат како Нидлман–Вуншов алгоритам.<ref name="Needleman1970">{{Наведено списание|last=Saul B. Needleman|last2=Christian D. Wunsch|year=1970|title=A general method applicable to the search for similarities in the amino acid sequence of two proteins|journal=[[Journal of Molecular Biology]]|volume=48|pages=443–453|doi=10.1016/0022-2836(70)90057-4|pmid=5420325}}</ref> Станува збор за алгоритам за глобално порамнување на низи, за кого се потребни <math>O(mn)</math> пресметковни чекори (<math>m</math> и <math>n</math> се должините на двете низи кои треба да се порамнат). Алгоритмот користи итеративна пресметка на матрица за прикажување на глобално порамнување на низите. Во текот на наредната деценија, Санков,<ref name="Sankoff1972">{{Наведено списание|last=Sankoff D.|year=1972|title=Matching Sequences under Deletion/Insertion Constraints|journal=[[Proceedings of the National Academy of Sciences of the United States of America]]|volume=69|pages=4–6|doi=10.1073/pnas.69.1.4|pmc=427531|pmid=4500555}}</ref> Рајчерт,<ref name="Reichert1973">{{Наведено списание|last=Thomas A. Reichert|last2=Donald N. Cohen|last3=Andrew K.C. Wong|year=1973|title=An application of information theory to genetic mutations and the matching of polypeptide sequences|journal=[[Journal of Theoretical Biology]]|volume=42|pages=245–261|doi=10.1016/0022-5193(73)90088-X}}</ref> Бејер<ref name="Beyer1974">{{Наведено списание|last=William A. Beyer, Myron L. Stein, Temple F. Smith, and Stanislaw M. Ulam|year=1974|title=A molecular sequence metric and evolutionary trees|journal=[[Mathematical Biosciences]]|volume=19|pages=9–25|doi=10.1016/0025-5564(74)90028-5}}</ref> и другите формулирале алтернативни евристички алгоритми за анализа на генски низи. Селерс вовел систем за мерење на низна дистанца.<ref name="Sellers1974">{{Наведено списание|last=Peter H. Sellers|year=1974|title=On the Theory and Computation of Evolutionary Distances|journal=[[Journal of Applied Mathematics]]|volume=26|pages=787–793|doi=10.1137/0126070}}</ref> Во 1976 година, Вотерман et al. го додале концептот на празнини во оригиналниот мерен систем.<ref name="Waterman1976">{{Наведено списание|last=M.S Waterman|last2=T.F Smith|last3=W.A Beyer|year=1976|title=Some biological sequence metrics|journal=[[Advances in Mathematics]]|volume=20|pages=367–387|doi=10.1016/0001-8708(76)90202-4}}</ref> Во 1981 година, Смит и Вотерман го објавиле нивниот Смит–Вотерманов алгоритам за пресметување на локално порамнување на низи.

Смит–Вотермановиот алгоритам изискува прилично долго време: за да се порамнат две низи со должини <math>m</math> и <math>n</math>, потребно е <math>O(mn)</math> време. Гото<ref name="Gotoh1982"/> и Алтшул<ref name="Altschul1986"/> го оптимизирале алгоритмот на <math>O(mn)</math> чекори. Просторната сложеност била оптимизирана од страна на Маерс и Милер<ref name="Myers1988"/> од <math>O(mn)</math> на <math>O(n)</math> (линеарна), каде <math>n</math> е должината на пократката низа, за случајот кога е потребно само едно од многуте можни оптимални порамнувања.

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

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

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

== Алгоритам ==
[[Податотека:Smith-Waterman-Algorithm-Scoring-1.png|рамка|Метод на бодување кај Смит–Вотермановиот алгоритам|алт=]]
Нека <math>A=a_1a_2...a_n</math> и <math>B=b_1b_2...b_m</math> се низи кои треба да бидат порамнети, каде <math>n</math> и <math>m</math> се должините на <math>A</math> и <math>B</math>, соодветно.

# Одреди ги матрицата на замена и системот за бодување на празнини.
#* <math>s(a,b)</math> - бод на сличност на елементите кои ги сочинуваат двете низи
#* <math>W_k</math> - Казнен бод за празнина со должина <math>k</math>
# Конструирај матрица на бодување <math>H</math> и иницијализирај ги првиот ред и првата колона. Димензијата на матрицата за бодување е <math>(n+1) * (m+1)</math>. Индексирањето е засновано на нула.
#: <math>H_{k0}=H_{0l}=0 \quad for \quad 0\le k\le n \quad and \quad 0\le l\le m</math>
# Пополни ја матрицата на бодување со користење на следната формула:
#:<math>
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)
</math>
#: каде
#: <math>H_{i-1,j-1} + s(a_i,b_j)</math> е бодот на порамнување на <math>a_i</math> и <math>b_j</math>,
#: <math>H_{i-k,j} - W_k</math> е бодот ако <math>a_i</math> е крајот на празнина со должина <math>k</math>,
#: <math>H_{i,j-l} - W_l</math> е бодот ако <math>b_j</math> е крајот на празнина со должина <math>l</math>,
#: <math>0</math> значи дека нема сличност до <math>a_i</math> и <math>b_j</math>.
# Следење назад кон потеклото. Почни со највисокиот бод во матрицата за бодување <math>H</math> и следи сѐ до ќелија на матрицата со бод нула.

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

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

=== Споредба со Нидлман–Вуншовиот алгоритам ===
[[Податотека:Alignment-Comparison-En.png|мини|338x338px|Глобално и локално порамнување на низи|алт=]]
Разликата помеѓу Смит–Вотермановиот алгоритам и [[Нидлман–Вуншов алгоритам|Нидлман–Вуншовиот алгоритам]] е што првиот служи за пронаоѓање на оние сегменти во две дадени низи кои имаат сличности, додека вториот целосно ги порамнува двете низи. Сличностите се што и двата алгоритми ги користат концептите на матрица на замена, функција за казнени бодови за празнини, матрица на бодување и процест на следењо назад кон потеклото. Три главни разлики се:
{| class="wikitable"
!
!'''Смит–Вотерманов алгоритам'''
!'''Нидлман–Вуншов алгоритам'''
|-
|Иницијализација
|На првиот ред и на првата колона се дава вредност нула
|За првиот ред и првата колона се користат казнените бодови за празнина
|-
|Бодување
|На негативните бодови им се дава вредност нула
|Може да има негативни бодови
|-
|Следење назад кон потеклото
|Се започнува со највисокиот бод, се завршува кога се доаѓа до нула
|Се започнува со ќелијата во долниот десен агол на матрицата, а се завршува со горната лева ќелија
|}
Една од најважните разлики помеѓу двата алгоритма е што во системот на бодување кај Смит–Вотермановиот алгоритам не се даваат негативни бодови. Кога некој елемент има бод помал од нула, тоа значи дека низите до таа позиција немаат никаква сличност; затоа овој елемент се поставува на вредност нула, за да се елиминира влијанието од претходното порамнување. На овој начин, може да се продолжи со пронаоѓање на порамнување во било која позиција која следи потоа.

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

=== Матрица на замена ===
Секоја супституција на азотна база или аминокиселина добива одреден бод. Во принцип, совпаѓањата добиваат позитивни бодови, а несовпаѓањата добиваат релативно ниски бодови. На пример, за [[РНК]]-низите, ако совпаѓањата добиваат +1, несовпаѓањата добиваат -1, па тогаш матрицата на замена е:
{| class="wikitable" style="font-family: monospace"
!
!А
!G
!C
!Т
|- style="text-align: right;"
! scope="row" |А
|1
| -1
| -1
| -1
|- style="text-align: right;"
! scope="row" |G
| -1
|1
| -1
| -1
|- style="text-align: right;"
! scope="row" |C
| -1
| -1
|1
| -1
|- style="text-align: right;"
! scope="row" |Т
| -1
| -1
| -1
|1
|}
Оваа матрица на замена може да се опише како: <math>s(a_i,b_j) = \begin{cases}+1, \quad a_i=b_j \\ -1, \quad a_i\ne b_j\end{cases}</math>

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

=== Казнени бодови за празнина ===
Казнените бодови за празнина се однесуваат на бодовите за вметнувања и бришења. Едноставна стратегија за казнени бодови за празнини е да се користат фиксни бодови за секоја празнина. Во биологијата, сепак, бодовите треба да бидат различни од практични причини. Од една страна, делумната сличност помеѓу две низи е честа појава; од друга страна, една генска [[мутација]] може да резултира со вметнување на една долга празнина. Затоа, долгите празнини обично повеќе се фаворизирани од повеќе расфрлани, кратки празнини. За да се земе предвид оваа разлика, во системот на бодување додадени се концептите на отворање на празнина и екстензија (проширување) на празнина. Бодот за отворање на празнина е обично поголем од бодот за проширување на празнина. На пример, основните параметри во [http://www.ebi.ac.uk/Tools/psa/emboss_water/ EMBOSS Water] се: отворање на празнина = 10, проширување на празнина = 0.5.

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

==== Линеарна ====
[[Податотека:Smith-Waterman-Algorithm-Scoring-2.png|Поедноставен Смит–Вотерманов алгоритам, каде се користи линеарна функција за казнени бодови за празнина.|алт=|мини]]
Линеарната стратегија за казнени бодови за празнина ги има истите бодови за отворање и проширување на празнината:

<math>W_k=kW_1</math>,

каде <math>W_1</math> е цената за една празнина.

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

<math>
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}
</math>

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

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

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

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

Во оригиналниот Смит–Вотерманов алгоритам бил користен произволен систем за казнени бодови за празнина. Овој систем користи <math>O(m^2n)</math> чекори, поради што е прилично долготраен. Гото ги оптимизирал чекорите за афин систем за казнени бодови за празнина на <math>O(mn)</math>,<ref name="Gotoh1982"/> но оптимизираниот алгоритам е способен да пронајде само едно оптимално порамнување, кое не е загарантирано да се пронајде.<ref name="Altschul1986"/> Алтшул го има изменето алгоритмот на Гото за да можат да бидат пронајдени сите оптимални порамнувања.<ref name="Altschul1986" /> Подоцна, Маерс и Милер покажале дека алгоритмот на Гото и Алтшул може дополнително да биде изменет врз основа на методот објавен од страна на Хиршберг во 1975 година.<ref name="Myers1988"/><ref name="Hirschberg1975">{{Наведено списание|last=D. S. Hirschberg|year=1975|title=A linear space algorithm for computing maximal common subsequences|journal=[[Communications of the ACM]]|volume=18|pages=341–343|doi=10.1145/360825.360861}}</ref>  Алгоритмот на Маерс и Милер може да порамни две низи со употреба на <math>O(n)</math> простор, каде <math>n</math> е должината на пократката низа.

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

=== Матрица за бодување ===
Функцијата на матрицата за бодување е да спроведе споредба помеѓу сите компоненти во две низи и да ги евидентира оптималните резултати на порамнувањето. Процесот на бодување го одразува концептот на динамичко програмирање. Конечното оптимално порамнување се наоѓа преку итеративно проширување на растечкото оптимално порамнување. Со други зборови, моменталното оптимално порамнување се генерира со одлучување која патека (совпаѓање/несовпаѓање или внесување на празнина) го дава највисокиот бод од претходното оптимално порамнување. Големината на матрицата е должината на едната низа плус 1 по должината на другата низа плус 1. Дополнителниот прв ред и прва колона служат да се порамни едната низа со било која позиција во другата низа. И на првиот ред и на првата колона им се дава вредност нула, за крајната празнина да не добие казнени бодови. Почетната матрица за бодување е:
{| class="wikitable" style="font-family: monospace"
! scope="col" style="width:18px;" |
! scope="col" style="width:18px;" |
! scope="col" style="width:18px;" |b<sub>1</sub>
! scope="col" style="width:18px;" |…
! scope="col" style="width:18px;" |b<sub>j</sub>
! scope="col" style="width:18px;" |…
! scope="col" style="width:18px;" |b<sub>m</sub>
|-
! scope="row" style="height:18px;" |
|0
|0
|…
|0
|…
|0
|-
! scope="row" style="height:18px;" |a<sub>1</sub>
|0
|
|
|
|
|
|-
! scope="row" style="height:18px;" |…
|…
|
|
|
|
|
|-
! scope="row" style="height:18px;" |a<sub>i</sub>
|0
|
|
|
|
|
|-
! scope="row" style="height:18px;" |…
|…
|
|
|
|
|
|-
! scope="row" style="height:18px;" |a<sub>n</sub>
|0
|
|
|
|
|
|}

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

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

Се иницијализира и се пополнува матрицата на бодување како што е прикажано подолу. Сликата го прикажува процесот на бодување за трите првите елементи. Жолтата боја ги означува азотните бази кои се разгледуваат. Црвената боја го означува највисокиот можен бод за ќелијата која се бодува.
[[Податотека:Smith-Waterman-Algorithm-Example-Step1.png|н|Иницијализација на матрицата на бодување (лево 1) и процесот на бодување на првите три елементи (лево 2-4)|алт=|мини|950x950пкс]]
Крајната матрица на бодување е прикажана подолу налево. Сината боја го покажува највисокиот бод. Забележете дека еден елемент може да добие бод од повеќе од еден елемент, секој ќе формира поинаква патека ако овој елемент се следи наназад. Во случај на повеќе највисоки бодови, следењето наназад треба да се изврши почнувајќи од секој највисок бод. Процесот на следење наназад кон потеклото е прикажан подолу десно. Најдоброто локално порамнување се генерирана во обратна насока.
{| class="wikitable"
|[[Податотека:Smith-Waterman-Algorithm-Example-Step2.png|н]]
|[[Податотека:Smith-Waterman-Algorithm-Example-Step3.png|н]]
|-
|Завршена матрица на бодување (највисокиот бод е син)
|Процес на следење назад кон потеклото и резултат на порамнувањето
|}
Резултатот на порамнувањето на овие две низи е:
 <tt>G T T - A C</tt>
 <tt>| | |   | |</tt>
 <tt>G T T G A C</tt>

== Поврзано ==

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

== Наводи ==
<references group=""></references>

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

* [http://jaligner.sourceforge.net/ JAligner] &#x2014; Java имплементација на Смит–Вотермановиот алгоритам
* [http://baba.sourceforge.net/ Basic-Algorithms-of-Bioinformatics Applet] &#x2014; аплет кој визуелно го објаснува алгоритмот
* [http://www.ebi.ac.uk/Tools/fasta FASTA/SSEARCH] 
* [https://ugene.net/wiki/display/UUOUM15/Smith-Waterman+Search UGENE Smith-Waterman Search plugin] {{Семарх|url=https://web.archive.org/web/20161224094953/https://ugene.net/wiki/display/UUOUM15/Smith-Waterman+Search |date=2016-12-24 }} &#x2014; извор со отворен код SSEARCH компатибилна имплементација на алгоритмот со графички интерфејс, напишан во C++
* [https://github.com/Martinsos/opal Opal] &#x2014; SIMD C/C++ библиотека за масовно оптимално порамнување на низи
* [http://diagonalsw.sourceforge.net/ diagonalsw] &#x2014; C/C++ имплементација со отворен код со SIMD инструкциски сет (особено SSE4.1) под MIT лиценца
* [https://github.com/mengyao/Complete-Striped-Smith-Waterman-Library SSW] &#x2014; C++ библиотека со отворен код која обезбедување на API за SIMD имплементација на Смит–Вотермановиот алгоритам под MIT лиценца
* [https://melodic-sequence-alignment.firebaseapp.com/#/ мелодично порамнување на низи] &#x2014; javascript имплементација за мелодично порамнување на низи

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