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

Смит-Ватерманов алгоритам (енгл. Smith-Waterman) изводи локално поравнавање секвенци; то јест, служи за одређивање сличних области између низова нуклеотида или низова протеина. Уместо претраге тоталног низа, Смит-Ватерманов алгоритам пореди сегменте свих могућих дужина и оптимизује сличну меру.

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

Алгоритам је најпре предложен од стране Темпле Ф. Смитх-а и Мицхаел С. Wатерман-а 1981. године. Као и Неедлеман-Wунсцх алгоритам, чија је варијација, и Смитх-Wатерман је алгоритам динамичког програмирања. Као такав, има пожељну особину која гарантује проналазак оптималног локалног поравнања у односу на систем бодовања који се користи (који укључује замену матрица и гап-сцоринг шему). Главна разлика у односу на Неедлеман-Wунсцх алгоритам је да се негативно означене ћелије матрице постављају на нулу, сто чини (као и позитивно означене) локално сврставање видљивим. Повратак истим путем (бектрекинг) почиње на највећој означеној ћелији матрице и наставља се све док се не наиђе на ћелију са вредношћу нула, преносећи тако локално поравнање највише вредности. Заправо, алгоритам се ипак не имплементира на описан начин зато што побољшане алтернативе имају боље скалирање (Готох, 1982) и прецизније су (Алтсцхул анд Ерицксон, 1986).

Објашњење алгоритма[уреди | уреди извор]

Матрица Х се гради на следећи начин:

$H(i,0)=0,\;0\leq i\leq m$

$H(0,j)=0,\;0\leq j\leq n$

${\text{ ako }}a_{i}=b_{j}$ онда се $w(a_{i},b_{j})=w{\text{(poklapa)}}$ ${\text{ ili }}a_{i}\neq b_{j}$ онда се $w(a_{i},b_{j})=w{\text{(ne poklapa)}}$

$H(i,j)=\max {\begin{Bmatrix}0\\H(i-1,j-1)+\ w(a_{i},b_{j})&{\text{Poklapa/Ne poklapa}}\\H(i-1,j)+\ w(a_{i},-)&{\text{Brisanje}}\\H(i,j-1)+\ w(-,b_{j})&{\text{Ubacivanje}}\end{Bmatrix}},\;1\leq i\leq m,1\leq j\leq n$

Где су:

$a,b$ = Низови кроз Алфабет $\Sigma$
$m={\text{duzina}}(a)$
$n={\text{duzina}}(b)$
$H(i,j)$ – је максимална вредност сличности између суфикса а[1...и] и суфикса б[1...ј]
$w(c,d),\;c,d\in \Sigma \cup \{'-'\}$ , '–' је гап-сцоринг шема

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

Секвенца 1 = АЦАЦАЦТА
Секвенца 2 = АГЦАЦАЦА

w (поклапа) = +2
$w(a,-)=w(-,b)=w({\text{ne poklapa}})=-1$

$H={\begin{pmatrix}&-&A&C&A&C&A&C&T&A\\-&0&0&0&0&0&0&0&0&0\\A&0&2&1&2&1&2&1&0&2\\G&0&1&1&1&1&1&1&0&1\\C&0&0&3&2&3&2&3&2&1\\A&0&2&2&5&4&5&4&3&4\\C&0&1&4&4&7&6&7&6&5\\A&0&2&3&6&6&9&8&7&8\\C&0&1&4&5&8&8&11&10&9\\A&0&2&3&6&7&10&10&10&12\end{pmatrix}}$

Да би добили оптимално локално поравнање, почињемо са највећом вредношћу у матрици (и, ј). Онда, идемо назад на једну од позиција (и-1, ј), (и, ј-1), и (и-1, ј-1) зависно од правца кретања коришћеног за конструкцију матрице. Понављамо процес док не достигнемо ћелију матрице вредности нула, или вредност са позиције (0,0).

У примеру, највећа вредност одговара ћелији позиције (8,8). Кретање назад одговара (8,8), (7,7), (7,6), (6,5), (5,4), (4,3), (3,2), (2,1), (1,1), и (0,0).

Једном кад завршимо, реконструишемо сврставање на следећи начин: почињемо од последње вредности, достижемо (и, ј) користећи претходно израчунату путању. Дијагоналан скок подразумева да постоји сврставање (било да се поклапа или не). Скок одозго на доле подразумева брисање. Скок с десна на лево подразумева убацивање.

На пример, добијамо:

Sekvenca 1 = A-CACACTA
Sekvenca 2 = AGCACAC-A

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

Једна од мотивација за локално сврставање је тешкоћа добијања коректних поравнања у областима мале сличности између далеко повезаних биолошких серија, зато што су мутације донеле превише 'буке' током еволуције како би се омогућила смислена поређења тих области. Локално сврставање избегава све регионе заједно и фокусира се на оне са позитивним вредностима, тј. оне са еволутивно заштићеним знаком сличности. Предуслов негативне усклађености је очекивање негативне вредности. Очекивана вредност је дефинисана као просечна вредност коју систем вредности (замена матрица и гап пенали) донети за насумичне низове.

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

Смит–Ватерманов алгоритам је прилично захтевног времена: да сврста два низа дузина м и н, потребно време је О(м*н) класе сложености. Смит–Ватерманове вредности локалне сличности могу бити израчунате у О(м) (линеарне) просторне сложености само ако оптимлно сврставање мора бити пронађено, али наивни алгоритми да изврше сортирање захтевају О(м*н) просторну сложеност. БЛАСТ и ФАСТА смањују приход времена потребног за идентификацију одређених региона користећи стратегију брзе претраге, по цену тачности.

