Design and Evaluation of A Parallel DNA Multiple Sequence Alignment (MSA) Algorithm
| المؤلف الرئيسي: | Al Kindi, Asma Abdulaziz Yahya (Author) |
|---|---|
| مؤلفين آخرين: | Day, Khaled (Advisor) |
| التاريخ الميلادي: |
2015
|
| موقع: | مسقط |
| الصفحات: | 1 - 71 |
| رقم MD: | 965592 |
| نوع المحتوى: | رسائل جامعية |
| اللغة: | الإنجليزية |
| الدرجة العلمية: | رسالة ماجستير |
| الجامعة: | جامعة السلطان قابوس |
| الكلية: | كلية العلوم |
| الدولة: | عمان |
| قواعد المعلومات: | Dissertations |
| مواضيع: | |
| رابط المحتوى: |
عدد مرات التحميل
31
| المستخلص: |
ترتيب السلاسل المتعددة أو ما يعرف بـ (multiple sequence alignment MSA) هي عملية أساسية يتم تطبيقها في أي دراسة تهدف إلى مقارنة السلاسل البيولوجية (سواء كانت DNA أو RNA أو البروتين). تعتمد العديد من التجارب في علم الأحياء الجزيئي والحوسبي وفي المعلوماتية الحيوية على ترتيب السلاسل، وجودتها تؤثر على العمليات التحليلية اللاحقة التي تتضمنها هذه الحقول العلمية. إن التحدي في حوسبة السلاسل المتعددة يكمن في الموازنة بين كفاءة الأداء والمحافظة على جودة المخرجات. فقد تم تطوير العديد من طرق حوسبة ترتيب السلاسل، ووجد أنه كلما زادت كفاءة الأداء تصبح الجودة (أي دقة ترتيب السلاسل) أقل، فيسبب ذلك خلا أساسية ومشتركا بين جميع هذه الطرق. تتطلب الطرق التي تعطي ترتيبا عالي الدقة مصادر حوسبية عالية، فتكون غير عملية لعدد كبير من السلاسل البيولوجية. وبسبب أهمية ترتيب السلاسل المتعددة في الكثير من دراسات علم الأحياء إلى جانب النقص في دقة الطرق المتاحة لترتيب السلاسل المتعددة فإن هناك حاجة ملحة إلى تطوير حل ذي كفاءة أداء عالية ينتج ترتيب سلاسل دقيقة. إحدى وسائل تحسين أداء هذه الطرق الدقيقة هي توظيف عدد من المعالجات التي تعمل بشكل متواز لإيجاد ترتيب السلاسل المتعددة وتقليص الوقت اللازم للحساب. في هذا البحث تم تطوير حل ذي كفاءة أداء عالية لإيجاد ترتيب السلاسل المتعددة MSA باستخدام الحوسبة المتوازية (parallel computing) وهو يعتمد على خوارزمية دقيقة لإيجاد ترتيب الزوج من السلاسل تعرف بخوارزمية Needleman-Wunsch. أولا: قمت بتعميم خوارزمية Needleman-Wunsch من ترتيب زوج واحد إلى عدد أكبر من السلاسل ومن ثم صممت حلولا ذات كفاءة أداء عالية باستخدام منهجين معروفين في الحوسبة المتوازية، وهما: تبادل الرسائل (message passing) والذاكرة المشتركة (shared memory)، وذلك لتحسين نسختنا المعممة من خوارزمية Needleman-Wunsch. علاوة على ذلك، تم إجراء تقييم أداء تحليلي وتجريبي للحلول المقترحة. وأظهرت نتائج التقييم أن تسارع الأداء تحسن بشكل كبير بزيادة عدد السلاسل. هذا التحسن يزداد كلما زاد عدد المعالجات، ولكن إلى حد معين. مع ذلك لم يتحسن تسارع الأداء مع سلاسل أطول لأن توزيع العمل بين المعالجات تم عبر عدد السلاسل. ولهذا فإن هذه الحلول المتوازية ملائمة جدا للتطبيقات التي تتطلب ترتيبا دقيقا لعدد كبير من السلاسل. على سبيل المثال: دراسات الترابط الجيني (Gerome-wide association studies) والتي تستخدم مع ذلك عددا كبيرا من المعالجات كالأنظمة متعددة النوى (multicore systems) أو الحواسيب فائقة السرعة (supercomputers). |
|---|
عناصر مشابهة
-
A Parallel Algorithm for Solving Large Scale Markov Chains on A High Performance Computer
بواسطة: Al Kharousi, Ibrahim Ahmed Mohammed منشور: (2012) -
Comparative Study of Genetic Algorithm and Dynamic Programming of DNA Sequence Alignment
بواسطة: Ahmed, Aisha Mohammed Mahjoub منشور: (2019) -
Designing Parallel Algorithms for Parallel System
بواسطة: Al-Khafaji, Israa M. Abdalameer منشور: (2018) -
An Efficient In-Exact Algorithm for Finding Approximate Alignment in DNA Sequences
بواسطة: عقيلان، رفيدة محمود منشور: (2018) -
Parallel Metaheuristic Algorithms for Solving the Link Prediction Problem
بواسطة: برهم، رهام شوقي أحمد منشور: (2018)
