БЛАСТ

У биоинформатици, БЛАСТ (енг. Басиц Lоцал Алигнмент Сеарцх Тоол) је алгоритам за упоређивање примарних биолошких секвенци, као што су аминокиселине различитих протеина или нуклеотиди ДНК секвенци. БЛАСТ претрага омогућава истраживачима да пореде низ секвенци са библиотекама или базама података секвенци, и идентификују библиотеку секвенци која одговара траженој, са одређеном грешком.

БЛАСТ

Програмер(и)	Алтсцхул СФ, Гисх W, Миллер W, Мyерс ЕW, Липман ДЈ, НЦБИ
Најновија верзија	2.5.0+ 12. септембар 2016. (2016-09-12)
Платформа	УНИX, Линуx, Мац, Мицрософт Wиндоwс
Тип	Биоинформатика
Лиценца	Јавно власништво
Веб-сајт	blast.ncbi.nlm.nih.gov/Blast.cgi

Различите врсте БЛАСТ-а су доступне у зависности од врсте секвенце која се претражује. На пример, након открића претходно непознатог гена код мишева, научник ће обично применити БЛАСТ претрагу људских генома да провери да ли људи садрже сличне гене; БЛАСТ ће препознати секвенце у људском геному који су налик мишјем заснованом на сличности секвенци. БЛАСТ алгоритам и програм су дизајнирани од стране Степхен Алтсцхул, Wаррен Гисх, Wебб Миллер, Еугене Мyерс, и Давид Ј. Липман у Националном институту за здравље и објављен је у Јоурнал оф Молецулар Биологy 1990. и цитиран више од 50,000 пута.

Позадина

БЛАСТ је један од најчешће коршћених програма у биоинформатици за претрагу секвенци. Он представља фундаментални проблем у биоинформатици. Хеуристички алгоритам који користи је много бржи него други приступи, као што је рачунање оптималног поравнања. Нагласак на брзини је кључан аспекат алгоритма, посебно на великим тренутно доступним базама генома, иако новији алгоритми могу бити још бржи.

Пре БЛАСТ-а, ФАСТА је креиран од стране Давид Ј. Липман и Wиллиам Р. Пеарсон 1985.

Пре брзих алгоритама као што су БЛАСТ и ФАСТА, претрага протеина и нуклеинских секвенци је била веома временски захтевна јер је коришћен потпун поступак поравнања(нпр., тхе Смитх–Wатерман алгоритам).

Иако је БЛАСТ бржи од свих Смитх-Wатерман имплементација за већину случајева, он ипак не може да "гарантује оптимално поравнање упита са базом секвенци" као Смитх-Wатерман алгоритам. Оптималност Смитх-Wатерман алгоритма "обезбеђује највећу тачност и најпрецизније резултате" по цену времена и ресурса рачунара.

БЛАСТ је временски ефикаснији од ФАСТА јер претражује само значајније узораке у секвенци, али са одређеном осетљивошћу.

Примери употребе БЛАСТ-а:

• Које врсте бактерија имају протеин који је у вези са одређеним протеином који има познату аминокиселину?
• Који још гени представљају протеине који имају структуру сличну онима који су већ откривени?

БЛАСТ је често коришћен као део других алгоритама који захтевају приближно поклапање секвенци.

Улаз

Улаз представљају секвенце (у ФАСТА формату или Генбанк формату) и тежинска матрица.

Излаз

Излаз БЛАСТ алгоритма може бити представљен на различите начине. Ови формати могу бити ХТМЛ, текст и XМЛ. За НЦБИ wеб страницу, подразумевани формат излаза је ХТМЛ. Када се изврши БЛАСТ алгоритам на НЦБИ сајту, резултати су дати у графичком облику и приказују поготке, табеле приказују идентификаторе секвенци за поготке заједно са пратећим подацима, као и поравнање секвенци од интереса и поготке добијене коришћењем одговарајућег БЛАСТ вредносног система. Најједноставније за читање и најинформативније су табеле.

Ако неко жели да пронађе секвенцу које нема у базама доступних јавности путем извора попут НЦБИ сајта, БЛАСТ алгоритам је могуће бесплатно преузети са интернета. Може се преузети са НЦБИ сајта. Доступни су и комерцијални програми који се могу купити. Базе се могу наћи на НЦБИ сајту, као и на индексу БЛАСТ база података.

