BLAST

U bioinformatici, **BLAST** (eng. **B**asic **L**ocal **A**lignment **S**earch **T**ool) je algoritam za poređenje primarnih bioloških sekvenci, kao što su aminokiseline raznih proteina ili nukleotid, a u molekulama DNK. Pretraživač BLAST pomogućava spoređenje mnoštva sekvenci sa bibliotekama ili bazama podataka o sekvencama i identificiraju sekvencu koja odgovara traženoj, sa određenom greškom.

BLAST-u  je *The New York Times* nazivao *Googleom bioloških istraživanja* i jedan je od najčešće korištenih bioinformatičkih programa za pretraživanje sekvenci.

Danas su dostupni raazličiti tipovi BLAST-a, u zavisnosti od tipa pretraživane sekvence. Naprimjer, nakon otkrića prethodno nepoznatog gena kod miševa, obično se uključuje BLAST pretraga ljudskih genoma u provjeri da li dati ljudi sadrže slične gene, BLAST prepoznaje sekvence u genomu koje liče mišjem, zasnovanom na sličnosti sekvenci. BLAST-ov algoritam i program dizajnirali su i  Stephen Altschul, Warren Gish, Webb Miller, Eugene Myers, i David J. Lipman u Nacionalnom institutu za zdravlje Sjedinjenih Država  i objavili u *Journal of Molecular Biology*, 1990.

## Okviri
BLAST je jedan od najčešće koršćenih programa u bioinformatici za pretragu sekvenci. Predstavlja temelj za rješavanje problem u bioinformatici. Korišteni Heuristički algoritam je  mnogo brži nego drugi pristupi, kao što je računanje optimalnog poravnanja. Naglasak na brzini je ključan aspekat algoritma, posebno na velikim sada dostupnim bazama genoma, iako noviji algoritmi mogu biti još brži.
Za slične potrebe, prije BLAST-a, David J. Lipman i William R. Pearson kreirali su FASTA, 1985.
Prije brzih algoritama, kao što su BLAST i FASTA, pretraživbanja proteina i nukleinskih sekvenci bila je vremenski veoma zahtijevna jer je korišten potpuni postupak poravananja (npr., Smit-Vatermanov algoritam).

Iako je BLAST brži od svih Smith-Watermanovih implementacija za većinu slučajeva, ipak ne može "garantirati optimalno poravnavanje upita sa bazom sekvenci" kao Smith-Watermanov.  Optimalnost S–W algoritma "obezjbeđuje najveću tačnost i najpreciznije rezultate", po cijenu vremena i resursa računara.

BLAST je vremenski efikasniji od FASTA jer budući da pretražuje samo značajnije uzorake u sekvenci, ali sa potrebnom osetljivošću.

Primjeri upotrebe BLAST-a, između ostalih, je traženje odgovora na upite:
* Koje vrste bakterija imaju protein koji je u vezi sa određenim proteinom sa poznatom aminokiselinom?
* Koji još geni predstavljaju proteine koji imaju strukturu sličnu onima koji su već otkriveni?
BLAST je često korišćen kao komponenta drugih algoritama koji zahtijevaju približno poklapanje sekvenci.

### Ulaz 
Ulaz predstavljaju sekvence (u FASTA formatu ili Genbank formatu) i težinsku matricu.

### Izlaz 
Izlaz BLAST algoritma može biti predstavljen na različite načine. Korišteni formati mogu biti HTML, tekst i XML. Za web stranicu NCBI, podrazumijevani format izlaza je HTML. Kada se BLAST algoritam realizira na NCBI sajtu, rezultati se dobiju u grafičkom obliku i prikazuju pogotke, a tabele p identifikatore sekvenci za pogotke, zajedno sa pratećim podacima, kao i poravnanje sekvenci od interesa. Uključuje i pogotke dobijene korišćenjem odgovarajućeg vrijednosnog sistema BLAST. su Tabele su i najjednostavnije i najinformativnije za čitanje.

Ako se traži sekvenca koje nema u javno dostupnim bazama putem izvora, kao što je NCBI sajt, BLAST-ov algoritam je moguće besplatno preuzeti sa interneta. Može se preuzeti sa NCBI sajta. Dostupni su i komercijalni programi, a baze se mogu naći na NCBI sajtu, kao i na indeksu BLAST baza podataka.

