In this paper, we address the biological sequence alignment problem, which is a fundamental operation performed in computational biology. We employ the data parallelism paradigm that is suitable for handling large-scale processing to achieve a high degree of parallelism. Using data parallelism, we propose a strategy in which we employ a parallel clustering scheme to partition the set of sequences into subsets based on sequence similarity. Then the subsets are distributed among the processors using a heuristic algorithm based on Integer Programming so as to minimize the overall processing time, and each subset can be independently aligned in parallel using any sequential approach. The global alignment is achieved using a progressive profile-profile alignment within and between the processors. We implement the proposed algorithm on a cluster using the MPI library, and analyze the experimental results for different problem sizes in terms of quality of alignment, execution time and speed-up

چکیده

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

1-مقدمه

همترازسازی چند توالی (MSA) یک مسالۀ بسیار مهم بوده و عملیات اساسی اجرایی در زیست شناسی محاسباتی است. این روش اطلاعات ارزشمندی در ارتباط با روابط تکاملی فراهم کرده، موتیف های محافظت شده را شناسایی کرده و پیش بینی ساختار برای RNA و پروتئین ها را بهبود می دهد...