Процес

Коришћењем хеуристичких метода, БЛАСТ налази сличне секвенце, лоцирањем кратких поклапања између две секвенце. Овај процес проналажења се назива сејање (енг. сеединг). Након првог поклапања БЛАСТ почиње да прави локална поравнања. Док покушава да нађе сличност у секвенци, скуп честих слова, познат као реч, је веома важан. На пример, претпоставимо да секвенца садржи следећи низ слова: ГЛКФА. Ако се БЛАСТ покрене под нормалним условима, дужина речи би била 3 слова. У овом случају, коришћењем датог низа слова, добијене речи би биле ГЛК, ЛКФ, КФА. БЛАСТ-ов хеуристички алгоритам лоцира све честе појаве трословних речи између задате и пронађене секвенце. Овај резултат се затим користи за прављење поравнања. Након што је направио речи за посматрану секвенцу, остале речи су такође обрађене. Ове речи морају да имају задовољен праг Т, у поређењу са матрицом вредности. Често коришћена матрица вредности за БЛАСТ претраге је БЛОСУМ62, иако оптимална матрица вредности зависи од сличности секвенци. Када су речи, као и околне речи, процесуиране оне се пореде са секвенцама из базе у циљу проналаска поклапања. Праг Т одређује да ли конкретна реч улази у поравнање. Када је сејање извршено, поравнање које је само дужнине 3, је проширено у оба смера помоћу БЛАСТ алгоритма. Свако проширење утиче на резултат поравнања било повећањем било смањењем. Ако је резултат већи од унапред одређеног Т, поравнање ће бити укључено у резултат БЛАСТ-а. Међутим, ако је резултат мањи од унапред одређеног Т, поравнање ће престати да се шири, спречавајући да се сегменти са лошим поравнањем укључе у резултат БЛАСТ-а. Приметимо да повећањем Т ограничавамо простор који можемо да претражујемо, смањујемо број суседних речи, док у исто време убрзавамо БЛАСТ.

Алгоритам

За покретање програма, БЛАСТ захтева унос секвенце за претрагу, и секвенце са којом ће упоређивати (такође се назива и “циљана секвенца”) или базе која садржи више секвенци. БЛАСТ ће наћи више подсеквенци у бази које су сличне подсеквенци упита. Обично, упитна секвенца је доста мања од базе, нпр., упит може садржати хиљаду нуклеотида, док база садржи неколико милијарди нуклеотида.

Главна идеја БЛАСТ-а је да често постоји високо рангирани сегментни парови (Хигх-сцоринг Сегмент Паирс (ХСП)) садржани у статистички битном поравнању. БЛАСТ тражи високо рангирана поравнања секвенци између упитне и посматране секвенце из базе, користећи хеуристички приступ који апроксимира Смитх-Wатерман алгоритам. Међутим, исцрпни Смитх-Wатерман приступ је сувише спор за претраживање великих база генома, као што је ГенБанк. Стога, БЛАСТ алгоритам користи хеуристички приступ који је мање прецизан од Смитх-Wатерман алгоритма, али преко 50 пута бржи. Брзина и релативно добра прецизност БЛАСТ-а су међу кључним техничким иновацијама БЛАСТ програма.

Преглед БЛАСТ алгоритма (протеин-протеин претрага): ^{анд ЦТГА2016}

1. Брисање некомплексних региона или понављање секвенци из упита.

   "Некомплексни регион" представља регион секвенци састављен од неколико врсти елемената. Ови региони могу да онемогуће програм да нађе битну секвенцу у бази, па би их требало исфилтрирати. Ти региони ће бити обележени са X(протеинске секвенце) или Н (нуклеинске киселине) и биће игнорисане од стране БЛАСТ програма. За филтрирање некомплексних региона, за протеинске секвенце се користи програм СЕГ, а за ДНК секвенце програм ДУСТ.

2. Прављење к-словне листе речи од упитне секвенце.

   Узмимо к=3 као пример. Излиставамо речи дужине 3 из упитне протеинске секвенце (к је обично 11 за ДНК секвенцу) "секвенцијално", док сва слова упитне секвенце не буду укључена. Метод је приказан на слици 1.

   

   Слика1 Метода за прављење "к"-словне листе упитних речи