Имплементација Смит-Ватермановог алгоритма, С-ПРЕТРАГА, је доступна само у ФАСТА делу пакета анализе. Ова имплементација укључује Алтивец убрзани код за ПоwерПЦ Г4 и Генерације 5 процесора који убрзавају поређење 10-20 пута, користећи модификацију Wозниак-а, 1997 приступ-а, и ССЕ2 векторизацију развио Фаррар правећи оптималну базу података протеина прилично практичне претраге.

Убрзане верзије[уреди | уреди извор]

ФПГА[уреди | уреди извор]

Цраy је демонстрирао убрзање Смит–Ватерман алгоритма користећи реконфигуришућу платформу за рачунање базирану на ФПГА чиповима, са резултатима који су показали до 28 пута већу брзину у односу на стандардна, микропроцесорски базирана решења. Заснована на ФПГА, верзија Смит–Ватерман алгоритма показује ФПГА (Виртеx-4) убрзање до 100 пута над 2.2 ГХз Оптерон процесором. ТимеЛогиц ДеЦyпхер и ЦодеQуест системи такође убрзавају Смит–Ватерман и Фрамесеарцх користећи ПЦИе ФПГА картице.

Недавно је објављена теза у истраживању, Генетичко сврставање делова на суперрачунарској платформи од стране одељења за Системско Инжињерство на Делфт Универзитету показује анализу убрзања ФПГА-заснованог Смит–Ватерман алгоритма.

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

Лаwренце Ливерморе Дрзавна Лабораторија и Институт Јоинт Геноме УС Енергетског Сектора су имплементирали убрзану верзију Смит–Ватермана сврставања локалних делова користећи графичке процесорске јединице (ГПУс) са прелиминарним резултатима који су показивали двоструко убрзање у односу на софтверске имплементације. Сличан метод је већ био имплементиран у Биофацет софтверу још 1997. године, са истим фактором убрзања.

Неколико ГПУ имплементација алгоритма у НВИДИА ЦУДА C платформи су такође доступне. У поређењу са најбољом познатом рачунарском имплементацијом (користи СИМД инструкције на архитектури x86), од стране Фаррар-а, тестирање рада овог решења користи једну НВидиа ГеФорце 8800 ГТX картицу и показује благо повећање за мање делове, али благо смањење за оне који су већи. Како год, покретање истог теста на двоструким НВидиа ГеФорце 8800 ГТX картицама су скоро двоструко бржи од Фаррар-ове имплементације са тестираним свим дужинама секвенци.

Новија ГПУ ЦУДА имплементација Смит–Ватермана је сада доступна, и бржа је од претходних верзија и такође уклања ограничења задата питањем дужине.

Једанаест различитих имплементација Смит–Ватермана на ЦУДА су биле пријављене, три које имају убрзања од 30 пута.

СИМД[уреди | уреди извор]

2000. године, брза имплементација Смит–Ватерман алгоритма која користи СИМД технологију доступну у Интел Пентиум MMX процесорима и сличну технологију била је описана у објави Рогнес-а и Сееберг-а. Супротно од приступа Wозниак-а (1997), нова имплементација је заснована на паралелним векторима са редоследом питања, не дијагоналних вектора. Компанија Сенцел Биоинформатицс је поднела захтев за производ који покрива овај приступ. Сенцел развија софтвер дубље и обезбеђује извршавање за академску бесплатну употребу.

Данска биоинформатичка компанија "ЦЛЦ био" је достигла убрзања чак приближно 200 пута изнад стандардне софтверске имплементације ССЕ2 на Интел 2.17 ГХз Цоре 2 Дуо ЦПУ, према објавама доступним белој штампи.

Убрзана верзија Смит–Ватерман алгоритма, на Интел и АМД заснованим Линуx серверима, је подржана ГенЦоре пакетом, понуђеним од стране Биоццелератион. Испитивања перформансе овог софтверског пакета показују 10 пута већу брзину у односу на стандардне имплементације софтвера на истом процесору.

Тренутно једина компанија у биоинформатици која нуди обоје, и ССЕ и ФПГА решења убрзаног Смит–Ватермана, ЦЛЦ био је постигнут убрзањима са висе од 110 над стандардним софтверским имплементацијама компаније ЦЛЦ Биоинформатицс Цубе.

Најбржа имплементација алгоритма на процесорима са СССЕ3 се може наћи на СWИПЕ софтверу (Рогнес, 2011), која је доступна под ГНУ Афферо Генерал Публиц Лиценце. Паралелно, овај софтвер упоређује остатке из шеснаест различитих база података на једној секвенци упита остатка. Користећи секвенцу од 375 упита остатака, брзина од 106 билиона ажурираних ћелија по секунди (ГЦУПС) је постигнута на дуалном Интел Xеон X5650 процесорском систему са шест језгара, који је шест пута бржи него софтвер базиран на Фаррар-овом 'пругастом' приступу. Бржи је од БЛАСТ-а када користи БЛОСУМ50 матрицу.

Ћелија широкопојасне машине[уреди | уреди извор]

2008. године, Фаррар је описао порт Стрипед Смит–Ватерман на Ћелији Сирокопојасног Мотора и пријавио брзине од 32 и 12 ГЦУПС на ИБМ QС20 бладе и Сонy ПлаyСтатион 3, респективно.

Види још[уреди | уреди извор]