U bioinformatici, BLAST (eng. Basic Local Alignment Search Tool) 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 s 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 sajtaBLAST+ executables. Dostupni su i komercijalni programi, a baze se mogu naći na NCBI sajtu, kao i na indeksu BLAST baza podatakaIndex of BLAST databases (FTP).
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 (High-scoring Segment Pairs – 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 SEGSEG, a za DNK sekvence program DUSTDUST. 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. 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 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. мини|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)Gumbel extreme value distribution (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:
gdje je
Statistički parametri i procjenjuju se na osnovu vriednosti poravnanja bez rupa. Tako da i zavise od matrice zamjene i kompozicije sekvence. i 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:
gdje je očekivana srednja vrijednost po poravnatom paru u poravnanju dvije slučajne sekvence. Altschul i Gish dali su uobičajene vrednosti, , , i , 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:
Štaviše, kada je , E može biti aproksimirano pomoću Poissonove distribucije, kao
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.