Smit-Vatermanov algoritam

Smit-Vatermanov algoritam (енгл. Smith-Waterman) izvodi lokalno poravnavanje sekvenci; to jest, služi za određivanje sličnih oblasti između nizova nukleotida ili nizova proteina. Umesto pretrage totalnog niza, Smit-Vatermanov algoritam poredi segmente svih mogućih dužina i optimizuje sličnu meru.

Pozadina уреди

Algoritam je najpre predložen od strane Temple F. Smith-a i Michael S. Waterman-a 1981. godine. Kao i Needleman-Wunsch algoritam, čija je varijacija, i Smith-Waterman je algoritam dinamičkog programiranja. Kao takav, ima poželjnu osobinu koja garantuje pronalazak optimalnog lokalnog poravnanja u odnosu na sistem bodovanja koji se koristi (koji uključuje zamenu matrica i gap-scoring šemu). Glavna razlika u odnosu na Needleman-Wunsch algoritam je da se negativno označene ćelije matrice postavljaju na nulu, sto čini (kao i pozitivno označene) lokalno svrstavanje vidljivim. Povratak istim putem (bektreking) počinje na najvećoj označenoj ćeliji matrice i nastavlja se sve dok se ne naiđe na ćeliju sa vrednošću nula, prenoseći tako lokalno poravnanje najviše vrednosti. Zapravo, algoritam se ipak ne implementira na opisan način zato što poboljšane alternative imaju bolje skaliranje (Gotoh, 1982) i preciznije su (Altschul and Erickson, 1986).

Objašnjenje algoritma уреди

Matrica H se gradi na sledeći način:

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

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

${\text{ ako }}a_{i}=b_{j}$ onda se $w(a_{i},b_{j})=w{\text{(poklapa)}}$ ${\text{ ili }}a_{i}\neq b_{j}$ onda se $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$

Gde su:

$a,b$ = Nizovi kroz Alfabet $\Sigma$
$m={\text{duzina}}(a)$
$n={\text{duzina}}(b)$
$H(i,j)$ – je maksimalna vrednost sličnosti između sufiksa a[1...i] i sufiksa b[1...j]
$w(c,d),\;c,d\in \Sigma \cup \{'-'\}$ , '–' je gap-scoring šema

Primer уреди

Sekvenca 1 = ACACACTA
Sekvenca 2 = AGCACACA

w (poklapa) = +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}}$

Da bi dobili optimalno lokalno poravnanje, počinjemo sa najvećom vrednošću u matrici (i, j). Onda, idemo nazad na jednu od pozicija (i-1, j), (i, j-1), i (i-1, j-1) zavisno od pravca kretanja korišćenog za konstrukciju matrice. Ponavljamo proces dok ne dostignemo ćeliju matrice vrednosti nula, ili vrednost sa pozicije (0,0).

U primeru, najveća vrednost odgovara ćeliji pozicije (8,8). Kretanje nazad odgovara (8,8), (7,7), (7,6), (6,5), (5,4), (4,3), (3,2), (2,1), (1,1), i (0,0).

Jednom kad završimo, rekonstruišemo svrstavanje na sledeći način: počinjemo od poslednje vrednosti, dostižemo (i, j) koristeći prethodno izračunatu putanju. Dijagonalan skok podrazumeva da postoji svrstavanje (bilo da se poklapa ili ne). Skok odozgo na dole podrazumeva brisanje. Skok s desna na levo podrazumeva ubacivanje.

Na primer, dobijamo:

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

Motivacija уреди

Jedna od motivacija za lokalno svrstavanje je teškoća dobijanja korektnih poravnanja u oblastima male sličnosti između daleko povezanih bioloških serija, zato što su mutacije donele previše 'buke' tokom evolucije kako bi se omogućila smislena poređenja tih oblasti. Lokalno svrstavanje izbegava sve regione zajedno i fokusira se na one sa pozitivnim vrednostima, tj. one sa evolutivno zaštićenim znakom sličnosti. Preduslov negativne usklađenosti je očekivanje negativne vrednosti. Očekivana vrednost je definisana kao prosečna vrednost koju sistem vrednosti (zamena matrica i gap penali) doneti za nasumične nizove.

Druga motivacija za upotrebu lokalnog svrstavanja je ta da postoji pouzdan statistički model (razvijen od strane Karlin i Altschull-a) za optimalna lokalna svrstavanja. Poravnanje nepovezanih delova teži da proizvede optimalno svrstane lokalne vrednosti koje prate distribuciju ekstremnih vrednosti. Ovo svojstvo dozvoljava programu da proizvede očekivanu vrednost za optimalno lokalno svrstavanje dva dela, koje je mera toga koliko će često dva nepovezana dela proizvesti optimalno lokalno poravnanje čija je vrednost veća ili jednaka posmatranoj vrednosti. Veoma malo očekivane vrednosti pokazuju da dva dela iz postavke mogu biti odgovarajuća, što znači da oni moraju biti istog porekla.

Smit–Vatermanov algoritam je prilično zahtevnog vremena: da svrsta dva niza duzina m i n, potrebno vreme je O(m*n) klase složenosti. Smit–Vatermanove vrednosti lokalne sličnosti mogu biti izračunate u O(m) (linearne) prostorne složenosti samo ako optimlno svrstavanje mora biti pronađeno, ali naivni algoritmi da izvrše sortiranje zahtevaju O(m*n) prostornu složenost. BLAST i FASTA smanjuju prihod vremena potrebnog za identifikaciju određenih regiona koristeći strategiju brze pretrage, po cenu tačnosti.

