بلاست

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
نتیجه یک جستجو با بلاست و امتیازات تطبیق رشته‌های قیاس شده

بلاست (به انگلیسی: BLAST) نام یک نرم‌افزار کاربردی در علوم سلولی و مولکولی و ژنتیک است که مخفف واژگان Basic Local Alignment Search Tool یا ابزار پایه‌ای برای جستجوی برهمنهی‌های موضعی است.[۱] این ابزار قسمتی از مجموعهٔ اطلاعات کیفی مرکز ملی اطلاعات زیست‌فناوری است.[۲]

با این نرم‌افزار می‌توان توالی اسیدهای آمینه در پروتئین‌ها یا توالی نوکلئوتیدها را در DNA را با هم مقایسه کرد. این نرم‌افزار به پژوهشگر اجازه می‌دهد تا یک توالی را با توالی دیگر یا توالی که در بانک اطلاعاتی وجود دارد، مقایسه کند. شناسایی توالی‌های موجود در بانک اطلاعاتی که بیشترین شباهت را با توالی مورد نظر دارد از دیگر قابلیت‌های این نرم‌افزار است. بر حسب نوع توالی انواع مختلفی از بلاست امکان پذیر است. مثلاً اگر یک ژن ناشناخته در موش که قبلاً اطلاعاتی از آن در اختیار نبوده، باید بررسی شود، یک پژوهشگر ترجیح می‌دهد این توالی را با ژنوم انسان بلاست کند. این نرم‌افزار در NIH (موسسه ملی بهداشت آمریکا) طراحی شد. بلاست یکی از برکاربردترین نرم‌افزارها در بیوانفورماتیک است که با سرعت مطلوب مقایسه مورد نظر را انجام می‌دهد. سرعت زمانی اهمیت خود را نشان می‌دهد که با ژنوم کامل روبرو باشیم. پیش از طراحی این نرم‌افزار مقایسه توالی‌ها بسیار وقت گیر بود.

پیشینه[ویرایش]

به دلیل اینکه بلست مربوط به یکی از بنیادیترین مسائل بیوانفورماتیک است و سرعت خوبی دارد یکی از پر کاربردترین نرم اقزارهای بیوانفورماتیک به حساب می آید. سرعت، مخصوصا در کاربردهای واقعی روی پایگاههای داده ی بزرگ ژنوم امری حیاتی است.

پیش از ارائه الگوریتمهای سریعی مثل BLAST و FASTA جستجو در پایگاههای داده ی بزرگ برای دنباله های پروتئین یا نوکلئیک با استفاده از الگوریتمهای انطباق کامل مثل Smith-Waterman بسیار زمانگیر بود. BLAST از نظر زمانی کارآمد تر از FASTA است زیرا الگوهای مهمتر در دنباله را مورد جستجو قرار میدهد.

از BLAST در موارد زیر استفاده میشود:

  • کدام گونه باکتریها پروتئینی دارند که از نظر اصل و نسب به پروتئینی با آمینواسید شناخته شده مرتبط باشد؟
  • دنباله ی معلومی از DNA ها از کجا سرچشمه گرفته اند؟
  • کدام ژنهای دیگر پروتئینهایی را به وجود می آورند که ساختارشان با ساختارهایی که قبلاً مشخص شده است یکی باشد؟

الگوریتم بلاست و برنامه ی کامپیوتری آن توسط Stephen Altschul، Warren Gish و David Lipman در موسسه ملی اطلاعات بیوتکنولوژی آمریکا(NCBI) (شاخه ای از NIH)و Web Myers در ایالت پنسیلوانیا و Gen Myers در دانشگاه Arizona پیاده سازی شد.

ورودی[ویرایش]

دنباله های ورودی در فرمت FASTA format یا Genbank هستند.

خروجی[ویرایش]

خروجی بلاست در فرمتهای مختلفی موجود است: فرمت HTML، متن و XML. در نرم‌افزار موجود در سایت NCBI فرمت پیشفرض خروجی HTML است. در این نرم‌افزار موفقیتها (مواردی که تطابق رخ داده) به صورت گرافیکی نمایش داده میشوند بعلاوه ی یک جدول که دنباله ی تطابقها همراه با امتیاز داده شده به هرکدام را نشان میدهد.

