شماره ركورد كنفرانس :
4379
عنوان مقاله :
بهبود كارايي الگوريتم هم‌ترازسازي اسميت-واترمن با استفاده از واحد پردازنده‌ي گرافيكي
پديدآورندگان :
شاهمرادي نرجس nshahmoradi@webmail.guilan.ac.ir گروه مهندسي كامپيوتر، دانشكده مهندسي، دانشگاه گيلان , شاه‌بهرامي اسدالله shahbahrami@guilan.ac.ir گروه مهندسي كامپيوتر، دانشكده مهندسي، دانشگاه گيلان
كليدواژه :
الگوريتم اسميت-واترمن , برنامه‌نويسي پويا , بيوانفورماتيك , موازي‌سازي , هم‌ترازسازي توالي
عنوان كنفرانس :
هشتمين كنفرانس فناوري اطلاعات و دانش
چكيده فارسي :
هم‌ترازسازي توالي‌هاي بيولوژيكي يكي از وظايف مهم و چالش‌برانگيز بيوانفورماتيك است. اين فرايند براي تحليل و شناسايي نواحي مشابهت بين توالي‌ها به كار مي‌رود. الگوريتم‌هاي مختلفي براي چنين تحليل‌هايي وجود دارند كه از لحاظ دقت و پيچيدگي محاسباتي با يكديگر متفاوتند و در دو دسته‌ي كلي عمومي و محلي مي‌گنجند. الگوريتم اسميت-واترمن يكي از دقيق‌ترين الگوريتم‌هاي مبتني بر برنامه‌نويسي پويا براي يافتن بهترين هم‌ترازسازي محلي بين دو توالي است. اين الگوريتم در كنار دقت بالايي كه دارد، داراي پيچيدگي محاسباتي متناسب با حاصل‌ضرب طول دو توالي است. به همين دليل، در زمره‌ي الگوريتم‌هاي زمان‌بر است و براي افزايش سرعت آن از موازي‌سازي استفاده خواهد شد. هدف اين مقاله، افزايش كارايي الگوريتم اسميت-واترمن با استفاده از تكنيك موازي‌سازي بر روي GPU است. مرحله‌ي محاسبه‌ي ماتريس امتيازدهي بر روي GPU پياده‌سازي شده است. بررسي‌هاي انجام گرفته نشان مي‌دهند كه اين پياده‌سازي موازي از الگوريتم اسميت-واترمن، تسريع 47 برابري نسبت به حالت پياده‌سازي سريال الگوريتم دارد.