3. Листа могућих речи које се поклапају.

   Овај корак је једна од главних разлика између БЛАСТ-а и ФАСТА. ФАСТА користи све честе речи нађене у кораку 2; међутим, БЛАСТ користи једино високовредноване речи. Вредности су креиране упоређивањем речи добијених у кораку 2 са свим преосталим речима. Коришћењем матрице вредности и поређењем свих парова, постоји 20³ могућих вредности за трословне речи. На пример, вредност добијена поређењем ПQГ са ПЕГ и ПQА је 15 и 12, редом. За ДНК речи, погодак се рачуна као +5, а промашај као -4, или као +2 и -3. Након тога, вредност прага суседних речи Т се користи да смањи број могућих речи које се поклапају. Речи чије су вредности веће од прага Т ће остати на листи тих речи, док ће речи чија је вредност мања од овог прага бити одбачене. На пример, ПЕГ се чува, али ПQА је одбачен када је Т = 13.

4. Организација високо рангираних речи у ефикасно стабло претраге.

   Ово омогућава програму да брзо пореди високо рангиране речи са онима из базе.

5. Понављање корака 3 - 4 за сваку к-словну реч из упитне секвенце.
6. Претрага базе ради проналажења егзактног поклапања са преосталим високо рангираним речима.

   БЛАСТ програм претражује базу по преосталим високо рангираним речима, као што је ПЕГ, по свакој позицији. Ако се пронађе егзактно поклапање, оно се користи за сејање могућих поравнања без одступања између упитне секвенце и секвенце из базе.

7. Проширивање егзактног поклапања у високо рангирани сегментни пар (ХСП).
   • Оригинална верзија БЛАСТ-а прави дугачко поравнање између упита и секвенци из базе у оба смера од позиције где је пронађено егзактно поклапање. Проширење не престаје све док нагомилана вредност ХСП-а не почне да опада.

     

     Слика2 Позиција егзактних погодака

   • Ради уштеде времена, новија верзија БЛАСТ-а, звана БЛАСТ2, је развијена. БЛАСТ2 присваја ниже рангиране суседне речи да би очувао исти ниво осетљивости за откривање сличних секвенци. Стога, листа могућих поклапања из корака 3 постаје дужа. Даље, региони код којих је дошло до егзактног поклапања, који су на међусобном растојању А на истој дијагонали на слици 2, биће спојени у један дугачак нови регион. Коначно, нови региони су проширени на исти начин као у оригиналној верзији БЛАСТ-а.
8. Листа свих ХСП у бази чија је вредност довољно велика да буду узети у обзир.

   Листамо ХСП вредности које су веће од емпиријски утврђених граница вредности С. Проучавањем дистрибуције вредности поравнања добијене поређењем случајних секвенци гранична вредност С може бити утврђена тако да њена вредност буде довољно велика да гарантује значајан остатак ХСП-а.

9. Процена значајности ХСП вредности.

   БЛАСТ даље приступа статистичком значењу сваке ХСП вредности коришћењем Гумбелове дистрибуције екстремних вредности (ЕВД). У поређењу са Гумбел ЕВД, вероватноћа п за достизање С, која је већа или једнака од x, дата је следећом једначином:

   $p\left(S\geq x\right)=1-\exp \left(-e^{-\lambda \left(x-\mu \right)}\right)$

   где је

   $\mu ={}^{\left[\log \left(Km'n'\right)\right]}\!\!\diagup \!\!{}_{\lambda }\;$

   Статистички параметри$\lambda$ и $\mathrm {K}$ се процењују на основу вредности поравнања без рупа. Приметимо да $\lambda$ и $\mathrm {K}$ зависе од матрице замене и композиције секвенце. $m'$ и $n'$ су ефективне дужине уноса и секвенце из базе, редом. Дужина секвенце је скраћена на ефективну дужину да би компензовала ефекат ивице. Могу се израчунати као:

   $m'\approx m-{}^{\left(\ln Kmn\right)}\!\!\diagup \!\!{}_{H}\;$

   $n'\approx n-{}^{\left(\ln Kmn\right)}\!\!\diagup \!\!{}_{H}\;$

   где је $\mathrm {H}$ очекивана просечна вредност по поравнатом пару у поравнању две случајне секвенце. Алтсцхул и Гисх дали су уобичајене вредности, $\lambda =0.318$, $\mathrm {K} =0.13$, и $\mathrm {H} =0.40$, за локално поравнање без рупа, коришћењем БЛОСУМ62 као матрице замене. Коришћење типичних вредности за додељивање значајности се зове лоокуп-табле метод, и он није прецизан. Очекивана вредност Е је број колико пута ће неповезана секвенца из базе добити вредност С већу од x по вероватноћи. Очекивано Е, које је добијено у претрази базе од D секвенци, дато је са

   $E\approx 1-e^{-p\left(s>x\right)D}$

   Шта више, када $p<0.1$, Е може бити апроксимирано помоћу тхе Поиссон дистрибуције као

   $E\approx pD$

   Очекивана вредност Е додељује значај ХСП вредностима за локално поравнање без рупа, и то се представља као резултат БЛАСТ-а. Израчунавања приказана овде се модификују ако се појединачни ХСП комбинују као да представљају рупичасто поравнање, због варијације статистичких параметара.

