Çoklu dizi hizalama probleminin yapay arı koloni algoritması ile çözülmesi
Solving multiple sequence alignment problem with artificial bee colony algorithm
Yazar: SELÇUK ASLAN
Danışman: YRD. DOÇ. DR. CELAL ÖZTÜRK
Erciyes Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2013
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Çoklu dizi hizalama, biyolojik sekansların yorumlanabilmesi için en sık başvurulan analiz yöntemidir. Makro moleküllerin yapı ve fonksiyon tahmininden filogenetik ağaçların oluşturulmasına, polimeraz zincir reaksiyon birincil tasarımından hücre simülasyonuna kadar Biyoinformatik?in hemen hemen tüm problemlerinde çoklu dizi hizalamalarına ihtiyaç duyulmaktadır.
Protein, DNA ya da RNA makro moleküllerine ait sekans bileşenlerinin hizalanması için kullanılan yaklaşımları genel olarak dinamik programlama algoritmaları ve sezgisel algoritmalar olarak iki gruba ayırmak mümkündür. İkiden fazla olan sekans sayısı ve sekans uzunlukları dikkate alındığında dinamik programlama bazı hesaplama sınırlarını beraberinde getirmektedir. Hem dinamik programlama sınırlamaları dikkate alındığında hem de çoklu dizi hizalama işlemi ayrık optimizasyon problemi olarak değerlendirildiğinde sezgisel algoritmaların bu problemlerin çözümünde kullanılabilirliği daha önemli hale gelmiştir. Bu tez bağlamında, arıların yiyecek arama davranışlarındaki zekiliği modelleyen Yapay Arı Koloni Algoritması kullanılarak çoklu dizi hizalama problemine ait optimum çözümler bulunmaya çalışılmıştır. Yapay Arı Koloni Algoritması?nın sağlam, esnek yapısı ve algoritmanın işçi, gözcü, izci arı fazlarının çoklu dizi hizalama problemi için önerilen yeni modelleri sayesinde literatürle karşılaştırılabilir sonuçlar alınmıştır. Aynı zamanda yapılan çalışmalar CUDA platformu ile birleştirilerek paralel çalışma performansları da araştırılmıştır.

Abstract:
Multiple Sequence Alignment is one of the most commonly used analysis tool for interpreting and identifying biological sequences. Almost all problems in Bioinformatics which can be extended from structure and function prediction to phylogenetic tree construction and polymerase chain reaction primer design to cell simulation needs methods of Multiple Sequence Alignment. 
The approaches chosen for aligning residues of the protein, DNA or RNA macro molecules roughly fall into two categories named dynamic programming algorithms and heuristic algorithms. When considering number of the aligned sequences are more than two and length of the aligned sequences dynamic programming algorithms have disadvantages and computational limitations. Considering main drawbacks of dynamic programming algorithms and accepting the multiple sequence alignment process as a combinatorial optimization problem, heuristic algorithms are more eligible than other greedy approaches in solving these problems. In the context of this thesis, Artificial Bee Colony Algorithm which is inspired by the intelligent foraging behaviors of honey bees is used to find the optimal solutions of multiple sequence alignments. The robust, flexible structure of Artificial Bee Colony Algorithm and newly proposed model for employed, onlooker, scout bee phases have given comparable results with similar works in the literature. In addition, performance of the parallelized methods has been analyzed by incorporating the proposed models and CUDA platform.