Biyolojik veritabanlarında etkin benzerlik hesaplama
Effective similarity calculation in biological databases
Yazar: ARDA SÖYLEV
Danışman: DOÇ. DR. OSMAN ABUL
TOBB Ekonomi ve Teknoloji Ü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 ; Biyoloji = Biology
Dizin: Biyoinformatik = Bioinformatics ; Grafikler = Graphics ; Paralel hesaplama = Parallel computing

Özet:
Canlının temel özelliklerini taşıyan en küçük birim olan hücrenin içerisinde meydana 
gelen olayların açıklanması biyolojik ağlarının incelenmesiyle mümkün olur. Bu 
inceleme için kullanılan tekniklerden biri benzerlik tabanlı analizdir. Bu kapsamda, 
bir sorgu ağıyla biyolojik ağlardan oluşan bir biyolojik veritabanı karşılaştırılmakta, 
sorgu ağıyla benzerliği belli bir eşik değerinin üzerinde ve aşağısında olan ağlar 
ayrışmaktadır. Bu problemin çözümü, iki ağın benzerliğinin bulunmasını gerektirir. 
Literatürde NP-tam olarak geçen alt çizge eşleniği problemi sebebiyle problemin
çözümü hesaplamsal olarak çok maliyetlidir. Çözüm için literatürde çeşitli yöntemler 
geliştirilmiştir. Bu yöntemlerden biri olan QNET yöntemi, bu tez çalışması 
kapsamında Java diliyle ve Hadoop çatısında kodlanmıştır. 7 düğümlü sorgu ağları 
için Hadoop gerçekleştirimi 10 makinalı (18 çekirdekli) bir öbekte 11,42 hızlanma 
sağlamıştır.
Ayrıca literatürde yer alan "referans tabanlı indeksleme yöntemi" incelenerek ESBiD 
yöntemi geliştirilmiş, bir referans tabanlı indeksleme yöntemi olan RINQ' nun
zayıflıkları üzerine çalışmalar yapılmıştır. Bu kapsamda sezgisel yöntemler 
kullanılarak belirsizlik setindeki ağ sayısı %29,85 oranında, %93,22 doğruluk 
payıyla azaltılmış, referans ağların seçim yöntemi değiştirilmiş ve belirsizlik setinde 
biriken ağların daha hızlı hizalanması için "en yüksek dereceli düğüm" tekniği
geliştirilmiştir. Bu teknik, QNET' le yapılan tam hizalamanın %89,76 etkinliğine 
%51,14 daha kısa sürede ulaşmıştır .

Anahtar Kelimeler: Biyolojik ağ hizalama, biyolojik veritabanı hizalama, çizge 
hizalama, referans tabanlı indeksleme, QNET, Hadoop, ESBiD, en yüksek dereceli
düğüm

Abstract:
It is possible to explain the events occurring inside the cell, the smallest unit in living 
things, by observing biological networks. Similarity-based analysis is one of the 
techniques for biological network analysis. In this context, a database consisting of 
biological networks is aligned with a query network, and the networks having a 
similarity score higher and lower than a predefined cut-off value are separated. The 
exact similarity score of two networks needs to be known in the solution of this 
problem. Unfortunately, because of the NP-complete sub-graph isomorphism 
problem, this is computationally too expensive. Several methods are proposed in the 
literature to solve the graph alignment problem. QNET, which is one of these 
methods, is coded in Java using Hadoop framework in the scope of this thesis. For 
query networks with 7 nodes, Hadoop implementation with 10 machine cluster (18 
cores) achieved 11,42 speedup. 
A new method called ESBiD, taking the "reference based indexing method" 
approach has been developed. Particularly, ESBiD focused on the weaknesses of 
RINQ, another reference based indexing method. To this end, by using heuristics, the 
number of networks in the twilight zone has been reduced by 29,85% with 93,22%
accuracy, the reference network selection strategy has been changed and a new 
technique called "highest degree node" has been proposed in order to align the 
networks in the twilight zone faster. This technique reached 89,74% effectiveness in 
51,14% runtime with respect to the QNET's exact alignment method.

Keywords: Biological network alignment, biological database alignment, graph 
alignment, reference based indexing, QNET, Hadoop, ESBiD, highest degree node