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.
Programer(i) | Altschul SF, Gish W, Miller W, Myers EW, Lipman DJ, NCBI |
---|---|
Najnovija verzija | 2.5.0+ 12. септембар 2016. год. |
Platforma | UNIX, Linux, Mac, Microsoft Windows |
Tip | Bioinformatika |
Licenca | Javno vlasništvo |
Veb-sajt | blast |
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.
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:
BLAST je često korišćen kao deo drugih algoritama koji zahtevaju približno poklapanje sekvenci.
Ulaz predstavljaju sekvence (u FASTA formatu ili Genbank formatu) i težinska matrica.
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 sajta. Dostupni su i komercijalni programi koji se mogu kupiti. Baze se mogu naći na NCBI sajtu, kao i na indeksu BLAST baza podataka.
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.
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
Verzija paralelnog BLAST-a koja koristi razdvojene baze je implementirana korišćenjem MPI i Pthreads, i prilagođena je različitim platformama, uključijući i Windows, Linux, Solaris, Mac OS X i AIX. Popularni pristup paralelizacije BLAST-a uključuje distribuirane upite, segmentaciju heš tabela, paralelno računanje i segmentaciju baza. Baze su podeljene na jednake delove i čuvaju se na lokalnim čvorovima. Svaki upit je pokrenut na svim čvorovima paralelno i izlazni fajlovi su spojeni u finalni izlaz.
BLAST program može biti, ili preuzet, ili pokrenut iz komandne linije, ili se može koristiti besplatno onlajn. BLAST-ov web server, održavan od strane NCBI, dozvoljava svakome sa web pretraživačem da izvršava slične pretrage na konstantno ažuriranoj bazi proteina i DNK, koja uključuje većinu organizama.
BLAST program je otvorenog koda, što daje svima mogućnost da ga koriste i menjaju. Ovo je dovelo do nastanka više varijanti BLAST programa.
Danas su dostupne različite korisne varijacije BLAST-a, koje mogu biti korišćene u zavisnosti od onoga šta želimo da uradimo i sa čime radimo. Ove varijacije programa su različite po pitanju upitnih sekvenci, baze koja se pretražuje i šta se upoređuje. Ovi programi i njihovi opisi su izlistani ispod:
BLAST je zapravo familija programa (sve su uključene u blastall izvršavanje). Ovo uključuje:
Verzija dizajnirana za upoređivanje velikih genoma ili DNK je BLASTZ.
CS-BLAST (ContSxt-Specific BLAST) je proširena verzija BLAST-a za pretragu proteinskih sekvenci koja pronalazi dvostruko više daleko povezanih sekvenci od BLAST-a za isto vreme i sa istom stopom greške. U CS-BLAST-a, verovatnoća mutacije između aminokiselina ne zavisi samo od jedne aminokiseline kao u BLAST-u, već i od konteksta lokalne sekvence. Vašington Univerzitet napravio je alternativnu verziju NCBI BLAST-a, zvanu WU-BLAST. Autorska prava pripadaju Advanced Biocomputing, LLC.
2009. NCBI je objavio novu seriju BLAST izvršnih programa, C++ zasnovani BLAST+,, i objavio je paralelnu verziju do 2.2.26. Počevši sa verzijom 2.2.27 (April 2013), samo BLAST+ izvršni programi su dostupni. Među izmenama je i zamena blastall
komande za više različitih komandi za različite BLAST programe, i promene u rukovanju opcijama.
Ekstremno brza, ali znatno manje osetljiva, alternativa BLAST-u je BLAT (eng. Blast Like Alignment Tool). Dok BLAST vrši linearnu pretragu, BLAT se oslanja na k-mer indeksiranje baze, i na taj način često može brže da pronađe seme. Još jedan program sličan BLAT-u je PatternHunter.
Napretkom tehnologija sekvencioniranja kasnih 2000-tih, pronalaženje veoma sličnih nukleotida postaje važan problem. Novi programi poravnanja skrojeni za ovu specifičnu upotrebu koriste BWT-indeksiranje ciljane baze (obično genoma). Ulazna sekvenca može biti mapirana vrlo brzo, a izlaz je obično u vidu BAM fajla. Primeri programa poravnanja su BWA, SOAP i Bowtie.
Za identifikaciju proteina, traženje poznatih domena (npr. Pfam) povezivanjem sa Hidden Markov Models je popularna alternativa, kao što je npr. HMMER.
Alternativa BLAST-u za poređenje dve banke sekvenci je KLAST. 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.
BLAST se može koristiti u više svrha. Ovo uključuje identifikaciju vrsti, lociranje domena, uspostavljanje filogenije, DNK mapiranje i poređenje.
Dok se i Smith-Waterman i BLAST koriste za pronalaženje odgovaraćujih sekvenci pretragom i poređenje upitne sekvence sa onim iz baza, oni imaju razlike.
Iako je BLAST zasnovan na heurističkom algoritmu, rezultati dobijeni upotrebom BLAST-a, 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 rešenja bila bi korišćenje Smith-Waterman algoritma. Ovaj metod se razlikuje od BLAST-a u dve oblasti, preciznosti i brzni. The Smith-Waterman obezbeđuje veću preciznost, jer pronalazi podudaranja koja BLAST ne može, jer ne preskače nijednu informaciju. Međutim, u poređenju sa BLAST-om, troši više vremena i zahteva veću količinu kompjuterskih resursa. Pronađene su tehnologije koje mogu znatno da ubrzaju Smith-Waterman proces. Te tehnologije uključuju FPGA čipove i SIMD technologiju.
Za dobijanje boljih rezultata BLAST-a, podrazumevana podešavanja se mogu promeniti. Ne postoji siguran način za menjanje podešavanja kako bi se obezbedio najbolji rezultat za datu sekvencu.
This article uses material from the Wikipedia Српски / Srpski article BLAST, which is released under the Creative Commons Attribution-ShareAlike 3.0 license ("CC BY-SA 3.0"); additional terms may apply (view authors). Садржај је доступан под лиценцом CC BY-SA 4.0 осим ако је другачије наведено. Images, videos and audio are available under their respective licenses.
®Wikipedia is a registered trademark of the Wiki Foundation, Inc. Wiki Српски / Srpski (DUHOCTRUNGQUOC.VN) is an independent company and has no affiliation with Wiki Foundation.