DNA dizileri için sezgisel yöntemlere dayalı çoklu dizi hizalama yaklaşımlarının karşılaştırılması
Comparison of multiple sequence alignment approaches based on heuristic methods for DNA sequences
Yazar: Erdirik, Hatice; Karcıoğlu, Abdullah Ammar; Tanyolaç, Bahattin; Bulut, Hasan
Dergi: Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, Vol. 41 No. 1, 2024
Anahtar kelimeler: Data Structures and Algorithms ; Veri Yapıları ve Algoritmalar ; Informetrics ; İnformetrik ; Çoklu Dizi Hizalaması,Sezgisel Yaklaşım,Genetik Algoritma,Diferansiyel Evrim,Benzetimli Tavlama,Biyoenformatik. ; Multiple Sequence Alignmnet,Heuristic Approach,Genetic Algorithm,Differential Evaluation,Simulated Annealing,Bioinformatic

Biyoenformatik, biyolojik verileri kavramsallaştırmak ve aralarındaki ilişkileri anlamak için matematik, bilgi işlem ve istatistikten faydalanan bir bilim dalıdır. Artan biyolojik veri hacmi, dizi hizalama problemini daha karmaşık hale getirerek manuel çözümleri imkânsız kılmıştır. Bu nedenle, otomatik hesaplama sistemleri geliştirilmiştir. Dizi hizalaması, çiftli ve çoklu olmak üzere iki kategoriye ayrılır. Bu çalışma, genetik algoritma (GA), diferansiyel evrim (DE) ve simüle edilmiş tavlama (SA) algoritmaları gibi meta-sezgisel yöntemleri kullanarak çoklu dizi hizalama problemine odaklanmaktadır. GA, DE, GASA ve DESA algoritmaları önerilmiş ve DNA dizileri üzerinde Needleman-Wunsch algoritmasıyla hizalamalar yapılmıştır. Deneyler, GA'nın en iyi çalışma zamanına sahip olduğunu, DE ve DESA'nın ise daha uzun sürdüğünü göstermiştir. GA, DE ve DESA, GASA'ya göre daha yüksek hizalama puanları üretmiştir. Önerilen algoritmalar, Clustal algoritmasına kıyasla çoğu veri kümesinde daha iyi hizalama puanları sunarken, Clustal en hızlı çalışmayı gerçekleştirmiştir. Ayrıca, önerilen yöntemlerin aynı uzunluktaki diziler üzerinde mevcut algoritmalardan üstün performans gösterdiği tespit edilmiştir. Özellikle dört veri kümesinde (trnN-GUU_rps12, rrn4.5_rps12, rrn5_rps12, psbT_pbf1) önerilen algoritmalar daha yüksek puanlar elde etmiştir.

Bioinformatics utilizes mathematics, computing, and statistics to analyze biological data and establish relationships among them. As biological data volumes increase, the sequence alignment problem becomes more complex, rendering manual solutions impractical and necessitating automated computational systems. Sequence alignment is categorized into pairwise and multiple sequence alignment. This study addresses the multiple sequence alignment problem using meta-heuristic approaches, specifically genetic algorithms (GA), differential evolution (DE), and simulated annealing (SA). Four algorithmic variations—GA, DE, GASA, and DESA—are proposed, reordering DNA sequences with the Needleman-Wunsch algorithm to produce diverse alignments. Experimental results show that GA, DE, and DESA achieved higher alignment scores than GASA, with GA exhibiting the fastest runtime, while DE and DESA had longer runtimes than both GA and GASA. Compared to the Clustal algorithm, the proposed algorithms generally achieved better alignment scores across most datasets, though Clustal demonstrated the fastest runtime. Specifically, for four datasets (trnN-GUU_rps12, rrn4.5_rps12, rrn5_rps12, psbT_pbf1), the proposed algorithms outperformed Clustal in alignment scores. Additionally, the proposed methods proved more effective on datasets with sequences of equal length compared to existing alignment algorithms. These findings highlight the potential of the proposed algorithms in improving multiple sequence alignment outcomes.