Izvorni kôd stranice BLAST

{{Infokutija organizacija
| ime                            = <big>BLAST</big>
<br>
| slika                          =  CCDC132_Blast_Results.png     
| veličina_slike                 = 320px
| opis_slike                     =BLAST-ov rezultata za [[protein]] [[CCDC132]].
| karta                          = 
| veličina_karte                 = 
| opis_karte                     = 
| skraćenica                     = 
| uzrečica                       =
| nasljednik                     =[[FASTA]]-e, iz 1985
| datum_osnivanja                = 1990.
| datum_gašenja                  =
| vrsta                          = Baza genomskih podataka 
| status                         = Aktivna
| cilj                           = 
| glavno_sjedište                = [[NCBI]],  [[SAD]]
| glavno_sjedište_koordinate     = 
| područje_uticaja               =Globalno
| članstvo                       =
| jezik                          = [[Engleski jezik|Engleski]]
| generalni_sekretar             = 
| direktor                       =Autori: [[Stephen Altschul|Altschul SF]], [[Warren Gish|Gish W]], [[Webb Miller|Miller W]], [[Eugene Myers|Myers EW]], [[David Lipman|Lipman DJ]], 
| lider_ime1                     =
| glavni_organ                   =
|pmid=9097728          
| broj_zaposlenih                = 
| platforma = [[UNIX]], [[Linux]], [[Apple Macintosh|Mac]], [[Microsoft Windows]]
| broj_volontera=Neograničen
| web_stranica                   = {{URL|http://blast.ncbi.nlm.nih.gov/Blast.cgi}} 
}}
U [[bioinformatika|bioinformatici]], '''BLAST''' ([[Engleski jezik|eng.]] '''B'''asic '''L'''ocal '''A'''lignment '''S'''earch '''T'''ool) je [[algoritam]] za poređenje primarnih bioloških sekvenci, kao što su [[Aminokiselina|aminokiseline]] raznih [[Bjelančevine|proteina]] ili [[nukleotid]], a u [[molekula]]ma [[Dezoksiribonukleinska kiselina|DNK]].<ref>{{cite journal  
   |journal=The New York Times
   |url=https://www.nytimes.com/2008/02/21/us/21karlin.html
   |title=Samuel Karlin, Versatile Mathematician, Dies at 83
   |author=Douglas Martin |date=21. 2. 2008}}</ref> Pretraživač BLAST pomogućava spoređenje mnoštva sekvenci sa bibliotekama ili [[Baza podataka|bazama podataka]] o sekvencama i identificiraju sekvencu koja odgovara traženoj, sa određenom greškom.

BLAST-u  je ''The New York Times'' nazivao ''[[Google]]om bioloških istraživanja'' i jedan je od najčešće korištenih bioinformatičkih programa za pretraživanje sekvenci.<ref>{{cite web 
   |author=R. M. Casey |year=2005 
   |title=BLAST Sequences Aid in Genomics and Proteomics 
   |publisher=Business Intelligence Network 
   |url=http://www.b-eye-network.com/view/1730}}</ref>

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 [[Projekt ljudskog genoma|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 [[Nacionalni instituti za zdravlje|Nacionalnom institutu za zdravlje]] [[Sjedinjene Američke Države|Sjedinjenih Država]]  i objavili u ''Journal of Molecular Biology'', 1990.<ref name="Altschul1990">{{Cite journal | last1 = Altschul| first1 = Stephen| authorlink1 = Stephen Altschul| last2 = Gish| first2 = Warren| authorlink2 = Warren Gish| last3 = Miller| first3 = Webb| authorlink3  = Webb Miller | last4 = Myers| first4 = Eugene | authorlink4 = Eugene Koonin| last5 = Lipman| first5 = David| authorlink5 = David J. Lipman | title = Basic local alignment search tool | doi = 10.1016/S0022-2836(05)80360-2 | journal = Journal of Molecular Biology | volume = 215 | issue = 3 | year = 1990| pmid =  2231712| url = http://www.blastalgorithm.com| pmc = | pages = 403–410}}</ref>

==Okviri==
BLAST je jedan od najčešće koršćenih programa u bioinformatici za pretragu sekvenci.<ref>{{cite web | last = Casey| first = R. M. | year = 2005| title = BLAST Sequences Aid in Genomics and Proteomics | publisher = Business Intelligence Network | url = http://www.b-eye-network.com/view/1730}}</ref> Predstavlja temelj za rješavanje problem u [[bioinformatika|bioinformatici]]. Korišteni [[Heuristika (informatika)|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.<ref>{{cite journal | pmid = 2983426 | year = 1985| title = Rapid and sensitive protein similarity searches | volume = 227 | issue = 4693 | journal = Science | doi = 10.1126/science.2983426 | last1 = Lipman| first1 = DJ | last2 = Pearson| first2 = WR| pages = 1435–41}}</ref>
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 [[Nacionalni centar za biotehnološke informacije|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 [[internet]]a. Može se preuzeti sa NCBI sajta<ref>[http://blast.ncbi.nlm.nih.gov/Blast.cgi?CMD=Web&PAGE_TYPE=BlastDocs&DOC_TYPE=Download BLAST+ executables]</ref>. Dostupni su i komercijalni programi, a baze se mogu naći na NCBI sajtu, kao i na indeksu BLAST baza podataka<ref>[ftp://ftp.ncbi.nlm.nih.gov/blast/db/ Index of BLAST databases] (FTP)</ref>.

== 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.<ref>{{cite journal  
   |author1=Steven Henikoff  |author2=Jorja Henikoff
   |year=1992| journal=PNAS |volume=89 |pages=10915–10919
   |pmid=1438297 |title=Amino Acid Substitution Matrices from Protein Blocks 
   |doi=10.1073/pnas.89.22.10915  |issue=22 |pmc=50453|bibcode=1992PNAS...8910915H}}</ref>

== 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 [[nukleotid]]a, 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):<ref>{{Cite book| last = Mount| first = D. W. | title = Bioinformatics: Sequence and Genome Analysis | year = 2004| url = http://www.bioinformaticsonline.org/ | publisher = Cold Spring Harbor Press | isbn = 978-0-87969-712-9 | edition = 2nd}}</ref><sup> and [https://www.youtube.com/watch?v=SAweFv8I8ow CTGA2016]</sup>
# '''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 ([[protein]]ske sekvence) ili N ([[nukleinske kiseline]]) i biće ignorirane u programu  BLAST-a. Za filtriranje nekompleksnih regija proteinskih sekvenci koristi se program SEG<ref>[http://www.ncbi.nlm.nih.gov/Education/BLASTinfo/Seg.html SEG]</ref>, a za DNK sekvence program DUST<ref>[ftp://ftp.ncbi.nlm.nih.gov/pub/agarwala/windowmasker/windowmasker_suppl.pdf DUST]</ref>.
# '''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.
[[slika:Metodazapravljenjekslovnelisteupitnihreci.png|thumb|280px|Metod kreiranja "k"-slovne liste upitnih reči]]
# '''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 20<sup>3</sup> 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. [[slika:Pozicijaegzaktnihpogodaka.jpg|мини|Pozicija egzaktnih pogodaka]]
#* 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)<ref>[http://www.itl.nist.gov/div898/handbook/eda/section3/eda366g.htm Gumbel extreme value distribution (EVD)]</ref>. 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:
:: <math>p\left( S\ge x \right)=1-\exp \left( -e^{-\lambda \left( x-\mu  \right)} \right)</math>
: gdje je
:: <math>\mu ={}^{\left[ \log \left( Km'n' \right) \right]}\!\!\diagup\!\!{}_{\lambda }\;</math>
#: Statistički parametri<math>\lambda</math> i <math>\mathrm{K}</math> procjenjuju se na osnovu vriednosti poravnanja bez rupa. Tako da <math>\lambda</math> i <math>\mathrm{K}</math> zavise od matrice zamjene i kompozicije sekvence. <math>m'</math> i <math>n'</math> 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:
:: <math>m'\approx m-{}^{\left( \ln Kmn \right)}\!\!\diagup\!\!{}_{H}\;</math>
:: <math>n'\approx n-{}^{\left( \ln Kmn \right)}\!\!\diagup\!\!{}_{H}\;</math>
: gdje je <math>\mathrm{H}</math> očekivana [[srednja vrijednost]] po poravnatom paru u poravnanju dvije slučajne sekvence. Altschul i Gish dali su uobičajene vrednosti, <math>\lambda = 0,318</math>, <math> \mathrm{K} = 0,13</math>, i <math>\mathrm{H} = 0,40</math>, za lokalno poravnanje bez rupa, korišćenjem BLOSUM62<ref>[http://www.ncbi.nlm.nih.gov/Class/FieldGuide/BLOSUM62.txt BLOSUM62]</ref> 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:
#:: <math>E\approx 1-e^{-p\left( s>x \right)D}</math>
#: Štaviše, kada  je <math>p<0,1</math>, ''E'' može biti aproksimirano pomoću [[Poissonova distribucuija|Poissonove distribucije]], kao
#:: <math>E\approx pD</math>
#: 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 [[Microsoft Windows|Windows]], [[Linux]], [[Solaris operativni sistem|Solaris]], [[MacOS|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.<ref>{{cite journal |last1=Yim |first1=WC |last2=Cushman |first2=JC |title=Divide and Conquer (DC) BLAST: fast and easy BLAST execution within HPC environments |journal=PeerJ |date=2017 |volume=5 |pages=e3486 |doi=10.7717/peerj.3486 |pmid=28652936 |pmc=5483034}}</ref>

== 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 [[Nacionalni centar za biotehnološke informacije|NCBI]], dozvoljava svakome sa web pretraživačem da obavlja slične pretrage na konstantno ažuriranoj bazi [[protein]]a i [[DNK]], koja uključuje većinu [[organizam]]a.
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:<ref>{{cite web| title = Program Selection Tables of the Blast NCBI web site | url = http://blast.ncbi.nlm.nih.gov/Blast.cgi?CMD=Web&PAGE_TYPE=BlastDocs&DOC_TYPE=ProgSelectionGuide}}</ref>
;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 <ref>{{cite journal|title=GPU-BLAST: using graphics processors to accelerate protein sequence alignment|journal=Bioinformatics|volume=27|issue=2|pages=182–8|year=2010|doi=10.1093/bioinformatics/btq644|pmid=21088027|url=http://bioinformatics.oxfordjournals.org/content/27/2/182|last1=Vouzis|first1=P. D.|last2=Sahinidis|first2=N. V.|pmc=3018811}}</ref> is an accelerated version of NCBI BLASTP for [[CUDA]] which is 3x~4x faster than NCBI Blast.
** CUDA-BLASTP<ref>{{cite journal |vauthors=Liu W, Schmidt B, Müller-Wittig W |title=CUDA-BLASTP: accelerating BLASTP on CUDA-enabled graphics hardware |journal=IEEE/ACM Trans Comput Biol Bioinform |volume=8 |issue=6 |pages=1678–84 |date=2011 |pmid=21339531 |doi=10.1109/TCBB.2011.33}}</ref> is a version of BLASTP that is GPU-accelerated and is claimed to run up to 10x faster than NCBI BLAST.
** G-BLASTN<ref>{{cite journal |vauthors=Zhao K, Chu X |title=G-BLASTN: accelerating nucleotide alignment by graphics processors |journal=Bioinformatics |volume=30 |issue=10 |pages=1384–91 |date=maj 2014 |pmid=24463183 |doi=10.1093/bioinformatics/btu047</ref>
:Uključivanjem povezanih proteina u pretragu, PSI-BLAST je osetljiviji u izboru srodnika iz [[Filogenetsko stablo|filogenetskog stabla]], od običnog protein-protein BLAST-a.
;Nukleotid]ni 6-okvir translacije proteina (blastx) poredi šest okvira koncepta translacije [[nukleotid]]a upitne sekvence sa proteinom iz baze.
;Nukleotidna 6-okvirna translacija nukleotida 6-okvirnom  translacijom (tblastx) je najsporiji program  BLAST-ove porodice. Translira upitnu sekvencu nukleotida u svih šest mogućih okviraa i poredi ih sa šest okvira, translacijom nukleotida upitne sekvence sa proteinom iz baze. Svrha ovoga je da nađe veoma daleke veze između [[nukleotid]]nih sekvenci.
;Protein-nukleotidna 6-okvirna translacija (tblastn) poredi upit sa svih šest okvira sa sekvencom nukleotida iz baze.
;Veliki broj upitnih sekvenci (megablast): Pri upoređivanju velikog broja ulaznih sekvenci putem BLAST-a komandne linije, "megablast" je mnogo brži od višestrukog pokretanja BLAST-a. Obavlja konkatenaciju više ulaza, kako bi formirao veliku sekvencu pre pretrage, a zatim se naknadnom analizom dobijaju konačni rezultati.

=== Alternativne verzije ===
Dizajnirana verzija za poređenje velikih genoma ili DNK je BLASTZ.
CS-BLAST ('''C'''ont'''S'''xt-Specific '''BLAST''') je proširena verzija BLAST-a za pretragu proteinskih sekvenci, koja pronalazi dvostruko više daleko povezanijih sekvenci od BLAST-a za isto vrijeme i sa istom stopom greške. U CS-BLAST-a, vjerovatnoća [[mutacija]] između [[aminokiselina]] ne ovisi samo od jedne aminokiseline kao u BLAST-u, već i od konteksta lokalne sekvence. Vašingtoski univerzitet napravio je alternativnu verziju NCBI BLAST-a, zvanu WU-BLAST. Autorska prava pripadaju kompaniji  ''Advanced Bioco'', a [[NCBI]] objavio je novu seriju BLAST-ovih izvršnih programa, C++ zasnovani BLAST+,<ref name="Camacho2009">{{Cite journal | last1 = Camacho| first1 = C. | last2 = Coulouris| first2 = G. | last3 = Avagyan| first3 = V. | last4 = Ma| first4 = N. | last5 = Papadopoulos| first5 = J. | last6 = Bealer| first6 = K. | last7 = Madden| first7 = T. L. | title = BLAST+: Architecture and applications | doi = 10.1186/1471-2105-10-421 | journal = BMC Bioinformatics | volume = 10 | year = 2009| pmid =  20003500| pmc =2803857 | pages = 421}}</ref>, i objavio je paralelnu verziju do 2.2.26. Počevši sa verzijom 2.2.27 (April 2013),  dostupni su samo BLAST+ izvršni programi. Među izmjenama je i zamjena <code>blastall</code> komande za više različitih uputa za različite BLAST programe i promjene u rukovanju opcijama.

== Alternative BLAST-a ==
Ekstremno brza, ali znatno manje osetljiva, alternativa BLAST-u je BLAT ([[engleski|eng.]] '''B'''last '''L'''ike '''A'''lignment '''T'''ool). Dok BLAST obavlja linearnu pretragu, BLAT se oslanja na k-mer indeksiranje baze  i na tako često može brže pronaći sjeme. .<ref>{{Cite journal|last=Kent|first=W. James|date=1. 4. 2002|title=BLAT—The BLAST-Like Alignment Tool|journal=Genome Research|language=en|volume=12|issue=4|pages=656–664|doi=10.1101/gr.229202|issn=1088-9051|pmc=187518|pmid=11932250}}</ref> Još jedan program sličan BLAT-u je ''PatternHunter''.

Napretkom tehnologija sekvenciranja, kasnih 2000-tih, nalaženje veoma sličnih nukleotida postaje važan problem. Novi programi poravnanja skovani za ovu specifičnu upotrebu koriste BWT-indeksiranje ciljane baze (obično [[genom]]a). Ulazna sekvenca može biti mapirana vrlo brzo, a izlaz je obično u vidu BAM-fajla. Primjeri programa poravnanja su ''BWA'', ''SOAP'' i ''Bowtie''.
Za identificiranje  proteina, traženje poznatih domena (npr. [[Pfam]]) povezivanjem sa [[Skriveni Markovljev model|Skrivenog Markovljevog modela]] popularna je alternativa, kao što je npr. HMMER.
Alternativa BLAST-u za poređenje dvije banke sekvenci je KLAST<ref>{{cite journal |last1=Lavenier |first1=D. |year=2009|doi=10.1186/1471-2105-10-329 |pmid=19821978 |title=PLAST: parallel local alignment search tool for database comparison |journal=BMC Bioinformatics |volume=10 |pages=329 |last2=Lavenier |first2=Dominique |pmc=2770072 }}</ref> and ORIS<ref>{{cite book|doi=10.1109/IPDPS.2008.4536172|last=Lavenier |first=D. |year=2009 |chapter-url=http://www.hicomb.org/papers/HICOMB2008-01.pdf|chapter=Ordered index seed algorithm for intensive DNA sequence comparison |title=2008 IEEE International Symposium on Parallel and Distributed Processing |isbn=978-1-4244-1693-6 |pages=1–8 |url=https://hal.archives-ouvertes.fr/hal-00322696/file/lavenier_1569087275.pdf }}</ref>. Rezultati KLAST-a su veoma slični rezultatiima BLAST-a, ali KLAST je značajno brži i sposobniji da poredi velike skupove sekvenci sa malim utroškom memorije.

== Primjena BLAST-a ==
BLAST se može koristiti za više različitih potreba, uključujući i  identifikaciju [[vrsta]], lociranje domena, rekonstrukciju [[filogeneza|filogeneze]], [[genetičko mapiranje|DNK mapiranje]] i poređenje.

;Identifikacija vrsta: upotrebomm BLAST-a, moguće je tačno identificirati ili naći odgovarajuću vrstu. To može biti korisno, naprimjer, za rad sa DNK sekvencama nepoznatih vrsta.
;Lociranje domena: proteinske sekvence moguće je upotrebiti kao ulaz BLAST, da bi se locirali poznati domeni te sekvence.

;Uspostava filogenije : Korištenjem rezultata BLAST-a, moguće je kreirati [[filogenetsko stablo]] putem BLAST web-stranice. Filogenija zasnovana samo na BLAST-u je manje pouzdana nego drugi, namjenski kreiranei, filogenetski metodi, tako da bi trebalo da bude korišćena samo kao prvi i orijentacijski produkt analize.

; Mapiranje DNK: U radu sa poznatim vrstama i traganjz za  sekvencama gena na nepoznatoj lokacijii, BLAST može porediti hromosomske pozicije sekvenci DNK.
;Poređenje: U radovima  sa  genskim pokazateljima , BLAST može locirati česte gene u dvije povezane vrste, a može se koristiti i za mapiranje razlika među organizmima. [[Optičko računrstvo|Optičkoračunarski]] pristupi su predloženi za obećavajuće alternative sadašnjim električnim implementacijama. OptCAM je primjer takvih pristupa i pokazalo se da je brži od BLAST-a.<ref>{{Cite journal | doi=10.1002/jbio.201900227 |pmid = 31397961|title = OptCAM: An ultra‐fast all‐optical architecture for DNA variant discovery|journal = Journal of Biophotonics|pages = e201900227|year = 2020|last1 = Maleki|first1 = Ehsan|last2 = Koohi|first2 = Somayyeh|last3 = Kavehvash|first3 = Zahra|last4 = Mashaghi|first4 = Alireza|volume = 13|issue = 1|doi-access = free}}</ref>

== Poređenje BLAST-a i Smith-Watermanovog procesa ==
Iako se i Smith-Watermanov metod  i BLAST koriste za pronalaženje odgovaraćujih sekvenci pretragom i poređenje upitne sekvence sa onim iz baza, imaju određene  razlike.
BLAST zasnovan na heurističkom algoritmu, pa rezultati dobijeni njegovom primjrnom, u terminima broja pronađenih pogodaka, možda neće dati najbolje rezultate, jer neće pronaći sva podudaranja sa bazom.
Bolja alternativa za pronalaženje najboljeg mogućeg rješenja bila bi korišćenje Smith-Watermanovog algoritma. Ovaj metod se razlikuje od BLAST-a po  preciznosti i brzni. Smith-Watermanov metod  obezbjeđuje veću preciznost, jer pronalazi podudaranja koja BLAST ne može,  zato što ne preskače nijednu informaciju. Međutim, u poređenju sa BLAST-om, troši više vremena i zahtijeva veću količinuračunarskih resursa. Pronađene su tehnologije koje mogu znatno da ubrzaju Smith-Watermanov proces. Uključuju [[FPGA]] čipove i [[SIMD]] technologiju.

Za dobijanje boljih rezultata BLAST-a, mogu se promijeniti podrazumijevana podešavanja. Ne postoji siguran način za mijenjanje podešavanja, kako bi se obezbijedio najbolji rezultat za datu sekvencu.

== Također pogledajte==
* [[Logaritmi]]
* [[Nacionalni centar za biotehnološke informacije]]
* [[Poravnavanje sekvenci]]
{{Div col end}}

== Reference ==
{{reflist|}}

== Dopunska literatura ==
{{refbegin}}
* {{Cite book | ref = harv| last = Mount| first = D. W. | title = Bioinformatics: Sequence and Genome Analysis | year = 2004| url = http://www.bioinformaticsonline.org/ | publisher = Cold Spring Harbor Press | isbn = 978-0-87969-712-9 | edition = 2nd}}
* {{cite book| chapter = Chapter 11: Assessing Pairwise Sequence Similarity: BLAST and FASTA | title = Bioinformatics: A Practical Guide to the Analysis of Genes and Proteins, Third Edition | first1 = Andy | last1 = Baxevanis| location = New York | publisher = John Wiley & Sons | year = 2005| url = http://www.wiley.com/WileyCDA/WileyTitle/productCd-0471478784.html}}
* {{cite book| chapter = Chapter 9: BLAST QuickStart | title = Comparative Genomics Volumes 1 and 2 | series = Methods in Molecular Biology | volume = 395-396 |editor-first=Nicholas H |editor-last=Bergman| location = Totowa, NJ | publisher = Humana Press | year = 2007| pmid = 21250292 | first1 = David | last1 = Wheeler| first2 = Medha | last2 = Bhagwat| url = http://www.ncbi.nlm.nih.gov/books/NBK1734/}}
* {{cite journal | title = Using the Basic Local Alignment Search Tool (BLAST) | last = Mount| first = DW| date = 1. 7. 2007 | journal = Cold Spring Harbor Protocols | volume = 2007 | issue = 14 | pages = pdb.top17 | doi = 10.1101/pdb.top17 | url = http://www.cshprotocols.org/cgi/content/full/2007/14/pdb.top17 | pmid = 21357135}}
{{refend}}

== Vanjski linkovi ==
*http://blast.ncbi.nlm.nih.gov/}}
* {{URL|1=ftp://ftp.ncbi.nlm.nih.gov/blast/executables/blast+/LATEST/ |2=BLAST+ executables}} — free source downloads
* {{URL|1=https://www.youtube.com/watch?v=SAweFv8I8ow |2=Biological Sequence Analysis I}}: Andy Baxevanis' lecture from NHGRI's [https://www.genome.gov/ctga2016/ Current Topics in Genome Analysis] series, covering contemporary areas in genomics and bioinformatics
* {{URL|1=https://tech.yandex.com/events/cpm/2014/talks/169/ |2=What's behind BLAST?}}: talk by Gene Myers (slides and video)
{{commonscat|BLAST}}

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