10. Спајање два или више ХСП региона у дуже поравнање.

    Понекад нађемо два или више ХСП региона у једној секвенци из базе, који се могу спојити у дуже поравнање. Ово обезбеђује додатну евиденцију о релацијама између упита и секвенце из базе. Постоје два метода: тхе Поиссон метод и сум-оф-сцорес метод, за поређење значајности новодобијених ХСП региона. Претпоставимо да постоје два комбинована ХСП региона са вредностима (65, 40) и (52, 45), редом. Тхе Поиссон метод придаје већи значај скупу са максималном нижом вредношћу (45>40). Међутим, тхе сум-оф-сцорес метод придаје већи значај првом скупу, зато што је 65+40 (105) веће од 52+45(97). Оригинални БЛАСТ користи тхе Поиссон метод; БЛАСТ2 и WУ-БЛАСТ котисте тхе сум-оф сцорес метод.

11. Приказ гаппед Смитх-Wатерман локалног поравнања у упиту и упарених секвенци из базе.
    • Оригинални БЛАСТ генерише само цела поравнања укључујући иницијално успостављене ХСП, чак и ако има више од једног ХСП-а у секвенци из базе.
    • БЛАСТ2 користи једноструко рупичасто поравнање које укључује све иницијално пронађене ХСП регионе.
12. Пријава сваког поготка чија је очекивана вредност мања од параметра Е.

Паралелни БЛАСТ

Верзија паралелног БЛАСТ-а која користи раздвојене базе је имплементирана коришћењем МПИ и Птхреадс, и прилагођена је различитим платформама, укључијући и Wиндоwс, Линуx, Соларис, Мац ОС X и АИX. Популарни приступ паралелизације БЛАСТ-а укључује дистрибуиране упите, сегментацију хеш табела, паралелно рачунање и сегментацију база. Базе су подељене на једнаке делове и чувају се на локалним чворовима. Сваки упит је покренут на свим чворовима паралелно и излазни фајлови су спојени у финални излаз.

Програм

БЛАСТ програм може бити, или преузет, или покренут из командне линије, или се може користити бесплатно онлајн. БЛАСТ-ов wеб сервер, одржаван од стране НЦБИ, дозвољава свакоме са wеб претраживачем да извршава сличне претраге на константно ажурираној бази протеина и ДНК, која укључује већину организама.

БЛАСТ програм је отвореног кода, што даје свима могућност да га користе и мењају. Ово је довело до настанка више варијанти БЛАСТ програма.

Данас су доступне различите корисне варијације БЛАСТ-а, које могу бити коришћене у зависности од онога шта желимо да урадимо и са чиме радимо. Ове варијације програма су различите по питању упитних секвенци, базе која се претражује и шта се упоређује. Ови програми и њихови описи су излистани испод:

БЛАСТ је заправо фамилија програма (све су укључене у бласталл извршавање). Ово укључује:

Нуклеотид-нуклеотид БЛАСТ (бластн)

Овај програм, коме се задаје ДНК упит, враћа најсличнију ДНК секвенцу из базе коју је корисник одабрао.

Протеин-протеин БЛАСТ (бластп)

Овај програм, коме се задаје протеински упит, враћа најсличнију протеинску секвенцу из базе коју је корисник одабрао.

