U bioinformatici, BLAST (eng. Basic Local Alignment Search Tool) je algoritam za upoređivanje primarnih bioloških sekvenci, kao što su aminokiseline različitih proteina ili nukleotidi DNK sekvenci. BLAST pretraga omogućava istraživačima da porede niz sekvenci sa bibliotekama ili bazama podataka sekvenci, i identifikuju biblioteku sekvenci koja odgovara traženoj, sa određenom greškom.
Različite vrste BLAST-a su dostupne u zavisnosti od vrste sekvence koja se pretražuje. Na primer, nakon otkrića prethodno nepoznatog gena kod miševa, naučnik će obično primeniti BLAST pretragu ljudskih genoma da proveri da li ljudi sadrže slične gene; BLAST će prepoznati sekvence u ljudskom genomu koji su nalik mišjem zasnovanom na sličnosti sekvenci. BLAST algoritam i program su dizajnirani od strane Stephen Altschul, Warren Gish, Webb Miller, Eugene Myers, i David J. Lipman u Nacionalnom institutu za zdravlje i objavljen je u Journal of Molecular Biology 1990. i citiran više od 50,000 puta.
Pozadina
BLAST je jedan od najčešće koršćenih programa u bioinformatici za pretragu sekvenci. On predstavlja fundamentalni problem u bioinformatici. Heuristički algoritam koji koristi 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 trenutno dostupnim bazama genoma, iako noviji algoritmi mogu biti još brži.
Pre BLAST-a, FASTA je kreiran od strane David J. Lipman i William R. Pearson 1985.
Pre brzih algoritama kao što su BLAST i FASTA, pretraga proteina i nukleinskih sekvenci je bila veoma vremenski zahtevna jer je korišćen potpun postupak poravnanja(npr., the Smith–Waterman algoritam).
Iako je BLAST brži od svih Smith-Waterman implementacija za većinu slučajeva, on ipak ne može da "garantuje optimalno poravnanje upita sa bazom sekvenci" kao Smith-Waterman algoritam. Optimalnost Smith-Waterman algoritma "obezbeđuje najveću tačnost i najpreciznije rezultate" po cenu vremena i resursa računara.
BLAST je vremenski efikasniji od FASTA jer pretražuje samo značajnije uzorake u sekvenci, ali sa određenom osetljivošću.
Primeri upotrebe BLAST-a: Koje vrste bakterija imaju protein koji je u vezi sa određenim proteinom koji ima poznatu aminokiselinu? Koji još geni predstavljaju proteine koji imaju strukturu sličnu onima koji su već otkriveni? BLAST je često korišćen kao deo drugih algoritama koji zahtevaju približno poklapanje sekvenci.
Ulaz Ulaz predstavljaju sekvence (u FASTA formatu ili Genbank formatu) i težinska matrica.
Izlaz
Izlaz BLAST algoritma može biti predstavljen na različite načine. Ovi formati mogu biti HTML, tekst i XML. Za NCBI web stranicu, podrazumevani format izlaza je HTML. Kada se izvrši BLAST algoritam na NCBI sajtu, rezultati su dati u grafičkom obliku i prikazuju pogotke, tabele prikazuju identifikatore sekvenci za pogotke zajedno sa pratećim podacima, kao i poravnanje sekvenci od interesa i pogotke dobijene korišćenjem odgovarajućeg BLAST vrednosnog sistema. Najjednostavnije za čitanje i najinformativnije su tabele.
Ako neko želi da pronađe sekvencu koje nema u bazama dostupnih javnosti putem izvora poput NCBI sajta, BLAST algoritam je moguće besplatno preuzeti sa interneta. Može se preuzeti sa NCBI sajtaBLAST+ executables. Dostupni su i komercijalni programi koji se mogu kupiti. Baze se mogu naći na NCBI sajtu, kao i na indeksu BLAST baza podatakaIndex of BLAST databases (FTP).
Proces Korišćenjem heurističkih metoda, BLAST nalazi slične sekvence, lociranjem kratkih poklapanja između dve sekvence. Ovaj proces pronalaženja se naziva sejanje (eng. seeding). Nakon prvog poklapanja BLAST počinje da pravi lokalna poravnanja. Dok pokušava da nađe sličnost u sekvenci, skup čestih slova, poznat kao reč, je veoma važan. Na primer, pretpostavimo da sekvenca sadrži sledeći niz slova: GLKFA. Ako se BLAST pokrene pod normalnim uslovima, dužina reči bi bila 3 slova. U ovom slučaju, korišćenjem datog niza slova, dobijene reči bi bile GLK, LKF, KFA. BLAST-ov heuristički algoritam locira sve česte pojave troslovnih reči između zadate i pronađene sekvence. Ovaj rezultat se zatim koristi za pravljenje poravnanja. Nakon što je napravio reči za posmatranu sekvencu, ostale reči su takođe obrađene. Ove reči moraju da imaju zadovoljen prag T, u poređenju sa matricom vrednosti. Često korišćena matrica vrednosti za BLAST pretrage je BLOSUM62, iako optimalna matrica vrednosti zavisi od sličnosti sekvenci. Kada su reči, kao i okolne reči, procesuirane one se porede sa sekvencama iz baze u cilju pronalaska poklapanja. Prag T određuje da li konkretna reč ulazi u poravnanje. Kada je sejanje izvršeno, poravnanje koje je samo dužnine 3, je prošireno u oba smera pomoću BLAST algoritma. Svako proširenje utiče na rezultat poravnanja bilo povećanjem bilo smanjenjem. Ako je rezultat veći od unapred određenog T, poravnanje će biti uključeno u rezultat BLAST-a. Međutim, ako je rezultat manji od unapred određenog T, poravnanje će prestati da se širi, sprečavajući da se segmenti sa lošim poravnanjem uključe u rezultat BLAST-a. Primetimo da povećanjem T ograničavamo prostor koji možemo da pretražujemo, smanjujemo broj susednih reči, dok u isto vreme ubrzavamo BLAST.
Algoritam Za pokretanje programa, BLAST zahteva unos sekvence za pretragu, i sekvence sa kojom će upoređivati (takođe se naziva 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, npr., upit može sadržati hiljadu nukleotida, dok baza sadrži nekoliko milijardi nukleotida.
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 sekvenci između upitne i posmatrane sekvence iz baze, koristeći heuristički pristup koji aproksimira Smith-Waterman algoritam. Međutim, iscrpni Smith-Waterman pristup je suviše spor za pretraživanje velikih baza genoma, kao što je GenBank. Stoga, BLAST algoritam koristi heuristički pristup koji je manje precizan od Smith-Waterman 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 regiona ili ponavljanje sekvenci iz upita. "Nekompleksni region" predstavlja region sekvenci sastavljen od nekoliko vrsti elemenata. Ovi regioni mogu da onemoguće program da nađe bitnu sekvencu u bazi, pa bi ih trebalo isfiltrirati. Ti regioni će biti obeleženi sa X(proteinske sekvence) ili N (nukleinske kiseline) i biće ignorisane od strane BLAST programa. Za filtriranje nekompleksnih regiona, za proteinske sekvence se koristi program SEGSEG, a za DNK sekvence program DUSTDUST. Pravljenje k-slovne liste reči od upitne sekvence. Uzmimo k=3 kao primer. Izlistavamo reči dužine 3 iz upitne proteinske sekvence (k je obično 11 za DNK sekvencu) "sekvencijalno", dok sva slova upitne sekvence ne budu uključena. Metod je prikazan na slici 1.мини|Slika1 Metoda za pravljenje "k"-slovne liste upitnih reči Lista mogućih reči koje se poklapaju. Ovaj korak je jedna od glavnih razlika između BLAST-a i FASTA. FASTA koristi sve česte reči nađene u koraku 2; međutim, BLAST koristi jedino visokovrednovane reči. Vrednosti su kreirane upoređivanjem reči dobijenih u koraku 2 sa svim preostalim rečima. Korišćenjem matrice vrednosti i poređenjem svih parova, postoji 20³ mogućih vrednosti za troslovne reči. Na primer, vrednost dobijena poređenjem PQG sa PEG i PQA je 15 i 12, redom. Za DNK reči, pogodak se računa kao +5, a promašaj kao -4, ili kao +2 i -3. Nakon toga, vrednost praga susednih reči T se koristi da smanji broj mogućih reči koje se poklapaju. Reči čije su vrednosti veće od praga T će ostati na listi tih reči, dok će reči čija je vrednost manja od ovog praga biti odbačene. Na primer, PEG se čuva, ali PQA je odbačen kada je T = 13. Organizacija visoko rangiranih reč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 reč iz upitne sekvence. Pretraga baze radi pronalaženja egzaktnog poklapanja sa preostalim visoko rangiranim rečima. BLAST program pretražuje bazu po preostalim visoko rangiranim rečima, kao što je PEG, po svakoj poziciji. Ako se pronađe egzaktno poklapanje, ono se koristi za sejanje 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 dugačko poravnanje između upita i sekvenci iz baze u oba smera od pozicije gde je pronađeno egzaktno poklapanje. Proširenje ne prestaje sve dok nagomilana vrednost HSP-a ne počne da opada. мини|Slika2 Pozicija egzaktnih pogodaka Radi uštede vremena, novija verzija BLAST-a, zvana BLAST2, je razvijena. BLAST2 prisvaja niže rangirane susedne reči da bi očuvao isti nivo osetljivosti za otkrivanje sličnih sekvenci. Stoga, lista mogućih poklapanja iz koraka 3 postaje duža. Dalje, regioni kod kojih je došlo do egzaktnog poklapanja, koji su na međusobnom rastojanju A na istoj dijagonali na slici 2, biće spojeni u jedan dugačak novi region. Konačno, novi regioni su prošireni na isti način kao u originalnoj verziji BLAST-a. Lista svih HSP u bazi čija je vrednost dovoljno velika da budu uzeti u obzir. Listamo HSP vrednosti koje su veće od empirijski utvrđenih granica vrednosti S. Proučavanjem distribucije vrednosti poravnanja dobijene poređenjem slučajnih sekvenci granična vrednost S može biti utvrđena tako da njena vrednost bude dovoljno velika da garantuje značajan ostatak HSP-a. Procena značajnosti HSP vrednosti. BLAST dalje pristupa statističkom značenju svake HSP vrednosti korišćenjem Gumbelove distribucije ekstremnih vrednosti (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:
gde je
Statistički parametri i se procenjuju na osnovu vrednosti poravnanja bez rupa. Primetimo da i zavise od matrice zamene 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 kompenzovala efekat ivice. Mogu se izračunati kao:
gde je očekivana prosečna vrednost po poravnatom paru u poravnanju dve slučajne sekvence. Altschul i Gish dali su uobičajene vrednosti, , , i , za lokalno poravnanje bez rupa, korišćenjem BLOSUM62BLOSUM62 kao matrice zamene. Korišćenje tipičnih vrednosti za dodeljivanje značajnosti se zove lookup-table metod, i on nije precizan. Očekivana vrednost E je broj koliko puta će nepovezana sekvenca iz baze dobiti vrednost S veću od x po verovatnoći. Očekivano E, koje je dobijeno u pretrazi baze od D sekvenci, dato je sa
Šta više, kada , E može biti aproksimirano pomoću the Poisson distribucije kao
Očekivana vrednost E dodeljuje značaj HSP vrednostima za lokalno poravnanje bez rupa, i to se predstavlja kao rezultat BLAST-a. Izračunavanja prikazana ovde se modifikuju ako se pojedinačni HSP kombinuju kao da predstavljaju rupičasto poravnanje, zbog varijacije statističkih parametara. Spajanje dva ili više HSP regiona u duže poravnanje.