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

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

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

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

Историја[уреди | уреди извор]

Во 1970 година, Саул Б. Нидлман и Кристијан Д, Вунш, предложиле хевристички хомолошки алгоритам за порамнување на секвенци, исто така познат како Нидлман–Вуншов алгоритам.[5] Станува збор за алгоритам за глобално порамнување на секвенци, за кого се потребни пресметковни чекори ( и се должините на двете секвенци кои треба да се порамнат). Алгоритмот користи итеративна пресметка на матрица за прикажување на глобално порамнување на секвенците. Во текот на наредната деценија, Санков,[6] Рајчерт,[7] Бејер[8] и другите формулирале алтернативни хевристички алгоритми за анализа на генски секвенци. Селерс вовел систем за мерење на секвенциска дистанца.[9] Во 1976 година, Вотерман et al. го додале концептот на празнини во оригиналниот мерен систем.[10] Во 1981 година, Смит и Вотерман го објавиле нивниот Смит–Вотерманов алгоритам за пресметување на локално порамнување на секвенци.

Смит–Вотермановиот алгоритам изискува прилично долго време: за да се порамнат две секвенци со должини и , потребно е време. Гото[2] и Алтшул[3] го оптимизирале алгоритмот на чекори. Просторната сложеност била оптимизирана од страна на Маерс и Милер[4] од на (линеарна), каде е должината на пократката секвенца, за случајот кога е потребно само едно од многуте можни оптимални порамнувања.

Мотивација[уреди | уреди извор]

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

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

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

Алгоритам[уреди | уреди извор]

Метод на бодување кај Смит–Вотермановиот алгоритам

Нека и се секвенци кои треба да бидат порамнети, каде и се должините на и , соодветно.

  1. Одреди ги матрицата на замена и системот за бодување на празнини.
    • - бод на сличност на елементите кои ги сочинуваат двете секвенци
    • - Казнен бод за празнина со должина
  2. Конструирај матрица на бодување и иницијализирај ги првиот ред и првата колона. Димензијата на матрицата за бодување е . Индексирањето е базирано на нула.
  3. Пополни ја матрицата на бодување со користење на следната формула:
    каде
    е бодот на порамнување на и ,
    е бодот ако е крајот на празнина со должина ,
    е бодот ако е крајот на празнина со должина ,
    значи дека нема сличност до и .
  4. Следење назад кон потеклото. Почни со највисокиот бод во матрицата за бодување и следи сѐ до ќелија на матрицата со бод нула.

Објаснување[уреди | уреди извор]

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

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

Споредба со Нидлман–Вуншовиот алгоритам[уреди | уреди извор]

Глобално и локално порамнување на секвенци

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

Смит–Вотерманов алгоритам Нидлман–Вуншов алгоритам
Иницијализација На првиот ред и на првата колона се дава вредност нула За првиот ред и првата колона се користат казнените бодови за празнина
Бодување На негативните бодови им се дава вредност нула Може да има негативни бодови
Следење назад кон потеклото Се започнува со највисокиот бод, се завршува кога се доаѓа до нула Се започнува со ќелијата во долниот десен агол на матрицата, а се завршува со горната лева ќелија

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

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

Матрица на замена[уреди | уреди извор]

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

А G C Т
А 1 -1 -1 -1
G -1 1 -1 -1
C -1 -1 1 -1
Т -1 -1 -1 1

Оваа матрица на замена може да се опише како:

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

Казнени бодови за празнина[уреди | уреди извор]

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

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

Линеарна[уреди | уреди извор]

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

Линеарната стратегија за казнени бодови за празнина ги има истите бодови за отворање и проширување на празнината:

,

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

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

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

Афина[уреди | уреди извор]

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

,

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

Во оригиналниот Смит–Вотерманов алгоритам бил користен произволен систем за казнени бодови за празнина. Овој систем користи чекори, поради што е прилично долготраен. Гото ги оптимизирал чекорите за афин систем за казнени бодови за празнина на ,[2] но оптимизираниот алгоритам е способен да пронајде само едно оптимално порамнување, кое не е загарантирано да се пронајде.[3] Алтшул го има модифицирано алгоритмот на Гото за да можат да бидат пронајдени сите оптимални порамнувања.[3] Подоцна, Маерс и Милер покажале дека алгоритмот на Гото и Алтшул може дополнително да биде модифициран врз основа на методот објавен од страна на Хиршберг во 1975 година.[11][4] Алгоритмот на Маерс и Милер може да порамни две секвенци со употреба на простор, каде е должината на пократката секвенца.

Пример[уреди | уреди извор]