Поситион-Специфиц Итеративе БЛАСТ (ПСИ-БЛАСТ) (бластпгп)

Овај програм се користи за проналажење даљих рођака протеина. Прво се креира листа свих блиско повезаних протеина. Ови протеини се комбинују у општу “профил" секвенцу, која сумира значајне особине присутне у тим секвенцама. Упит на бази протеина користи тај профил, и проналази се већа група протеина. Ова већа група се користи за прављење новог профила и процес се понавља.

Укључивањем повезаних протеина у претрагу, ПСИ-БЛАСТ је осетљивији у избору рођака из филогенетског стабла од обичног протеин-протеин БЛАСТ-а.

Нуцлеотиде 6-фраме транслатион-протеин (бластx)

Овај програм пореди шест фрејмова концептуалном транслацијом нуклеотида упитне секвенце са протеином из базе.

Нуцлеотиде 6-фраме транслатион-нуцлеотиде 6-фраме транслатион (тбластx)

Овај програм је најспорији из БЛАСТ фамиије. Он транслира упитну секвенцу нуклеотида у свих шест могућих фрејмова и пореди их са шест фрејмова транслацијом нуклеотида упитне секвенце са протеином из базе. Сврха овога је да нађе веома далеке везе између секвенци нуклеотида.

Протеин-нуцлеотиде 6-фраме транслатион (тбластн)

Овај програм пореди упит са свих шест фрејмова са секвенцом нуклеотида из базе.

Велики број упитних секвенци (мегабласт)

При упоређивању великог броја улазних секвенци путем БЛАСТ-а командне линије, "мегабласт" је много бржи од вишеструког покретања БЛАСТ-а. Он врши конкатенацију више улаза како би формирао велику секвенцу пре претраге, а затим се накнадном анализом добијају коначни резултати.

Алтернативне верзије

Верзија дизајнирана за упоређивање великих генома или ДНК је БЛАСТЗ.

ЦС-БЛАСТ (ЦонтСxт-Специфиц БЛАСТ) је проширена верзија БЛАСТ-а за претрагу протеинских секвенци која проналази двоструко више далеко повезаних секвенци од БЛАСТ-а за исто време и са истом стопом грешке. У ЦС-БЛАСТ-а, вероватноћа мутације између аминокиселина не зависи само од једне аминокиселине као у БЛАСТ-у, већ и од контекста локалне секвенце. Вашингтон Универзитет направио је алтернативну верзију НЦБИ БЛАСТ-а, звану WУ-БЛАСТ. Ауторска права припадају Адванцед Биоцомпутинг, ЛЛЦ.

2009. НЦБИ је објавио нову серију БЛАСТ извршних програма, C++ засновани БЛАСТ+,, и објавио је паралелну верзију до 2.2.26. Почевши са верзијом 2.2.27 (Април 2013), само БЛАСТ+ извршни програми су доступни. Међу изменама је и замена blastall команде за више различитих команди за различите БЛАСТ програме, и промене у руковању опцијама.

Алтернативе БЛАСТ-а

Екстремно брза, али знатно мање осетљива, алтернатива БЛАСТ-у је БЛАТ (енг. Бласт Lике Алигнмент Тоол). Док БЛАСТ врши линеарну претрагу, БЛАТ се ослања на к-мер индексирање базе, и на тај начин често може брже да пронађе семе. Још један програм сличан БЛАТ-у је ПаттернХунтер.

Напретком технологија секвенционирања касних 2000-тих, проналажење веома сличних нуклеотида постаје важан проблем. Нови програми поравнања скројени за ову специфичну употребу користе БWТ-индексирање циљане базе (обично генома). Улазна секвенца може бити мапирана врло брзо, а излаз је обично у виду БАМ фајла. Примери програма поравнања су БWА, СОАП и Боwтие.

За идентификацију протеина, тражење познатих домена (нпр. Пфам) повезивањем са Хидден Марков Моделс је популарна алтернатива, као што је нпр. ХММЕР.

Алтернатива БЛАСТ-у за поређење две банке секвенци је КЛАСТ. Резултати КЛАСТ-а су веома слични резултатиима БЛАСТ-а, али КЛАСТ је значајно бржи и способнији да пореди велике скупове секвенци са малим утрошком меморије.

Примена БЛАСТ

