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

همترازسازی توالی های بیولوژیکی یکی از وظایف مهم و چالش برانگیز بیوانفورماتیک است. این فرایند برای تحلیل و شناسایی نواحی مشابهتبین توالیها به کار می رود. الگوریتم های مختلفی برای چنین تحلیل هایی وجود دارند که از لحاظ دقت و پیچیدگی محاسباتی با یکدیگرمتفاوتند و در دو دسته ی کلی عمومی و محلی می گنجند. الگوریتم اسمیت-واترمن یکی از دقیق ترین الگوریتم های مبتنی بر برنامه نویسیپویا برای یافتن بهترین همترازسازی محلی بین دو توالی است. این الگوریتم در کنار دقت بالایی که دارد، دارای پیچیدگی محاسباتی متناسببا حاصل ضرب طول دو توالی است. به همین دلیل، در زمره ی الگوریتم های زمان بر است و برای افزایش سرعت آن از موازی سازی استفادهخواهد شد. هدف این مقاله، افزایش کارایی الگوریتم اسمیت-واترمن با استفاده از تکنیک موازی سازی بر روی GPU است. مرحله ی محاسبه یماتریس امتیازدهی بر روی GPU پیاده سازی شده است. بررسی های انجام گرفته نشان می دهند که این پیاده سازی موازی از الگوریتماسمیت-واترمن، تسریع 47 برابری نسبت به حالت پیاده سازی سریال الگوریتم دارد.

کلیدواژه ها:

الگوریتم اسمیت-واترمن ، برنامه نویسی پویا ، بیوانفورماتیک ، موازی سازی ، همترازسازی توالی