همچنین یک نسخه ی رایگان بلاست قبل اجرا بر روی کامپیوتر شخصی از آدرس BLAST + Exe قبل دانلود است. پایگاه داده نیز از سایت NCBI و هم چنین از آدرس پایگاه داده بلاست قابل دانلود است.

نحوه پردازش[ویرایش]

با استفاده از روش Heuristic الگوریتم بلاست دنباله های همسان را پیدا میکند. در این روش به جای مقایسه کامل دو دنباله، تطابقهای کوتاه با یکدیگر مقایسه میشوند. به پروسه ی پیدا کردن کلمات اولیه برای اجرای الگوریتم بلاست seeding میگویند. بعد از پیدا کردن این تطابق های اولیه الگوریتم بلاست یک تطابق محلی (local alignment) انجام میدهد. هنگام پیدا کردن هومولوگ در دنباله ها، مجموعه حروف مشترک که به آنها لغت گفته میشود بسیار مهم اند. به عنوان مثال اگر دنباله ای شامل حروف GLKFA باشد؛ اگر BLASTp با تنظیمات پیشفرض اجرا شود، طول لغت 3 خواهد بود( word size = 3).در این حالت لغاتی که جستجو خواهند شد لغات روبه رو هستند: GLK, LKF, KFA. الگوریتم اکتشافی (heuristic) بلاست، حروف سه تایی مشترک را بین دنباله ی مورد نظر و دنباله ی تطابق یا دنباله های پایگاه داده مکان یابی میکند. سپس از این نتایج برای ساخت یک تطابق استفاده میشو. بعد از ساخت لغات برای دنباله ی مورد نظر، لغات موجود در همسایگی نیز ساخته میشوند. این لغات باید در پروسه ی امتیاز دهی، امتیازشان از یک حد آستانه ای بیشتر شده باشد. و معمولاً برای این امتیاز دهی از ماتریس BLOSUM62 استفاده میشود. بعد از ساخت لغات و برای پیدا کردن تطابق لفات ساخته شده با دنباله های موجود در پایگاه داده مقایسه میشوند. حد آستانه مشخص میکند که لغت مورد نظر در تطابق نهایی باشد یا نباشد. بعد از انجام پروسه ی seeding (پیدا کردن تطابق اولیه)، تطابق یافته شده ی اولیه که در این مثال طول آن سه بود در دو جهت گسترش می یابد و با هر گسترش امتیاز جدیدی به تطابق داده میشود و اگر این امتیاز از مقداری از قبل تعیین شده بیشتر بود تطابق پذیرفته میشود و در غیر اینصورت از گسترش تطابق خودداری میشود. افزایش مقدار از قبل تعیین شده، فضای جستجو را محدود میکند و تعداد لغات همسایگی را کاهش میدهد اما سرعت اجرای الگوریتم بلاست را افزایش میدهد.

الگوریتم[ویرایش]

برای اجرای بلاست نیاز به دو دنباله می باشد یکی دنباله ی درخواستی یا مورد نظر و دیگری دنباله ی هدف یا دنباله های موجود در پایگاه داده ای از دنباله ها. بلاست زیر دنباله هایی از پایگاه داده را پیدا میکند که شبیه دنباله ی ورودی (query) باشند. معمولاً دنباله ی query بسیار کوچکتر از پایگاه داده است. به عنوان مثال query ممکن است هزار نوکلئوتیدی باشد در حالی که پایگاه داده از چندین بیلیون نوکلئوتید تشکیل شده باشد. ایده ی اصلی الگوریتم بلاست این است که به دنبال تطابقهای با بیشترین امتیاز بین query و پایگاه داده میگردد بر اساس تقریب زدن یک الگوریتم اکتشافی به اسم Smith-Waterman_algorithm. الگوریتم Smith-Waterman بسیار زمانگیر است از اینرو در بلاست از یک روش اکتشافی (heuristic) که البته دقت کمتری خواهد داشت استفاده میشود. اما در عوض 50 بار سریعتر است. در زیر مراحل الگوریتم بلاست (پروتئین به پروتئین) به صورت خلاصه آورده شده است:

  1. حذف قسمتهای تکراری از دنباله ی query (قسمتهای با پیچیدگی کم): قسمتهای با پیچیدگی کم قسمتهایی در دنباله هستند که عناصرشان تنوع کمی دارند.
  2. ساخت یک لیست k حرفی از دنباله query:

