ترجمه فارسی عنوان مقاله

یک راهبرد موازی داده برای همتراز کردن توالی‌های زیست‌شناختی روی پایگاه چندپردازنده‌ای همگن

عنوان انگلیسی

A Data Parallel Strategy for Aligning Multiple Biological Sequences on Homogeneous Multiprocessor Platform

کد مقاله	سال انتشار	تعداد صفحات مقاله انگلیسی
54040	2011	8 صفحه PDF

منبع

Publisher : IEEE (آی تریپل ای)

Journal : Chinagrid Conference (ChinaGrid), 2011 Sixth Annual, Date of Conference: 22-23 Aug. 2011 Page(s): 188 - 195 Print ISBN: 978-1-4577-0885-5 INSPEC Accession Number: 12316680 Conference Location : Liaoning

فهرست مطالب ترجمه فارسی

چکیده

مقدمه

فرمولبندی مساله

همترازسازی چند توالی

تحلیل راهبرد موازی

توصیف شهودی خوشه-توزیع-همترازسازی

دسته‌بندی

فاصلۀ محاسباتی توالی‌ها

الگوریتم PDBSCAN پیشرفته

الگوریتم ابتکاری توزیع مجدد

الگوریتم ابتکاری توزیع مجدد

همترازسازی

شکل. 1. همترازسازی تدریجی پروفیل و ترکیب دسته‌های متوالی

ارزیابی عملکرد

ارزیابی کیفیت

جدول 1 نمره‌دهی‌های Q روی مقایسۀ زیرمجموعه‌ها با استفاده از BaliBase

جدول 2 نمره‌دهی‌های Q روی مقایسۀ زیرمجموعه‌ها با استفاده از Prefab

ارزیابی مقیاس‌بندی

شکل.2. مقیاس‌بندی زمان اجرا در برابر تعداد پردازنده‌ها.

شکل.3. تسریع‌ها برای دسته- توزیع- همترازسازی با افزایش تعداد پردازنده‌ها.

نتیجه‌گیری

ترجمه کلمات کلیدی

همترازسازی چند توالی؛ الگوریتم موازی؛ محاسبات با عملکرد بالا

کلمات کلیدی انگلیسی

Algorithm design and analysis Clustering algorithms Heuristic algorithms Load management Parallel processing Partitioning algorithms Program processors

ترجمه چکیده

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

ترجمه مقدمه

همترازسازی چند توالی (MSA) یک مسالۀ بسیار مهم بوده و عملیات اساسی اجرایی در زیست‌شناسی محاسباتی است. این روش اطلاعات ارزشمندی در ارتباط با روابط تکاملی فراهم کرده، موتیف‌های محافظت‌شده را شناسایی کرده و پیش‌بینی ساختار برای RNA و پروتئین‌ها را بهبود می‌دهد. با رشد سریع تکنیک‌های توالی‌سازی کلان، هم‌اکنون توالی‌های کاملتری از ژنوم در پایگاه‌ داده‌های عمومی موجود بوده و تعداد توالی‌ها به سرعت در حال افزایش است. از سوی دیگر، به طور ذاتی مسالۀ ترکیبیاتی است. با معرفی محتمل تعداد مختلفی از فضاها (فضاهای خالی) در موقعیت‌های گوناگون توالی‌ها، نتایج مختلفی برای تراز حاصل می‌شود. برای دو توالی که هر کدام به تعداد x باقی‌مانده دارند، به تعداد ترکیب ترازی ممکن وجود دارد [1]. اثبات شده است که همترازسازی چند توالی یک مسالۀ کاملا NP است. در نتیجه، نیاز مبرم به توسعۀ راهبردهای موثر و قابل مقیاس‌بندی برای عملکرد به شدت محاسباتی و حجم عظیم داده‌های موجود است. پاسخ‌های موازی یک روش کارساز بوده و الگوریتم‌های موازی متعددی توسعه یافته است تا رویۀ همترازسازی تسریع شود [2]، [3]. یکی از اولین روش‌های دقیق در نوشته‌‌های فنی برای همترازکردن محلی دو توالی روش اسمیت- واترمن (SW) است [4]، که اصلاح شدۀ الگوریتم نیدلمن- وانچ (NW) است [5]. این روش مبتنی بر برنامه‌نویسی پویا بوده و ماتریس مشابهتی با اندازۀ m×n را محاسبه می‌کند، که m و n اندازه‌های توالی‌ها هستند. اسمیت- واترمن دارای پیچیدگی O(mn) زمان و فضاست. در این الگوریتم بیشتر زمان صرف محاسبۀ ماتریس مشابهت D می‌شود و این بخشی از چیزی است که آن را معمولا موازی‌سازی گویند. در طی سال‌ها انواع حالت‌های موازی از الگوریتم اسمیت- واترمن اساسی ارائه شده است

دانلود رایگان 2 صفحه اول مقاله لاتین (PDF)

پیش نمایش مقاله

چکیده انگلیسی

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.