Genomik verinin analizinde yapay arı koloni algoritması temelli yeni tekniklerin geliştirilmes
Developing new techniques based on artificial bee colony algorithm for analysis of genomic data
Yazar: SELÇUK ASLAN
Danışman: PROF. DR. DERVİŞ KARABOĞA
Erciyes Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2016
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin: Algoritmalar = Algorithms ; Global optimizasyon yöntemi = Global optimization method

Özet:
Sekanslama, bilgi depolama ve çözümleme teknolojilerindeki gelişme ile birlikte, aralarında fare, şempanze ve insanında olduğu yüksek organizmalara ait bütün genom elde edilmiş durumdadır. Ancak, dört farklı nükleotidin değişik sayı ve sıralardaki ardışık yerleşimi olan genomun tam diziliminin elde edilmesi, ekzon bölgelerinin nerede başlayıp bittiği ya da transkripsiyon faktörünün bağlanacağı bölgeyi nasıl belirlediğinin bilinmesi için tek başına yeterli değildir. Transkripsyion ve translasyon gibi kompleks biyolojik süreçlerin yönetilmesinden sorumlu ve motif olarak isimlendirilen çeşitli fonksiyonel bölgelerin bulunması en zor biyoinformatik problemleri arasında yer alır. Yeni genomik verilerin kolayca sekanslanması ve kompleks düzenleyici süreçler hakkında artan bilgimiz dikkate alındığında, hızlı ve hassas motif tahmin metodlarının geliştirilmesi ya da mevcut metodların önemli boyutlarda iyileştirilmesi hala bir gereklilik olarak durmaktadır.

Geçtiğimiz yıllarda sezgisel teknikler birçok araştırmacının dikkatini çekmiş, aralarında sekansların hizalanması, yapı tahmini ve protein-protein etkileşiminin de olduğu kompleks biyoinformatik problemlerinin çözümünde kullanılmıştır. Bu tez çalışmasında, sürü zekası temelli sezgisel yöntemlerin en başarılarından biri olan Yapay Arı Koloni (Artificial Bee Colony, ABC) algoritmasından faydalanılmış ve DNA sekansları arasında korunmuş bölgelerin bulunması için algoritmanın görevli ve gözcü arı fazlarında kullandığı aday çözüm üretme modeline olabildiğince bağlı kalınarak ABCMOD1, ABCMOD2 ve ABCMOD3 isimleri verilen üç yeni motif tahmin yöntemi geliştirilmiştir. Buna ek olarak, ABCMOD1, ABCMOD2 ve ABCMOD3 algoritmaları konsensus sekansları ile yönlendirilen komşu ve parametre seçim stratejileri ile güçlendirilmiştir. Son olarak, ABCMOD1, ABCMOD2 ve ABCMOD3 algoritmaları ve bunların konsensus sekans destekli implementasyonları paylaşılan-hafızalı sistemler için paralel hale getirilmiştir. Üç farklı sekans grubu için yapılan uygulamalara ait sonuçlar, tez dahilinde önerilen ABC algoritması temelli seri ve paralel modellerin Genetik algoritma temelli MOGAMOD, Değişken Komşu Arama algoritması temelli MO-VNS, Diferansiyel Gelişim algoritması temelli DEPT, çaprazlama ve mutasyon operatorleri ile kullanılan ABC Algoritması temelli MOABC, Yerçekimi Araştırma algoritması temelli MO-GSA ile kıyaslandığında oldukça başarılı sonuçlar ürettiğini göstermiştir.

Abstract:
Driven by the technological improvements in sequencing methods, information storage and retrieval systems, the whole genomes of some higher organisms including mouse, chimpanzee, and also human are now available. However, knowing the concrete nucleotide sequences, containing arbitrary number of only four different type nucleotides, of these genomes is not enough to understand where an exon starts or finishes, how a transcription factors find the corresponding domains to bind to sequence. Discovery of these mentioned function regions that regulate the complex biological processes like transcription and translation and called motifs is one of the most challenging problem in bioinformatics. With the avalanche of the newly sequenced genomic data and our evolving understanding of the characteristics of the regulatory mechanisms, there is still a need for developing fast and accurate motif discovery techniques or considerably refinement on the existing models.

In recent years, metaheuristic techniques have attracted the researchers attention and they have been used to solve complex bioinformatics problems including alignment of sequences, structure prediction, protein-protein interaction and so on. In this PhD dissertation, we utilized Artificial Bee Colony (ABC) algorithm that is one of the most important swarm intelligence based metaheuristics and proposed three new ABC algorithm based techniques called ABCMOD1, ABCMOD2 and ABCMOD3 by adhering to the individual effect of the candidate generation approach in the mathematical expression used in the employed and onlooker bee phases to find conserved regions within DNA sequences. In addition to these, we improved ABCMOD1, ABCMOD2 and ABCMOD3 algorithms by proposing consensus string based neighbour and parameter selection strategies. Finally, ABCMOD1, ABCMOD2 and ABCMOD3 algorithms and their consensus string based improved implementations are parallelized. Experimental studies on three different data sets showed that both serial and parallel implementation of the ABC algorithm based motif discovery techniques outperform the Genetic Algorithm based motif discovery technique MOGAMOD, Variable Neighbor Search algorithm based MO-VNS, Differential Evolution algorithm based DEPT, ABC algorithm and evolutionary operator basedMOABC and Gravitational Search algorithm basedMO-GSA algorithms.