## Proces 
Korištenjem heurističkih metoda, BLAST nalazi slične sekvence, lociranjem kratkih poklapanja između poređenih  sekvenci. Ovaj proces pronalaženja naziva se sijanje (eng. *seeding*). Nakon prvog poklapanja, BLAST počinje praviti lokalna poravnavanja. Dok pokušava naći sličnost u sekvenci, veoma je važan skup čestih slova, poznat kao riječ. Naprimjer, ako  sekvenca sadrži niz slova: GLKFA. Ako se BLAST pokrene pod normalnim uvjetima, riječ  bi bila duga tri slova. U ovom slučaju, korištenjem datog niza slova, dobijene riječi bi bile GLK, LKF, KFA. BLAST-ov heuristički algoritam locira sve česte pojave troslovnih riječi između zadate i pronađene sekvence. Ovaj rezultat se zatim koristi za kreiranje poravnavanja. Nakon što je napravio moguće  riječi za posmatranu sekvencu, također su obrađene i ostale. Te riječi, u poređenju sa matricom vrijednosti, moraju imati zadovoljen prag *T*. Često korištena matrica vreijdnosti za BLAST pretraživanja je BLOSUM62, iako optimalna matrica vrijednosti ovisi od sličnosti sekvenci. Kada su riječi, kao i okolne , procesuirane, porede se sa sekvencama iz baze u cilju pronalaska poklapanja. O tome da li konkretna riječ ulazi u poravnanje određuje Prag *T*. Kada se obavi  sijanje , poravnanje dužine 3, prošireno je u oba smjera pomoću BLAST algoritma. Svako proširenje utiče na rezultat poravnanja, bilo povećanjem bilo smanjenjem. Ako je rezultat veći od unaprijed određenog *T*, poravnanje će biti uključeno u rezultat BLAST-a. Međutim, ako je rezultat manji od  predodređenog *T*, poravnanje će prestati da se širi, sprečavajući da se segmenti sa lošim poravnanjem uključe u rezultat BLAST-a. Treba uočiti da dse povećanjem *T* ograničava prostor koji se može pretraživati i smanjujej broj susednih riječi, dok se  istovremeno ubrzava BLAST.

## Algoritam 
Za pokretanje programa, BLAST zahtijeva unos sekvence za pretragu i sekvence sa kojom će upoređivati (također znava i “ciljana sekvenca”) ili baze koja sadrži više sekvenci. BLAST će naći više podsekvenci u bazi koje su slične podsekvenci upita. Obično, upitna sekvenca je dosta manja od baze, naprimjer, upit može sadržati hiljadu nukleotida, dok baza ih sadrži nekoliko milijardi.

Glavna ideja BLAST-a je da često postoji visoko rangirani segmentni parovi (**H**igh-scoring **S**egment **P**airs – HSP) sadržani u statistički bitnom poravnanju. BLAST traži visoko rangirana poravnanja između upitne i posmatrane sekvence iz baze, koristeći heuristički pristup, koji aproksimira Smith-Waterman algoritam. Međutim, iscrpni Smith-Watermanov pristup suviše je spor za pretraživanje velikih baza genoma, kao što je GenBank. Zato se BLAST algoritam koristi heuristički i manje je precizan od Smith-Watermanovog algoritma, ali preko 50 puta brži. Brzina i relativno dobra preciznost BLAST-a su među ključnim tehničkim inovacijama BLAST programa.
Pregled BLAST algoritma (protein-protein pretraga): and CTGA2016
# **Brisanje nekompleksnih regija ili ponavljajućih sekvenci iz upita.**
#:**Nekompleksirana regija** predstavlja područje sekvenci koje je sastavljeno od nekoliko tipova elemenata. Ove regije mogu onemogućiti program da nađe bitnu sekvencu u bazi, pa bi ih trebalo isfiltrirati. Te regije se obilježe sa X (proteinske sekvence) ili N (nukleinske kiseline) i biće ignorirane u programu  BLAST-a. Za filtriranje nekompleksnih regija proteinskih sekvenci koristi se program SEG, a za DNK sekvence program DUST.
# '*Pravljenje *k*-slovne liste reči  upitne sekvence.*'
#: Ako se uzme *k*=3 kao primjer, izlistavaju se  riječi dužine 3 iz upitne proteinske sekvence (*k* je obično 11 za sekvencuDNK ) "sekvencino", dok ne budu uključena sva slova upitne sekvence. Metod je prikazan na slici  ispod.