Query word.jpg

  1. لیست کردن تطابقهای ممکن:

این مرحله یکی از تفاوتهای اساسی بین بلاست و FASTA است.برای FASTA تمام لغات مشترک در پایگاه داده ودنباله های کوئری ای که در مرحله ی دوم لیست شدند مهم است، اما برای بلاست فقط لغات با امتیاز بالا اهمیت دارند.

  1. سازماندهی لغات باقی‌مانده (لغات با امتیاز بیشتر از حد آستانه) و تبدیل آن به یک درخت جستجوی بهینه:

Neighbor HSP.jpg هدف این قسمت این است که برنامه بتواند سریعتر لغات با امتیاز بالا را با دنباله های پایگاه داده مقایسه کند.

  1. تکرار مراحل 3 و 4 به ازای هر لغت k-حرفی در دنباله query.
  2. جستجو در پایگاه داده برای پیدا کردن تطابق دقیق بین دنباله های باقی‌مانده و دنباله های پایگاه داده:
  3. گسترش تطابقهای دقیق به HSP (جفت دنباله های با امتیاز تطابق بالاتر از حد آستانه)

Extension process.jpg

  1. بررسی معناداری امتیاز داده شده به HSP ها.

در این مرحله، بلاست میزان معناداری آماری امتیاز داده شده به هر HSP را با استفاده از Gumbel extreme value distribution (EVD) بررسی میکند. بر طبق Gumbel EVD احتمال اینکه با احتمال p امتیاز مشاهده شود مثل S که بزرگتر یا مساوی x باشد برابر است با:

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

به طوریکه:

\mu ={}^{\left[ \log \left( Km'n' \right) \right]}\!\!\diagup\!\!{}_{\lambda }\;
  1. ادغام HSP ها و تبدیل آنها به تطابقهای بزرگتر
  2. نمایش تطابق محلی دنباله query با پایگاه داده با استفاده از الگوریتم gapped Smith-Waterman.
  3. انتخاب تطابقهایی که مقدار مورد انتظار امتیاز آنها کمتر از حد آستانه ی E شده باشد.

بلاست موازی[ویرایش]

نسخه های موازی از بلاست با استفاده از MPI و Pthreads پیاده سازی شده اند و روی پلتفرم های مختلف مثل ویندوز، لینوکس، مک و... قابل اجرا هستند. روشهای مشهور برای موازی سازی بلاست عبارتند از پراکنده یا پخش کردن query، قطعه قطعه سازی جدول hash، موازی سازی محاسباتی و قطعه قطعه سازی پایگاه داده.

برنامه[ویرایش]

بلاست هم میتواند دانلود شده و به صورت command-line اجرا شود (برنامه blastall)و هم اینکه بدون دانلود روی وب اجرا شود. بلاست یک برنامه متن باز است و هرکس میتواند در کد تغییرات مورد نظر خود را اجرا کند و این خود علت وجود نسخه های مختلف از بلاست می باشد. بلاست مجموعه ای از برنامه های مختلف است که همگی در فایل اجرایی blastall قابل دسترسی است. ایم مجموعه ها شامل:

  • نوکلئوتید-نوکلئوتید بلاست (blastn)
  • پروتئین-پروتئین بلاست (blastp)
  • بلاست تکرار شونده ی وابسته به مکان (position-specific iterative blast)

در این روش ابتدا یک پروفایل عمومی ساخته میشود. سپس با استفاده از این پروفایل گروههای بیشتری از پروتئینها به دست می آیند که خود انها نیز تشکیل یک پروفایل جدید میدهند و این کار تکرار میشود.

  • Nucleotide 6-frame translation-protein

این برنامه به صورت 6-فریم 6-فریم ترجمه ی دنباله ی query را با دنباله پروتئین مقایسه میکند.

  • Nucleotide 6-frame translation-nucleotide 6-frame translation (tblastx)

این برنامه مانند قبلی است با این تفاوت که هر دو را ترجمه میکند و ترجمه ها را با هم مقایسه میکند.

  • Protein-nucleotide 6-frame translation (tblastn)

این برنامه query پروتئین را با ترجمه نوکلئوتید مقایسه میکند.

  • Large numbers of query sequences (megablast)

