موازی‌سازی کارا و تسریع عملیات انطباق رشته‌ها بر روی بستر پردازنده های چند هسته ای

انطباق رشته‌ها یک بحث پایه‌ای و پرکاربرد در بیوانفورماتیک است که جهت یافتن میزان مشابهت توالی‌های آمینواسیدی و یا رشته‌های دی.ان.ای از آن استفاده می‌شود. عمل انطباق دو رشته با یکدیگر یک عمل پایه‌ای است که در انطباق‌های چندگانه نیز از آن استفاده می‌شود. یکی از الگوریتم‌های انطباق دو رشته، الگوریتم نیدلمن-وانچ است که در آن از شیوه‌ی برنامه‌سازی پویا برای انجام این عملیات استفاده می‌شود. از چالش‌های مطرح در این الگوریتم، بالا بودن پیچیدگی زمانی آن است که جهت بهبود در سرعت اجرای این الگوریتم از راه‌کارهایی موازی می‌توان استفاده نمود. ازاین‌رو با ظهور پردازنده‌های چندهسته‌ای و امکان انجام محاسبات به شکل موازی می‌توان تسریع قابل‌ملاحظه‌ای را به دست آورد. بر اساس روش‌های موازی‌سازی موجود برای این الگوریتم، در هر گام خانه‌های آرایه‌ی به‌کاررفته در روش برنامه‌سازی پویا یک قطر به‌طور هم‌زمان و موازی تکمیل می‌شود. در این مقاله با یک تغییر دیدگاه نسبت به مسئله و در نظر گرفتن یک تصور گراف‌گونه، روشی ارائه شده ‌است تا به نسبت روش‌های پیشین تسریع مناسبی را ارائه کند. نتایج به‌دست‌آمده نشان می‌دهد، در این پیاده‌سازی بهبود عملکردی تا حدود 5.9 برابر نسبت به پیاده‌سازی‌های پیشین حاصل می‌گردد..