Implementacija Smit-Vatermanovog algoritma, S-PRETRAGA, je dostupna samo u FASTA delu paketa analize. Ova implementacija uključuje Altivec ubrzani kod za PowerPC G4 i Generacije 5 procesora koji ubrzavaju poređenje 10-20 puta, koristeći modifikaciju Wozniak-a, 1997 pristup-a, i SSE2 vektorizaciju razvio Farrar praveći optimalnu bazu podataka proteina prilično praktične pretrage.

Ubrzane verzije уреди

FPGA уреди

Cray je demonstrirao ubrzanje Smit–Vaterman algoritma koristeći rekonfigurišuću platformu za računanje baziranu na FPGA čipovima, sa rezultatima koji su pokazali do 28 puta veću brzinu u odnosu na standardna, mikroprocesorski bazirana rešenja. Zasnovana na FPGA, verzija Smit–Vaterman algoritma pokazuje FPGA (Virtex-4) ubrzanje do 100 puta nad 2.2 GHz Opteron procesorom. TimeLogic DeCypher i CodeQuest sistemi takođe ubrzavaju Smit–Vaterman i Framesearch koristeći PCIe FPGA kartice.

Nedavno je objavljena teza u istraživanju, Genetičko svrstavanje delova na superračunarskoj platformi od strane odeljenja za Sistemsko Inžinjerstvo na Delft Univerzitetu pokazuje analizu ubrzanja FPGA-zasnovanog Smit–Vaterman algoritma.

GPU уреди

Lawrence Livermore Drzavna Laboratorija i Institut Joint Genome US Energetskog Sektora su implementirali ubrzanu verziju Smit–Vatermana svrstavanja lokalnih delova koristeći grafičke procesorske jedinice (GPUs) sa preliminarnim rezultatima koji su pokazivali dvostruko ubrzanje u odnosu na softverske implementacije. Sličan metod je već bio implementiran u Biofacet softveru još 1997. godine, sa istim faktorom ubrzanja.

Nekoliko GPU implementacija algoritma u NVIDIA CUDA C platformi su takođe dostupne. U poređenju sa najboljom poznatom računarskom implementacijom (koristi SIMD instrukcije na arhitekturi x86), od strane Farrar-a, testiranje rada ovog rešenja koristi jednu NVidia GeForce 8800 GTX karticu i pokazuje blago povećanje za manje delove, ali blago smanjenje za one koji su veći. Kako god, pokretanje istog testa na dvostrukim NVidia GeForce 8800 GTX karticama su skoro dvostruko brži od Farrar-ove implementacije sa testiranim svim dužinama sekvenci.

Novija GPU CUDA implementacija Smit–Vatermana je sada dostupna, i brža je od prethodnih verzija i takođe uklanja ograničenja zadata pitanjem dužine.

Jedanaest različitih implementacija Smit–Vatermana na CUDA su bile prijavljene, tri koje imaju ubrzanja od 30 puta.

SIMD уреди

2000. godine, brza implementacija Smit–Vaterman algoritma koja koristi SIMD tehnologiju dostupnu u Intel Pentium MMX procesorima i sličnu tehnologiju bila je opisana u objavi Rognes-a i Seeberg-a. Suprotno od pristupa Wozniak-a (1997), nova implementacija je zasnovana na paralelnim vektorima sa redosledom pitanja, ne dijagonalnih vektora. Kompanija Sencel Bioinformatics je podnela zahtev za proizvod koji pokriva ovaj pristup. Sencel razvija softver dublje i obezbeđuje izvršavanje za akademsku besplatnu upotrebu.

Danska bioinformatička kompanija "CLC bio" je dostigla ubrzanja čak približno 200 puta iznad standardne softverske implementacije SSE2 na Intel 2.17 GHz Core 2 Duo CPU, prema objavama dostupnim beloj štampi.

Ubrzana verzija Smit–Vaterman algoritma, na Intel i AMD zasnovanim Linux serverima, je podržana GenCore paketom, ponuđenim od strane Biocceleration. Ispitivanja performanse ovog softverskog paketa pokazuju 10 puta veću brzinu u odnosu na standardne implementacije softvera na istom procesoru.

Trenutno jedina kompanija u bioinformatici koja nudi oboje, i SSE i FPGA rešenja ubrzanog Smit–Vatermana, CLC bio je postignut ubrzanjima sa vise od 110 nad standardnim softverskim implementacijama kompanije CLC Bioinformatics Cube.

Najbrža implementacija algoritma na procesorima sa SSSE3 se može naći na SWIPE softveru (Rognes, 2011), koja je dostupna pod GNU Affero General Public Licence. Paralelno, ovaj softver upoređuje ostatke iz šesnaest različitih baza podataka na jednoj sekvenci upita ostatka. Koristeći sekvencu od 375 upita ostataka, brzina od 106 biliona ažuriranih ćelija po sekundi (GCUPS) je postignuta na dualnom Intel Xeon X5650 procesorskom sistemu sa šest jezgara, koji je šest puta brži nego softver baziran na Farrar-ovom 'prugastom' pristupu. Brži je od BLAST-a kada koristi BLOSUM50 matricu.

Ćelija širokopojasne mašine уреди

2008. godine, Farrar je opisao port Striped Smit–Vaterman na Ćeliji Sirokopojasnog Motora i prijavio brzine od 32 i 12 GCUPS na IBM QS20 blade i Sony PlayStation 3, respektivno.