Да го земеме како пример порамнувањето на ДНК секвенците TACGGGCCCGCTAC и TAGCCCTATCGGTCA. Кога се користи линеарна функција за казнени бодови за празнина резултатот е (Порамнувањето е извршено од EMBOSS Water. Матрицата на замена е DNAfull. Казнените бодови за отворање и проширување на празнина се 1.0):

TACGGGCCCGCTA-C
||   | || ||| |
TA---G-CC-CTATC

Кога се користи афината функција за казнени бодови за празнина, резултатот е (Казнените бодови за отворање и проширување на празнина се 5.0 и 1.0, соодветно):

TACGGGCCCGCTA
||   |||  |||
TA---GCC--CTA

Овој пример покажува дека афината функција за казнени бодови за празнина може да помогне да се избегнат расфрлани мали празнини.

Матрица за бодување[уреди | уреди извор]

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

b1 bj bm
0 0 0 0
a1 0
ai 0
an 0

Пример[уреди | уреди извор]

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

  • Матрица на замена:
  • Казнени бодови за празнина: (линеарна функција на казнени бодови за празнина од )

Се иницијализира и се пополнува матрицата на бодување како што е прикажано подолу. Сликата го прикажува процесот на бодување за трите првите елементи. Жолтата боја ги означува азотните бази кои се разгледуваат. Црвената боја го означува највисокиот можен бод за ќелијата која се бодува.

Иницијализација на матрицата на бодување (лево 1) и процесот на бодување на првите три елементи (лево 2-4)

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

Smith-Waterman-Algorithm-Example-Step2.png
Smith-Waterman-Algorithm-Example-Step3.png
Завршена матрица на бодување (највисокиот бод е син) Процес на следење назад кон потеклото и резултат на порамнувањето

Резултатот на порамнувањето на овие две секвенци е:

G T T - A C
| | |   | |
G T T G A C

Поврзано[уреди | уреди извор]

Наводи[уреди | уреди извор]

  1. Smith, Temple F.; Waterman, Michael S.. Identification of Common Molecular Subsequences. „Journal of Molecular Biology“ том  147: 195–197. doi:10.1016/0022-2836(81)90087-5. PMID 7265238. http://dornsife.usc.edu/assets/sites/516/docs/papers/msw_papers/msw-042.pdf. 
  2. 2,0 2,1 2,2 Osamu Gotoh. An improved algorithm for matching biological sequences. „Journal of Molecular Biology“ том  162: 705–708. doi:10.1016/0022-2836(82)90398-9. 
  3. 3,0 3,1 3,2 3,3 Stephen F. Altschul; Bruce W. Erickson. Optimal sequence alignment using affine gap costs. „Bulletin of Mathematical Biology“ том  48: 603–616. doi:10.1007/BF02462326. 
  4. 4,0 4,1 4,2 Miller, Webb; Myers, Eugene. Optimal alignments in linear space. „Bioinformatics“ том  4: 11–17. doi:10.1093/bioinformatics/4.1.11. 
  5. Saul B. Needleman; Christian D. Wunsch. A general method applicable to the search for similarities in the amino acid sequence of two proteins. „Journal of Molecular Biology“ том  48: 443–453. doi:10.1016/0022-2836(70)90057-4. PMID 5420325. 
  6. Sankoff D.. Matching Sequences under Deletion/Insertion Constraints. „Proceedings of the National Academy of Sciences of the United States of America“ том  69: 4–6. doi:10.1073/pnas.69.1.4. PMID 4500555. 
  7. Thomas A. Reichert; Donald N. Cohen; Andrew K.C. Wong. An application of information theory to genetic mutations and the matching of polypeptide sequences. „Journal of Theoretical Biology“ том  42: 245–261. doi:10.1016/0022-5193(73)90088-X. 
  8. William A. Beyer, Myron L. Stein, Temple F. Smith, and Stanislaw M. Ulam. A molecular sequence metric and evolutionary trees. „Mathematical Biosciences“ том  19: 9–25. doi:10.1016/0025-5564(74)90028-5. 
  9. Peter H. Sellers. On the Theory and Computation of Evolutionary Distances. „Journal of Applied Mathematics“ том  26: 787–793. doi:10.1137/0126070. 
  10. M.S Waterman; T.F Smith; W.A Beyer. Some biological sequence metrics. „Advances in Mathematics“ том  20: 367–387. doi:10.1016/0001-8708(76)90202-4. 
  11. D. S. Hirschberg. A linear space algorithm for computing maximal common subsequences. „Communications of the ACM“ том  18: 341–343. doi:10.1145/360825.360861. 

Надворешни врски[уреди | уреди извор]

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