An Efficient Approach for Storing Biological Sequences/
منهج فعال لتخزين السلاسل الحيوية
by Sarah Ahmed Mohamed Abd Ellatif Elnady; Prof. Abeer ElKorany, Prof. Akram Salah, Dr. Sabah Sayed.
- 77 Leaves: illustrations ; 30 cm. + CD.
Thesis (M.Sc.)-Cairo University, 2023.
Bibliography: pages 71-77.
In the blossoming age of Next-Generation Sequencing (NGS) technologies, genome sequencing has become much easier and more affordable. The large number of enormous genomic sequences obtained demands the availability of huge storage space in order to be kept for analysis. Since the storage cost has become an impediment facing biologists, there is a constant need of software that provides efficient compression of genomic sequences. Most general-purpose compression algorithms do not exploit the redundancies that exist in genomic sequences which is the reason for the success and popularity of special-purpose DNA compression algorithms. One of the main schemes of special-purpose DNA compression is reference-based compression. Although reference-based compression algorithms can achieve outstanding compression, they face several challenges. In this research, a new reference-based lossless compression framework is proposed for deoxyribonucleic acid (DNA) sequences stored in FASTA format. This framework makes use of redundancies in DNA sequences to achieve efficient compression. It has three main phases: data preparation, action sequence generation and gzip compression. The first two phases act as a reference-based compression layer above gzip compression. Furthermore, the “Genetic algorithm”, in addition to greedy alignment algorithms, is used to improve the proposed compression framework. Moreover, a reference selection technique is proposed as an initial phase in the proposed framework. The proposed reference selection technique uses clustering algorithms for determining the most suitable reference genomes to be selected thus enabling the whole framework to reach even more efficient compression. Several experiments were performed to evaluate the proposed framework and the experimental results show that it is able to obtain promising compression ratios saving up to 99.9% space and reaching a gain of 83% with respect to existing algorithms for some plant genomes. The proposed framework also succeeds in performing the compression at acceptable time; even saving more than 50% of the time taken by competitive algorithms in most experiments. Results also proved that using references selected by the proposed reference selection technique provides extremely higher compression gains reaching up to 85% than using a manually selected or random references. في الآونة الأخيرة، ارتفع عدد السلاسل الحيوية المتاحة بشكل كبير بفضل تقنيات التسلسل الجديدة. تطلب هذه التسلسلات الهائلة توفر مساحة تخزين ضخمة من أجل الاحتفاظ بها للتحليل. وبالتالي، هناك حاجة مستمرة لخوارزميات ضغط جديدة ومناسبة لهذه التسلسلات لتسهيل تخزينها ونقلها. على الرغم من وجود العديد من خوارزميات ضغط البيانات للأغراض العامة، إلا أنها لا تستغل البنية الأساسية للتسلسلات الجينومية. لذلك، تم تصميم خوارزميات ضغط خصيصًا للتسلسلات الجينومية. ومع ذلك، تواجه هذه الخوارزميات أيضًا بعض التحديات. لذا، في هذه الرسالة، تم اقتراح منهج فعال من أجل تحقيق ضغط للتسلسلات الجينومية. يعتمد هذا المنهج على طريقة ضغط جديدة باستخدام مرجع للتسلسلات الجينومية. الهدف هو أن تستفيد هذه الطريقة من التكرارات في تسلسلات الجينوم لتحسين نسبة ضغط التسلسلات والوقت ومحاولة التغلب على بعض التحديات التي تواجه الخوارزميات الموجودة مسبقا. علاوة على ذلك، تستخدم هذه الخوارزمية تقنيات الحوسبة الناعمة مثل الخوارزميات الجينية لتحقيق ضغط أكثر فعالية. وأيضا في هذه الرسالة تم اقتراح طريقة جديدة لاختيارالمرجع المناسب حتى يستخدم في عملية ضغط التسلسلات لأن اختيار المرجع المناسب يعتبر عقبة تواجه خوارزميات الضغط التي تحتاج إلى مرجع. هذه الطريقة تعتمد في الأساس على خوارزميات التصنيف وتستخدم أيضا المنهج الفعال الذي اقترحناه. في النهاية تم عرض ومناقشة جميع نتائج المنهج المقترح والتي من أبرزها الوصول لضغط أفضل للجينوم بنسبة تصل إلى ٨٣٪ أفضل من بعض الخوارزميات الموجودة وتوفير أكثر من ٥٠٪ من وقت ضغط التسلسلات و٩٩.٩٪ من مساحة التخزين. كما أن طريقة اختيار المرجع المقترحة تستطيع تحسين ضغط المجموعات بنسب كبيرة تصل إلى ٨٥٪.
Text in English and abstract in Arabic & English.
Bioinformatics
Bioinformatics, DNA sequences reference-based compression greedy alignment