Karmaşık ağlardaki modül yapılarının ve anlamlı alt-ağların tespiti
Detection of module structures and significant sub-networks in complex networks
Yazar: YILMAZ ATAY
Danışman: DOÇ. DR. HALİFE KODAZ
Selçuk Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2018
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Anlambilimsel, biyolojik, ekolojik, medikal, sosyal, telekomünikasyon ve ulaşım ağları gibi çok çeşitli alanlarda mevcut olan karmaşık ağ sistemleri ortaya çıkarılabilecek oldukça önemli bilgiler barındırır. Bu tür gerçek ağlardaki milyonlarca nesnenin ve etkileşimin analizi de bir o kadar zordur. Bu noktada fizik, istatistik ve matematik gibi temel bilimlerin yanında bilgisayar bilimleri, biyoinformatik, mühendislik, sosyal ve teknolojik alanlardaki disiplinlerle dinamik olarak sürekli etkileşim halinde olan ağ bilimi kavramı ön plana çıkmaktadır. Farklı alanlardan çeşitli yöntemlere sahip olan bu çok disiplinli bilim dalında gerçek-dünya sistemlerinin modellenmesinde genellikle çizgeler kullanılır. Böylece temelde çizge teorisi ve bilgisayar bilimleri yardımıyla gerçek ağ yapılarındaki gizli ve önemli bilgiler çeşitli yöntemler kullanılarak keşfedilebilmektedir. Bu bilgilerin bilgisayar sistemleri yardımıyla hızlı bir şekilde analiz edilerek ortaya çıkarılabilmesi amacıyla son yıllarda çeşitli çalışmalar yapılmakta ve farklı ağ analiz teknikleri önerilmektedir. Bu doktora tez çalışmasında, gerçek-dünya ağlarından anlamlı bilgilerin ortaya çıkarılmasında kullanılan iki farklı ağ analiz konusuna odaklanılmıştır. Bunlardan ilki, ağ modül ya da topluluk tespiti problemi hakkındadır. İkinci ise klinik kanser verileri ve bunlarla ilişkili biyolojik ağların analizleri hakkındadır. Tezdeki ilk çalışma konusunda, gerçek sistemleri oluşturan nesnelerin fiziksel etkileşim yoğunluklarına ya da fonksiyonel ilişkilerine göre modül yapılarının tanımlanması amaçlanır. Bu problemde kullanılan ağların oldukça karmaşık yapılarda olması ve ortaya çıkarılacak anlamlı bilgilerin ancak yüksek hesaplama maliyeti ile elde edilebilmesi gibi kısıtlamalar sebebiyle klasik ve sezgisel yöntemler yerine bu tez çalışmasında çeşitli metasezgisel yaklaşımlar kullanılmıştır. Bu amaçla sekiz farklı metasezgisel optimizasyon algoritması orijinal mekanizmalarıyla ya da çeşitli hibrit yaklaşımlarla bu probleme adapte edilmiştir. Bu algoritmalar iki farklı model ile üretilen sekiz farklı yapay ağda test edilmiştir. Ayrıca algoritmaların performanslarının gerçek sistemler üzerinde de karşılaştırılabilmesi amacıyla genellikle literatürde tercih edilen altı gerçek-dünya ağı kullanılmıştır. Buradaki karşılaştırmalarda nesnel değerlendirmeler için istatistiksel analizler yapılmıştır. Tüm testlerin sonuçlarına göre genellikle en başarılı sonuçlara ulaşan 3pHybrid algoritması, bu problemle ilgili gerçekleştirilen sonraki deneylerde test yöntemi olarak kullanılmıştır. Bahsi geçen testlerin ilkinde, ağ modül tespitinde çoğunlukla tercih edilen ve iyi bilinen on farklı amaç fonksiyonundan genellikle en uygun sonuçları veren fonksiyonun tespitine çalışılmıştır. Bu testlerde biyoloji, gen, protein, radar, sosyal ve tıbbi alanlardan temin edilen bilgi ağları kullanılmıştır. Bu ağlar için en uygun modül yapıları bilinmektedir. Böylece test edilen amaç fonksiyonları ile elde edilen ağ modüllerinin kaliteleri bu tez çalışmasında kullanılan altı farklı küme değerlendirme ölçütü ve gerçek ağ modül yapıları ile test edilmiştir. Bunların sonuçlarına göre genel başarı sıralamaları dikkate alındığında, genellikle en başarılı küme değerlendirme sonuçlarına modülerlik fonksiyonu ile ulaşılmış olsa da buna yakın sonuçlara ulaşan diğer fonksiyonların da bazı durumlarda tercih edilmesinin uygun olacağı sonucuna varılmıştır. Çünkü bazı test ağlarında modülerlik amaç fonksiyonu ile daha az kaliteli ağ modüllerinin tespit edildiği gözlemlenmiştir. Yine de ortalama değerlendirme sonuçları açısından bu fonksiyon ile genellikle en iyi ortalama sonuçlara ulaşıldığından sonraki testlerde uygunluk kriteri olarak aynı fonksiyon kullanılmıştır. Bu problemle ilgili en son çalışmada, genel olarak en iyi sonuçları sunan algoritmanın uygunluk kriteri olarak seçilen ve çoğunlukla en kaliteli ağ modül yapılarını sunan modülerlik amaç fonksiyonu ile elde edilen nihai skorlar literatürdeki diğer algoritmaların skorları ile karşılaştırılmıştır. Bu testlerde 21 farklı algoritma, 13 adet gerçek dünya ağında mevcut olan skorlara göre karşılaştırılmıştır. Tüm sonuçlara göre bu ağlardan 11'inde en yüksek skorlara tez çalışmasında önerilen algoritmalardan biri olan 3pHybrid algoritması ile ulaşılmıştır.
	Bu tezin ikinci çalışma konusunda, klinik kanser verileri ve karmaşık biyolojik ağların sağkalım analizleri ile birlikte değerlendirilmesiyle genlerin fonksiyonel etkileşimlerinden oluşan anlamlı alt-ağların tespitine odaklanılmıştır. Buradaki analizler sağkalım süreleri ile maksimum ilişkili olduğu düşünülen/varsayılan gen listelerinin ortaya çıkarılmasını kapsar. Burada kullanılan tüm genler özellikle kanser hastalıklarında çokça üzerinde durulan kopya sayısı değişikliklerini içerir. Genlerdeki bu değişikliklerle ilgili sunulan problem, ilk kez bu çalışmada anlatılmıştır. Burada, hastalıklarda ciddi klinik etkilere sahip olabilecek kopya sayısı değişikliklerinin temel alınmasıyla hastaların yaşam—sağkalım sürelerine etki edebilecek gen gruplarının ortaya çıkarılması amaçlanmıştır. Bununla ilgili gerçekleştirilen deneylerde, beş farklı kanser türü için temin edilen klinik hasta bilgileri ile bu hastaların sahip oldukları gen-gen etkileşim ağları kullanılmıştır. İlgili tez bölümünde bu problemin çözümü amacıyla dinamik programlama ve genetik algoritma temelli iki farklı teknik önerilmiştir. Burada uygunluk fonksiyonu olarak sağkalım analizinde önemli olan log-rank istatistik ölçütü kullanılmıştır. Önerilen iki yöntemin skorlarına ve çalışma sürelerine göre performansları birbirleriyle kıyaslanmıştır. Testler için gerçek verilerin kullanılmasının yanında rastsal olarak üretilen yapay veriler de kullanılmıştır. Bu problemle ilgili tüm deneyler sonunda kaydedilen genlerden bazılarının ilişkili oldukları hastalıkların ya da biyolojik bozuklukların/değişikliklerin listeleri deneysel çalışmalar bölümünde verilmiştir. Son olarak, hem birinci hem de ikinci problemin birlikte dikkate alınmasıyla gen-hastalık ilişkileri ayrıntılı olarak analiz edilmiştir. Bu en son ve yeni problemde, aynı modüllerde bulunan ve ilgili kanser türlerindeki sağkalım analizlerinde en fazla etkili oldukları kabul edilen genlerin tespitine odaklanılmıştır. Bu amaçla düğümler arası etkileşimlerin çok karmaşık olduğu biyolojik ağlardaki modül yapılarının tespiti problemi ile sağkalım analizi probleminin bir arada değerlendirildiği tüm deneysel sonuçlar ilgili eklerde ve ek dosyalarda sunulmuştur.

