Using genetic algorithm to extract an active subnetwork

Abstract

Son yıllarda, biyoinformatik alanında, hastalıkların davranışlarını anlamak ve hastalıkların tedavisinde kullanılabilecek ilaçların bulunabilmesi için genlerin analizi ve büyük protein-protein etkileşim ağları kullanılmaktadır. Protein-protein etkileşim ağlarının araştırılmasındaki en önemli adım, aktif alt ağların tespitidir. Aktif alt ağlar, belirli bir hastalığa neden olma olasılığı en yüksek olan proteinlerin etkileşimlerinden oluşur. Her protein bir düğüm olarak temsil edilir ve bu düğümün ağırlığı, bu proteinin belirli bir hastalık açısından önemini gösterir. Aktif alt ağ tespitinin temel amacı, en önemli proteinleri içeren bağlı bir alt ağ bulmaktır; dolayısıyla bulunan aktif alt ağ en yüksek puana sahiptir. Bu tezde, yeni bir probleme özgü çaprazlama operatörü, bir yerel arama tekniği ve bir zenginleştirme aşaması kullanarak aktif bir alt ağ bulmak için evrimsel bir algoritma öneriyoruz. Çaprazlama operatörü, her zaman uygun bir çözüm üretecek bağlantılı bir çizge olarak temsil edilen bir yavru oluşturmak için iki bit vektörleri üzerinde temel OR ve AND işlemlerini kullanır. Yerel arama tekniği, alt ağın toplam puanını artırmak için yavrular tarafından temsil edilen alt ağa düğümleri ekler veya bu alt ağdan düğümleri çıkarır. Son olarak zenginleştirme aşamasında, popülasyonun en iyi çözümü daha da iyileştirilir. Farklı özelliklere sahip 10 veri seti üzerinde deneysel çalışmalar yaptık ve sonuçlarımızı literatürdeki sonuçlarla karşılaştırdık. Önerilen algoritma umut verici bir performansa sahiptir, 8 veri setinde ilgili tüm çalışmalardan daha iyi performans gösterirken, algoritmalardan biri 2 tanesinde daha iyi sonuçlar vermektedir.In recent years, in the area of bioinformatics, analysis of genes and large protein-protein interaction networks are considered to understand behavior of diseases and and to develop drug therapy for these diseases. The most important step in the investigation of protein-protein interaction networks is the detection of active subnetworks. Active subnetworks consist of interactions of proteins that are most likely to cause a particular disease. Each protein is represented as a node and the weight of this node denotes the importance of this protein regarding a particular disease. The main objective of active subnetwork detection is to find a connected subnetwork which includes the most important proteins; thus has the highest subnetwork score. In this thesis, we propose an evolutionary algorithm to extract an active subnetwork using a novel problem-specific crossover operator, a local search technique and an enrichment phase. The crossover operator uses basic AND and OR operations on two bit vectors to form an offspring represented as a connected graph, which will always generate a feasible solution. The local search technique either adds or removes nodes from the subnetwork represented by the offspring to increase the overall score of the subnetwork. Finally in the enrichment phase, the best solution of the population is further improved. We conducted experimental studies on 10 datasets with different characteristics and compared our results with those from the literature. The proposed algorithm has promising performance, it outperforms all related studies on 8 datasets, whereas one of the algorithms gives better results in 2 of them.