Sequence alignment algorithms such as the Smith-Waterman algorithm are among the most important applications in the development of bioinformatics. Sequence alignment algorithms must process large amounts of data which may take a long time. Here, we introduce our Adaptive Hybrid Multiprocessor technique to accelerate the implementation of the Smith-Waterman algorithm. Our technique utilizes both the graphics processing unit (GPU) and the central processing unit (CPU). It adapts to the implementation according to the number of CPUs given as input by efficiently distributing the workload between the processing units. Using existing resources (GPU and CPU) in an efficient way is a novel approach. The peak performance achieved for the platforms GPU + CPU, GPU + 2CPUs, and GPU + 3CPUs is 10.4 GCUPS, 13.7 GCUPS, and 18.6 GCUPS, respectively 

چکیده

الگوریتم های تنظیم توالی از قبیل الگوریتم Smith – Waterman در زمره مهمترین روش ها برای توسعه بیوانفورماتیک قرار می گیرد. این الگوریتم ها باید حجم زیادی از داده ها پردازش کنند که ممکن است زمان زیادی طول بکشد. در این مقاله ما روش چندپردازنده مرکب تطبیقی خود را برای تسریع پیاده سازی الگوریتم Smith - Waterman معرفی می کنیم. روش ما از واحد پردازنده گرافیکی (GPU) و واحد پردازنده مرکزی (CPU) استفاده می کند. این روش برای پیاده سازی مطابق با CPU‌های داده شده به عنوان ورودی از طریق توزیع بهینه حجم داده بین واحد‌های پردازنده تطبیق می یابد. استفاده از منابع موجود (GPU و CPU) در یک روش موثر، یک شیوه نوین است. عملکرد بیشینه به دست آمده برای پلتفرم های GPU + CPU، GPU + 2CPU و GPU + 3CPU به ترتیب برابر 10.4 GCUPS، 13.7 GCUPS و 18.6 GCUPS (با طول کوئری اسید آمینه 511) است.

1-مقدمه

تنظیم توالی پایگاه داده پروتئین و DNA در زمره مهمترین روش ها در بیوانفورماتیک است. این روش مستلزم پردازش حجم بالای اطلاعات هستند. الگوریتم های موجود مانند FASTA(2) و BLAST(3)، در یافتن روش های تقریبی سریع هستند. این الگوریتم ها دارای مشکل حساسیت هستند؛ زیرا آنها جستجو را مختصر کرده و به طور غیر‌منتظره ای مگر در مورد تشابهات قابل توجه ناموفق هستند. به عبارت دیگر، الگوریتم Smith – Waterman(SW) یک الگوریتم تطبیق توالی شناخته‌شده مورد استفاده در تحقیقات بیوانفورماتیک است...