An algorithm for finding approximate local similarities in DNA sequences

Dissertant

al-Shanableh, Najah Mithqal Ali

Thesis advisor

al-Rababiah, Mamun S.

Comitee Members

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

University

Al albayt University

Faculty

Prince Hussein Bin Abdullah Faculty for Information Technology

Department

Department of Computer Science

University Country

Jordan

Degree

Master

Degree Date

2009

Arabic Abstract

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

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

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

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

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

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

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

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

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

English Abstract

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.

Main Subjects

Information Technology and Computer Science

Topics

• Nucleic acids
• Data processing

No. of Pages

73

Table of Contents

• APA
• MLA
• AMA

Language

English

Data Type

Arab Theses

Record ID

BIM-302961