Abstract:
Complex network systems, which can be exist in a wide range of fields such as semantic, biological, ecological, medical, social, telecommunication and transport networks, contain considerable information that can be uncovered. In such real-networks, the analysis of millions of objects and their interactions is so difficult. At this point, the concept of network science, which constantly is in interaction dynamically with the fundamental disciplines such as physics, statistics and mathematics, as well as disciplines in computer science, bioinformatics, engineering, social and technological fields, comes into prominence. In this multidisciplinary science, which has various methods from different fields, the graphs are generally used in modeling real-world systems. Thus, basically, with the help of graph theory and computer science, hidden and valuable information in real network structures can be discovered using various methods. In recent years, numerous studies have been carried out and different network analysis techniques have been proposed to analyze and to reveal this information with the help of computer systems. In this doctoral thesis, it has been focused on two different network analysis topics that are used to reveal meaningful information from real-world networks. The first of these is about network module or community detection problem. The second is about the analysis of clinical cancer data and related biological networks. In the first study in the thesis, it is aimed to define the module structures according to the physical interaction intensities or functional relations of the objects forming the real systems. Because of the complexity of the networks used in this problem, and the limitations such as meaningful information to be revealed that can be only obtained with high computational cost, various metaheuristic approaches have been used instead of classical and intuitive methods in this thesis. For this purpose, eight metaheuristic optimization algorithms have been adapted to this problem with the original mechanisms or with various hybrid approaches. These algorithms have been tested in eight different random networks produced with two different models. In addition, six real-world networks, which are generally preferred in the literature, have been used to compare the performance of algorithms on real-systems. In these comparisons, the statistical analyzes have been carried out for objective evaluations. According to the results of all the tests, the 3pHybrid algorithm, which usually achieves the most successful results, has been used as a test method in subsequent experiments on this problem. In the first of the aforementioned tests, it has been studied to determine the function that gives generally the most appropriate results, from the most commonly preferred, and well-known ten different objective functions in network module detection. In these tests, information networks are used which are obtained from biology, gene, protein, radar, social and medical fields. The most suitable module structures for these networks are known. Thus, the qualities of network modules obtained with the objective functions tested were examined with six different cluster evaluation criteria and real network module structures used in this thesis study. When the rankings of general success are taken into consideration, it is generally concluded that the most successful cluster evaluation results are achieved with modularity function, but other functions that reach comparable results can be preferred in some cases. Because in some test networks it has been observed to obtained less quality network modules with the modularity objective function. However, the same function was used as the eligibility criterion in subsequent tests, since it usually has been achieved the best average results in terms of average evaluation results with this function. In the final study with this problem, the final scores obtained with the modularity objective function, which is selected as the eligibility criterion of the algorithm that provides the best overall results, and which mostly provides the best quality network module structures, are compared with the scores of other algorithms in the literature. In these tests, 21 different algorithms were compared according to the scores available on 13 real-world networks. According to all the results, the highest scores in 11 of these networks were reached with the 3pHybrid algorithm, one of the algorithms proposed in this study.
	In the second study of this thesis, it has been focused on the identification of meaningful sub-networks consisting of functional interactions of genes by evaluating clinical cancer data and survival analysis of complex biological networks. These analyzes include the detection of sub-genomic networks that are assumed/considered to be most relevant to survival times. All genes contain copy number alterations which are particularly important in cancer diseases. The problem with these changes in the genes is presented for the first time in this thesis. Here, it is aimed to reveal gene groups that can affect the life-survival times of patients based on copy number alterations which can have serious clinical effects in diseases. In the related experiments, the clinical patient information provided for five different types of cancer and the gene-gene interaction networks possessed by these patients have been used. Two different methods based on dynamic programming and genetic algorithm have been proposed to solve this problem in the related section of thesis. Here, the log-rank statistical criterion, which is important in survival analysis, is used as a fitness function. The performances of the two proposed methods have been compared with each other according to their scores and their execution time. In addition to the used real data for tests, randomly generated artificial data have been also used in the experiments. The lists of diseases or biological disorders/changes which some of the recorded genes are related at the end of all experiments related to this problem are given in the section of experimental studies. Finally, gene-disease relationships have been analyzed in detail, taking both the first and second problems together. In this last and new problem, it has been focused on identification of genes found in the same network modules that are considered to be most effective in the survival analysis of the related cancer types. For this purpose, all the experimental results in which the problem of detection of module structures in biological networks where interactions between nodes are very complex, and the survival analysis problem are evaluated together, have been presented in the related appendices and in the supplementary files.