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

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