این برنامه هنگام مقایسه ی دنباله های بزرگ استفاده میشود.

نسخه های جایگزین[ویرایش]

یکی از نسخه های بلاست که خیلی سریع تر است اما دقت کمتری دارد BLAT است. نسخه ی دیگری که برای مقایسه ی ژنوم ها و کروموزوم های خیلی بزرگ استفاده می شود BLASTZ نام دارد. CS-BLAST (context-specific BLAST) نیز یک نسخه ی توسعه یافته ی بلاست برای جستجو در پروتوین هاست که دو برابر سریعتر از بلاست است. در این نسخه احتمال جهش بین آمینواسیدها نه تنها به خودشان بلکه به مکان آنها نیز وابسته است.

نسخه های سریعتر[ویرایش]

  • دو پیاده سازی اصلی در این رده progeniq و Tera-BLAST هستند که به عنوان مثال progeniq صد برابر سریعتر از بلاست معمولی است.
  • Mitrion-C Open نیز نسخه ی دیگری است که از لینک http://mitc-openbio.sourceforge.net/ قابل دسترسی است.
  • نسخه ی دیگری از بلاست که GPU-based است از CUDA-BLASTP قابل دسترسی است که ده برابر سریعتر از NCBI BLAST است.

کاربردهای بلاست[ویرایش]

از بلاست میتوان در مواردی مثل موارد زیر استفاده نمود:

  • تعیین نوع

با استفاده از بلاست میتوان هومولوگهای یک نوع را پیدا کرد.

  • قرار دادن دامنه ها

هنگام کار با پروتئینها میتوان آنها را به عنوان وروردی به بلاست داد تا دامنه های شناخته شده از دنباله ی مورد نظر را پیدا کند.

با استفاده از نتایج به دست آمده از بلاست میتوان درهت فیلوژنتیک را رسم کرد.

  • نگاشت DNA

هنگام جستجو به دنبال دنیاله ای از ژنها در مکانی ناشناخته روی یک گونه ی شناخته شده، بلاست میتواند مکانهای کروموزومی در دنباله های مورد نظر مقایسه کند.

  • مقایسه

هنگام کار کردن با ژن ها بلاست میتواند ژن های مشترک در دو گونه ی متفاوت را شناسایی کند.

مقایسه ی BLAST و Smith-Waterman[ویرایش]

اگرچه blast و Smith-Waterman هردو برای یافتن هومولوگ ها استفاده میشوند اما تفاوتهایی نیز با یکدیگر دارند. بلاست به خاطر اینکه یک الگوریتم اکتشافی (heuristic) است دقت کم تری دارد و ممکن است بعضی از تطابق ها را پیدا نکند و از دست بدهد اما در عوض سرعت خوبی دارد. در مقابل Smith-Waterman دقت مناسبی دارد اما در مقایسه با بلاست زمانگیرتر است و فضای حافظه ی بیشتری نیاز دارد؛ اما در عوض برای یافتن همومولوگهای دور مفید است. خوشبختانه تکنولوژیهایی برای سرعت بخشیدن به Smith-Waterman ارائه شده اند که به عنوان مثال میتوان استفاده از چیپهای FPGA یا پردازشهای SIMDرا نام برد. برای گرفتن نتایج بهتر از بلاست میتوان تنظیمات مختلفی که برای این برنامه وجود دارد را تغییر داد، اما روشی وجود ندارد که برای هر دنباله ی دلخواه بهترین تنظیمات را ارائه کند. این تنظیمات شامل E-value ، gap costs, filters, word size, وsubstitution matrix میباشند.

پیوند به بیرون[ویرایش]

منابع[ویرایش]

  1. Altschul, Stephen F. , Warren Gish, Webb Miller, Eugene W. Myers, and David J. Lipman (۱۹۹۰). Basic local alignment search tool. J. Mol. Biol. ۲۱۵:۴۰۳-۱۰
  2. Bioinformatics basics: applications in biological science and medicine. Hooman H. Rashidi, Lukas K. Buehler. Publisher CRC Press, 2000. ISBN ۰-۸۴۹۳-۲۳۷۵-۴ pp.۳۹
  • مشارکت‌کنندگان ویکی‌پدیا، «BLAST»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۳ می ۲۰۱۱).