An algorithm for finding approximate local similarities in DNA sequences

مقدم أطروحة جامعية

al-Shanableh, Najah Mithqal Ali

مشرف أطروحة جامعية

al-Rababiah, Mamun S.

أعضاء اللجنة

al-Samawi, Venus Wazir
Nhood, Jihad
Nusayr, Maryam

الجامعة

جامعة آل البيت

الكلية

كلية الأمير الحسين بن عبد الله لتكنولوجيا المعلومات

القسم الأكاديمي

قسم علوم الحاسوب

دولة الجامعة

الأردن

الدرجة العلمية

ماجستير

تاريخ الدرجة العلمية

2009

الملخص العربي

يعتبر إيجاد مناطق التشابه في الحمض النووي (DNA) أحد أهم العمليات عند تحليل الحمض النووي.

و هو يعد مؤشر على وجود علاقات القربى بين الأحماض أو يستخدم للبحث عن الطفرات الوراثية ذات الدلالات المرضية.

إن إيجاد الطفرات الوراثية مهم جدا لتحديد الطرق العلاجية الملائمة لبعض المرضى مما قد يؤثر على حياتهم.

يستخدم التشابه التقريبي أيضا في تحديد درجة تشابه السلالات الجينية للكائنات الحية مما يساعد على التعرف على الوظائف الحيوية للجينات المكتشفة حديثا.

أهم طرق البحث عن مناطق التشابه في سلاسل الحمض النووي الرايبوزي تنقسم بشكل رئيسي إلى نوعين البرمجة الديناميكية و البرمجة المعتمدة على تنقية النتائج المحتملة.

لكل منهما ما يميزها عن الأخرى فالبرمجة الديناميكية تضمن أفضل النتائج بينما التنقية للنتائج تقلل من الزمن اللازم للبحث.

تم في هذه الدراسة اقتراح خوارزمية AFALS-N)) لإيجاد مناطق التشابه التقريبي في سلاسل الحمض النووي (DNA)، و يتمثل مبدأ عمل الخوارزمية على تنقية النتائج المحتملة و تقليلها لتقليل عمليات البحث.

تم بناء برمجية تطبق الخوارزمية المقترحة و تم اختبار الخوارزمية المقترحة باستخدام عينات حمض نووي حقيقية و قد أظهرت النتائج تحسنا ملموسا من ناحية وقت البحث و الدقة.

و لقد قورنت الخوارزمية المقترحة مع خوارزمية (PatternHunter) حيث كان أدائها أفضل و بلغت نسبة التحسين نحو 9، 0 %.

الملخص الإنجليزي

Finding approximate local similarities in long DNA sequences is very important in bioinformatics.

These local regions of approximated similarity may be a consequence of functional, structural, or evolutionary relationships between the sequences.

DNA sequences, which hold the codon of life for every living organism, can be abstractly viewed as very long strings over a four–letter alphabet of A, C, G, and T.

Proteins which use an alphabet of 20 symbols, are translations from selected stretches of DNA, using a predefined translations table where each 3 letters of DNA translated to one amino-acid.

Many projects to sequence the genome of some species are well advanced or calculated.

The very large number of species (and their genetic variations) that is of interest to man, suggest that many new sequences will be revealed as the improved sequencing techniques and analysis are deployed Consequently, we are at a technical threshold.

Techniques that was capable of exploiting the smaller collections of genetic data, for example via serial search, may require radical revision.

Several techniques have been developed to address this problem.

However this study focuses not only on developing an algorithm, we also suggest advanced way to find acceptable results with increased sensitivity and decreased computation time using heuristics.

The proposed algorithm (AFALS-N) has been presented as an approximate local similarities finder and as a pair wise alignment algorithm.

It has been implemented using java and tested with real DNA sequences.

The experimental results have shown that AFALS-N performed better then Pattern Hunter.

When Compared with Pattern Hunter the enhancement over execution time was 0.9 %.

Also AFALS-N has achieved 66 % sensitivity.

التخصصات الرئيسية

تكنولوجيا المعلومات وعلم الحاسوب

الموضوعات

• الأحماض النووية
• معالجة البيانات

عدد الصفحات

73

قائمة المحتويات

• APA
• MLA
• AMA

لغة النص

الإنجليزية

نوع البيانات

رسائل جامعية

رقم السجل

BIM-302961