# **Lista mogućih riječi koje se poklapaju.**
#: Ovaj korak je jedna od glavnih razlika između BLAST-a i FASTA-a. FASTA koristi sve česte riječi nađene u koraku 2; ali BLAST  jedino uzima visokovrednovane riječi. Vrijednosti su kreirane upoređivanjem riječi dobijenih u koraku 2 sa svim preostalim. Korištenjem matrice vrijednosti i poređenjem svih parova, postoji 203 mogućih komcinacija za troslovne riječi. Naprimjer, vrijednost koja se dobije poređenjem PQG sa PEG i PQA je 15 i 12, redom. Za riječi u DNK, pogodak se računa kao +5, a promašaj kao –4, ili kao +2 i –3. Nakon toga, vrijednost praga susjednih riječi *T* koristi se da smanji broj mogućih riječi koje se poklapaju. One riječi čije su vrijednosti veće od praga *T* ostat će na listi tih riječi, dok će one čija je vrijednost manja od ovog praga biti odbačene. Naprimjer, kada je T = 13, PEG se čuva, ali PQA je odbačen.
# **Organizacija visokorangiranih riječi u efikasno stablo pretrage.**
#: Ovo omogućava programu da brzo poredi visoko rangirane reči sa onima iz baze.
# '*Ponavljanje koraka 3 – 4 za svaku *k*-slovnu riječ iz upitne sekvence.**
# **Pretraga baze za pronalaženja egzaktnog poklapanja sa preostalim visokorangiranim riječima.**
#: BLAST program pretražuje bazu po preostalim visokorangiranim riječima, kao što je PEG, po svakoj poziciji. Ako se pronađe egzaktno poklapanje,  koristi se za sijanje mogućih poravnanja bez odstupanja između upitne sekvence i sekvence iz baze.
# **Proširivanje egzaktnog poklapanja u visoko rangirani segmentni par (HSP).**
#* Originalna verzija BLAST-a pravi dugo poravnanje između upita i sekvenci iz baze u oba smjera od pozicije gde je pronađeno egzaktno poklapanje. Proširenje ne prestaje sve dok nagomilana vrijednost HSP-a ne počne opadati. 
#* Radi uštede vremena, razvijena je novija verzija BLAST-a, zvana BLAST2. BLAST2 prisvaja nižerangirane susjedne riječi da bi očuvao isti nivo osetljivosti za otkrivanje sličnih sekvenci. Zato lista mogućih poklapanja iz koraka 3 postaje duža. Nadalje, regije kod kojih je došlo do egzaktnog poklapanja, na međusobnom rastojanju A na istoj dijagonali na gornjoj slici, biće spojeni u jednu dugu novu regiju. Konačno, nove regije su proširene na isti način kao u originalnoj verziji BLAST-a.
# **Lista svih HSP u bazi čija je vrijednost dovoljno velika da se uzmu u obzir.**
#: Zatim  se listaju vrijednosti HSP-a koje su veće od empirijski utvrđenih granica vrednosti S. Proučavanjem distribucije vrijednosti poravnanja, dobijenih poređenjem slučajnih sekvenci, granična vrijednost S može biti utvrđena tako da njena vrijednost bude dovoljno velika da garantira značajan ostatak HSP-a.
# **Procjena značajnosti vrijednosti HSP-a *'
#: BLAST dalje pristupa statističkom vrednovanju svake HSP vrijednosti, korišćenjem Gumbelove distribucije ekstremnih vrijednosti (EVD). U poređenju sa Gumbel EVD, verovatnoća *p* za dostizanje *S*, koja je veća ili jednaka od x, data je sledećom jednačinom:
:: p\left( S\ge x \right)=1-\exp \left( -e^{-\lambda \left( x-\mu  \right)} \right)
: gdje je
:: \mu ={}^{\left[ \log \left( Km'n' \right) \right]}\!\!\diagup\!\!{}_{\lambda }\;
#: Statistički parametri\lambda i \mathrm{K} procjenjuju se na osnovu vriednosti poravnanja bez rupa. Tako da \lambda i \mathrm{K} zavise od matrice zamjene i kompozicije sekvence. m' i n' su efektivne dužine unosa i sekvence iz baze, redom. Dužina sekvence je skraćena na efektivnu dužinu, da bi kompenzirala rubni efekt. Mogu se izračunati kao:
:: m'\approx m-{}^{\left( \ln Kmn \right)}\!\!\diagup\!\!{}_{H}\;
:: n'\approx n-{}^{\left( \ln Kmn \right)}\!\!\diagup\!\!{}_{H}\;
: gdje je \mathrm{H} očekivana srednja vrijednost po poravnatom paru u poravnanju dvije slučajne sekvence. Altschul i Gish dali su uobičajene vrednosti, \lambda = 0,318,  \mathrm{K} = 0,13, i \mathrm{H} = 0,40, za lokalno poravnanje bez rupa, korišćenjem BLOSUM62 kao zamjenske matrice. Korištenje tipskih vrijednosti za procjenu značajnosti se zove metod table sa pogledom nagore, koji  nije precizan. Očekivana vrijednost *E* je broj koliko puta nepovezana sekvenca iz baze , po zakonu vjerovatnoće, dobiti vrijednost *S*  veću od *x*. Očekivano *E*, koje je dobijeno u pretrazi baze D sekvenci, dato je obrascem:
#:: E\approx 1-e^{-p\left( s>x \right)D}
#: Štaviše, kada  je p, *E* može biti aproksimirano pomoću Poissonove distribucije, kao
#:: E\approx pD
#: Očekivana vrijednost *E* dodeljuje značaj vrijednostima HSP-a za lokalno poravnanje bez rupa, i to se predstavlja kao rezultat BLAST-a. Izračunavanja prikazana ovdje se modificiraju, ako se pojedinačni HSP-ovi kombiniraju kao da predstavljaju rupičasto poravnanje, zbog varijacije statističkih parametara.
# **Spajanje dvije ili više HSP-regija u duže poravnanje.**
#: Ponekad se nađu dvije ili više HSP-regija u jednoj sekvenci iz baze, koji se mogu spojiti u duže poravnanje. Ovo omogućava dodatnu evidenciju o relacijama između upita i sekvence iz baze. U tom pracvcu, postoje dva metoda:  Poissonov metod i rezultat sume kvadrata, za poređenje značajnosti novodobijenih HSP-regija. Ako se pretpostavi  postojanje dvije kombinirane HSP-regije sa vrijednostima (65, 40) i (52, 45), tada Poissonov metod pridaje veći značaj skupu sa maksimalnom nižom vrednošću (45>40). Međutim,  metod sume kvadrata  daje veći značaj prvom skupu, zato što je 65+40 (105) veće od 52+45(97). Originalni BLAST koristi Poissonov metod; BLAST2 i WU-BLAST primjenjuju metod sume kvadrata.
# **Prikaz ispražnjenog Smith-Watermanovog lokalnog poravnanja u upitu i uparenih sekvenci iz baze.**
#* Originalni BLAST generira samo cijela poravnanja, uključujući inicijalno uspostavljene HSP, čak i ako ima više od jednog HSP-a u sekvenci iz baze.
#* BLAST2 koristi jednostruko rupičasto poravnanje koje uključuje sve inicijalno pronađene HSP regije.
# '*Pokaz svakog pogotka čija je očekivana vrijednost manja od parametra *E*.*'

