Sezgisel yaklaşımlara dayalı çoklu dizi hizalaması üzerine bir çalışma

Biyoinformatik, biyolojik verileri kavramsallaştırmak ve aralarındaki ilişkileri otaya koymak için matematik, bilgisayar ve istatistik gibi bilim dallarından yararlanan bir bilgi sistemidir. Biyoinformatikde ki en önemli görevlerden biri dizi hizalama problemidir. Dizi hizalama problemi biyolojideki artan veri sayısıyla orantılı olarak zorlaşmaktadır ve dizi hizalama problemini manuel olarak çözmek imkânsız hale gelmektedir. Bunun için otomatikleştirilmiş bilgisayar sistemlerinden yararlanılmaktadır. Dizi hizalama problemi kendi içerisinde ikili dizi hizalama ve çoklu dizi hizalama olarak ikiye ayrılmaktadır. Bu tez çalışmasında çoklu dizi hizalama problemi ele alınmıştır. Çoklu dizi hizalama probleminin çözümü için meta sezgisel yaklaşımı baz alan genetik algoritma, diferansiyel gelişim algoritması ve tavlama benzetimi algoritması kullanılmıştır. Algoritmaların geliştirilmesindeki amaç dinamik programlamadaki bellek kullanımı sorunu, aşamalı yöntemlerden kaynaklanan açgözlü yaklaşım sorununu gidermektir. Algoritmaların başarılarını test etmek ve karşılaştırabilmek için SP (çiftlerin toplamı) skorlama işlemi kullanılmıştır. Geliştirilen algoritmalar hem zaman hem de doğruluk açısından kendi aralarında ve mevcut çoklu dizi hizalama algoritmalarıyla karşılaştırılmıştır. Belirli veri setleri üzerinde geliştirilen algoritmalar, mevcut hizalama algoritmalarından daha iyi sonuç göstermiştir. Anahtar sözcükler: Çoklu Dizi Hizalama, Sezgisel Algoritmalar, Genetik Algoritma, Tavlama Benzetimi, Diferansiyel Gelişim Algoritması

Bioinformatics is an information system that uses mathematics, computing and statistics to conceptualize biological data and establish relationships between them. One of the most important tasks in bioinformatics is the sequence alignment problem. The sequence alignment problem is getting harder in proportion to the increasing number of data in biology and it is becoming impossible to solve the sequence alignment problem manually. For this, automated computer systems are used. Sequence alignment problem is divided into two as binary sequence alignment and multiple sequence alignment. In this thesis, the multiple sequence alignment problem is addressed. Genetic algorithm, differential evolution algorithm and simulated annealing algorithm based on meta-heuristic approach are used to solve the multiple sequence alignment problem. The aim of the development of the algorithms is to overcome the memory usage problem in dynamic programming and the greedy approach problem arising from incremental methods. The SP (Sum of Pairs) scoring process was used to test and compare the success of the algorithms. The algorithms are compared with each other and with existing multiple sequence alignment algorithms in terms of both time and accuracy. On certain datasets, the developed algorithms showed better results than the existing alignment algorithms.