موازی سازی الگوریتم ساخت آرایه پسوندی به منظور تطبیق دقیق رشته های DNA برروی پردازنده گرافیکی

آرایه های پسوندی یک رشته، مجموعه مرتبی از تمام پسوندهای آن رشته هستند که این ساختمان داده در زمینه های شاخص گذاری متن، فشردگی داده و تطبیق الگو کاربرد دارند. در دهه اخیر، الگوریتم های سری زیادی برای ساخت آرایه های پسوندی ارایه شده است. در این مقاله بر روی یکی از دسته های اصلی الگوریتم های ساخت آرایه های پسوندی مطالعه ای انجام شد و هدف موازی سازی یکی از الگوریتم های سری ارایه شده در دسته دوم بر روی معماری موازی پردازنده گرافیکی است. الگوریتم SA-IS (Suffix Array-Induce Sorting) که یک الگوریتم بازگشتی بازمان خطی است، قابلیت موازیسازی به روش تقسیم و غلبه را دارد و جزء آخرین کارهای تحقیقاتی در این دسته است را میتوان به صورت موازی بر روی سخت افزار پردازنده گرافیکی پیاده سازی کرد. این الگوریتم توسط پلت فرم کودا با استفاده از تکنیک های پردازنده گرافیکی قابل پیاده سازی است. سرعت این الگوریتم موازی نسبت به الگوریتم سری آن درداده هایی با حجم بالا تا 40 برابر و نسبت به الگوریتم موازی مشابه در دسته خودش 2/ 1 برابر افزایش می یابد.

کلیدواژه ها:

آرایه های پسوندی ، الگوریتم - SA-IS ، پردازندهی گرافیکی ، کودا