### Paralelni BLAST 
Verzija paralelnog BLAST-a, koja koristi razdvojene baze implementirana je korištenjem MPI i Pthreads, i prilagođena je različitim platformama, uključijući i Windows, Linux, Solaris, Mac OS X i AIX. Popularni pristup paraleliziranja BLAST-a uključuje distribuirane upite, segmentaciju keš tabela, paralelno računanje i segmentaciju baza. Baze su podeljene na jednake dijelove i čuvaju se na lokalnim čvorovima. Svaki upit pokrenut na svim čvorovima paralelno je  i izlazni za  fajlove koji su spojeni u finalni izlaz.

## Program 
Program BLAST-a može biti, ili preuzet, ili pokrenut iz komandne linije, ili se može koristiti besplatno onlajn. BLAST-ov web server, kojeg održava NCBI, dozvoljava svakome sa web pretraživačem da obavlja slične pretrage na konstantno ažuriranoj bazi proteina i DNK, koja uključuje većinu organizama.
Ovaj program je otvorenog koda, što daje svima mogućnost da ga i koriste i mijenjaju. To je dovelo do nastanka više varijanti programa BLAST.

Danas su dostupne različite korisne varijacije BLAST-a, koje mogu biti upotrebljene u zavisnosti od onoga šta se želi raditi i  čime se radi. Ove varijacije programa su različite po upitnim sekvencama baze koja se pretražuje i šta se upoređuje. Ovi programi i njihovi opisi su izlistani ispod:
BLAST je zapravo porodica programa (sve su uključene u Blastall ). Ovo uključuje:
;Nukleotid-nukleotid BLAST (blastn) je  program, kojem se zadaje upit o DNK, a vraća najsličniju DNK sekvencu iz baze koju je korisnik odabrao.
;Protein-protein BLAST (blastp): Ovaj program, kojem se zadaje proteinski upit, vraća najsličniju proteinsku odabranu sekvencu iz baze .
;Pozicijski-specifični interktivni BLAST (PSI-BLAST) (blastpgp) koristi se za pronalaženje daljih srodnika proteina. Prvo se kreira lista svih blisko povezanih proteina. Ovi proteini se kombiniraju u opću “profilnu" sekvencu, koja sumira značajne obilježja  u tim sekvencama. Upit na bazi proteina koristi taj profil i pronalazi veću grupu proteina. Ova veća grupa koristi se za pravljenje novog profila i proces se ponavlja. Blast  is an accelerated version of NCBI BLASTP for CUDA which is 3x~4x faster than NCBI Blast.
** CUDA-BLASTP is a version of BLASTP that is GPU-accelerated and is claimed to run up to 10x faster than NCBI BLAST.
** G-BLASTN
*  — free source downloads
* : Andy Baxevanis' lecture from NHGRI's Current Topics in Genome Analysis series, covering contemporary areas in genomics and bioinformatics
* : talk by Gene Myers (slides and video)

Kategorija:Bioinformatički algoritmi
Kategorija:Računska filogenetika
Kategorija:Softver za bioinformatiku
Kategorija:Bioinformatika