Search

Binary classification is the process of labeling the members of a given data set on the basis of whether they have some property or not. To train a binary classifier, normally one needs two sets of examples from each group, usually named as positive and negative examples. However, in some domains, negative examples are either hard to obtain or even not available at all. In these problems, data consist of positive and unlabeled examples. An example to this kind of problems is derivation of protein-protein networks. Biological processes in a living organism depend on proteins and mostly interactions of proteins. It is important to determine which proteins interact to understand how an organism survives. While it is possible to derive by experiments that two proteins interact with each other, it is much harder to conclude that they do not. Even if we do not observe the interaction of two proteins during an experiment, they may interact in a different time or condition. In this thesis we first present a survey of algorithms which can handle such problems, and then provide a comparison of some of these algorithms on the protein-protein interaction derivation problem by using the available (positive) interaction information. Thus we identify which algorithms can be used or have potential to be used for deriving protein-protein interaction networks., Bir veri kümesindeki örneklerin belli bir özelliğe sahip olup olmayışlarına göre etiketlendirilmeleri işlemine ikili sınıflandırma adı verilir. Bir ikili sınıflandırıcı eğitebilmek için, genel yaklaşımda, hem pozitif hem de negatif örnekler içeren bir eğitim verisine ihtiyaç duyulur. Ancak bazı çalışma alanlarında negatif örneklerin elde edilmesi zor, hatta imkansız olabilir. Bu durumlarda veri kümesi sadece pozitif örnekler ve üye oldukları sınıfların belirlenmesi hedeflenen etiketlenmemiş örneklerden oluşur. Bu tür problemlere bir örnek protein-protein etkileşim ağlarının tahminidir. Bir canlı vücudunda hayati işlemlerin devamlılığı proteinlerin çalışmasına bağlıdır ve proteinler bu işlemler sırasında birbirleriyle etkileşime girerler. Hangi proteinlerin birbirleriyle etkileştiğinin bilinmesi tıbbi açıdan önemli bir bilgidir. Proteinlerin etkileştiği laboratuar deneyleri ile tespit edilebilirken, aksi durum kesin bir şekilde belirlenemez. Deneyler sırasında bir protein çiftinin etkileştiğine şahit olunmaması, bu çiftin başka bir zaman ve durumda etkileşmeyeceğinin kanıtı olamaz. Bu çalışmamızda negatif eğitim verisinin mevcut olmadığı bu durumlarda kullanılabilinecek olan algoritmaları özetledik ve bu algoritmaların bir kısmını protein-protein etkileşimlerinin tahmininde kullanarak test edip karşılaştırdık. Böylece protein-protein etkileşim ağlarının tahmininde kullanılabilecek veya bu işlem için ümit vadeden algoritmaları belirledik.

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 ., 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.

Binary classification is the process of labeling the members of a given data set on the basis of whether they have some property or not. To train a binary classifier, normally one needs two sets of examples from each group, usually named as positive and negative examples. However, in some domains, negative examples are either hard to obtain or even not available at all. In these problems, data consist of positive and unlabeled examples. An example to this kind of problems is derivation of protein-protein networks. Biological processes in a living organism depend on proteins and mostly interactions of proteins. It is important to determine which proteins interact to understand how an organism survives. While it is possible to derive by experiments that two proteins interact with each other, it is much harder to conclude that they do not. Even if we do not observe the interaction of two proteins during an experiment, they may interact in a different time or condition. In this thesis we first present a survey of algorithms which can handle such problems, and then provide a comparison of some of these algorithms on the protein-protein interaction derivation problem by using the available (positive) interaction information. Thus we identify which algorithms can be used or have potential to be used for deriving protein-protein interaction networks., Bir veri kümesindeki örneklerin belli bir özelliğe sahip olup olmayışlarına göre etiketlendirilmeleri işlemine ikili sınıflandırma adı verilir. Bir ikili sınıflandırıcı eğitebilmek için, genel yaklaşımda, hem pozitif hem de negatif örnekler içeren bir eğitim verisine ihtiyaç duyulur. Ancak bazı çalışma alanlarında negatif örneklerin elde edilmesi zor, hatta imkansız olabilir. Bu durumlarda veri kümesi sadece pozitif örnekler ve üye oldukları sınıfların belirlenmesi hedeflenen etiketlenmemiş örneklerden oluşur. Bu tür problemlere bir örnek protein-protein etkileşim ağlarının tahminidir. Bir canlı vücudunda hayati işlemlerin devamlılığı proteinlerin çalışmasına bağlıdır ve proteinler bu işlemler sırasında birbirleriyle etkileşime girerler. Hangi proteinlerin birbirleriyle etkileştiğinin bilinmesi tıbbi açıdan önemli bir bilgidir. Proteinlerin etkileştiği laboratuar deneyleri ile tespit edilebilirken, aksi durum kesin bir şekilde belirlenemez. Deneyler sırasında bir protein çiftinin etkileştiğine şahit olunmaması, bu çiftin başka bir zaman ve durumda etkileşmeyeceğinin kanıtı olamaz. Bu çalışmamızda negatif eğitim verisinin mevcut olmadığı bu durumlarda kullanılabilinecek olan algoritmaları özetledik ve bu algoritmaların bir kısmını protein-protein etkileşimlerinin tahmininde kullanarak test edip karşılaştırdık. Böylece protein-protein etkileşim ağlarının tahmininde kullanılabilecek veya bu işlem için ümit vadeden algoritmaları belirledik.

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 ., 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.