БЛАСТ се може користити у више сврха. Ово укључује идентификацију врсти, лоцирање домена, успостављање филогеније, ДНК мапирање и поређење.

Идентификација врсти

Коришћењем БЛАСТ-а, могуће је тачно идентификовати врсту или наћи одговарајућу врсту. Ово може бити корисно, на пример, за рад са ДНК секвенцама непознатих врсти.

Лоцирање домена

Протеинске секвенце је могуће проследити као улаз БЛАСТ-у да би се лоцирали познати домени те секвенце.

Успостављање филогеније

Коришћењем резултата БЛАСТ-а могуће је креирати филогенетско стабло коришћењем БЛАСТ wеб-стране. Филогенија заснована само на БЛАСТ-у је мање поуздана него друге, за ту сврху направљене, филогенетске методе, тако да би требало да буде коришћена само као први продукт анализе.

ДНК мапирање

При раду са познатим врстама и тражења секвенци гена на непознатој локацијии, БЛАСТ може поредити хромозомске позиције хромозомске позиције.

Поређење

При раду са генима, БЛАСТ може да лоцира честе гене у две повезане врсте, и може да се користи за мапирање разлика између организама.

Поређење БЛАСТ-а и Смитх-Wатерман процеса

Док се и Смитх-Wатерман и БЛАСТ користе за проналажење одговараћујих секвенци претрагом и поређење упитне секвенце са оним из база, они имају разлике.

Иако је БЛАСТ заснован на хеуристичком алгоритму, резултати добијени употребом БЛАСТ-а, у терминима броја пронађених погодака, можда неће дати најбоље резултате, јер неће пронаћи сва подударања са базом.

Боља алтернатива за проналажење најбољег могућег решења била би коришћење Смитх-Wатерман алгоритма. Овај метод се разликује од БЛАСТ-а у две области, прецизности и брзни. Тхе Смитх-Wатерман обезбеђује већу прецизност, јер проналази подударања која БЛАСТ не може, јер не прескаче ниједну информацију. Међутим, у поређењу са БЛАСТ-ом, троши више времена и захтева већу количину компјутерских ресурса. Пронађене су технологије које могу знатно да убрзају Смитх-Wатерман процес. Те технологије укључују ФПГА чипове и СИМД тецхнологију.

За добијање бољих резултата БЛАСТ-а, подразумевана подешавања се могу променити. Не постоји сигуран начин за мењање подешавања како би се обезбедио најбољи резултат за дату секвенцу.

Види још

• Нидлмен-Ваншов алгоритам
• Смит-Ватерманов алгоритам
• Поравнавање секвенци

Литература

• Моунт, D. W. (2004). Биоинформатицс: Сеqуенце анд Геноме Аналyсис (2нд изд.). Цолд Спринг Харбор Пресс. ИСБН 978-0-87969-712-9. 
• Баxеванис, Андy (2005). „Цхаптер 11: Ассессинг Паирwисе Сеqуенце Симиларитy: БЛАСТ анд ФАСТА”. Биоинформатицс: А Працтицал Гуиде то тхе Аналyсис оф Генес анд Протеинс, Тхирд Едитион. Неw Yорк: Јохн Wилеy & Сонс. 
• Wхеелер, Давид; Бхагwат, Медха (2007). „Цхаптер 9: БЛАСТ QуицкСтарт”. Ур.: Бергман, Ницхолас Х. Цомпаративе Геномицс Волумес 1 анд 2. Метходс ин Молецулар Биологy. 395-396. Тотоwа, Њ: Хумана Пресс. ПМИД 21250292. 
• Моунт, ДW (1. 7. 2007). „Усинг тхе Басиц Лоцал Алигнмент Сеарцх Тоол (БЛАСТ)”. Цолд Спринг Харбор Протоцолс. 2007 (14): пдб.топ17. ПМИД 21357135. дои:10.1101/пдб.топ17. 

Спољашње везе

• Званични веб-сајт
• BLAST+ executables — фрее соурце доwнлоадс
• Biological Sequence Analysis I: Андy Баxеванис' лецтуре фром НХГРИ'с Цуррент Топицс ин Геноме Аналyсис сериес, цоверинг цонтемпорарy ареас ин геномицс анд биоинформатицс
• What's behind BLAST?: talk by Gene Myers (slides and video)