Biyolojik çizge madenciliği: Alt çizge örüntülerinin bulunması ve etkileşim tahmininde kullanılması
Biological graph mining: Discovery of subgraph paterns and their utilization in interaction prediction
Yazar: MEHMET EMİN TURANALP
Danışman: PROF. DR. SAADETDİN HERDEM
Selçuk Üniversitesi / Fen Bilimleri Enstitüsü / Elektrik-Elektronik Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2008
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Giderek artan sayıda organizmaya ait genom-ölçekli gen ve/veya protein ağlarının ortaya çıkmasına bağlı olarak, son yıllarda önemli ölçüde araştırma çabası biyolojik ağların analizine yöneltilmiştir. Bir protein-protein etkileşim (PPE) ağı, bir organizmanın etkileşen protein çiftlerinin yönsüz olarak bağlandığı bir çeşit biyolojik ağdır. Yönsüz bağlantı ağlarında örüntü bulmanın zorluğundan ötürü, PPE ağlarının analizi için geliştirilen tekniklerin çoğu aralarındaki etkileşimin yoğun olduğu proteinlerin oluşturduğu kümeleri bulmayı veya lineer etkileşim patikalarını bulmayı hedeflemişlerdir. Bu çalışmada, PPE ağındaki proteinler tekil olmayan Gen Ontolojisi açıklamalarıyla etiketlenmiş ve bu ağda sık görülen etkileşim örüntüleri ortaya çıkarılmıştır. Bulduğumuz örüntüler küme bulma algoritmaları tarafından bulunamayan ve herhangi bir topolojiye sahip olabilecek çizgelerdir.Bu çalışmada, PPISpan adını verdiğimiz ve gSpan olarak bilinen bir alt-çizge bulma metodundan PPE ağlarına özgü olarak uyarladığımız yeni bir sık geçen örüntü bulma tekniğini öneriyoruz. Bu teknik S. cerevisiae (Hamur Mayası) organizmasının PPE ağına uygulanmış ve sık görülen etkileşim örüntüleri belirlenmiştir. Bulgularımız PPE ağlarındaki modüler organizasyonun biyolojik içyüzünü kavramak için faydalı olabilecektir.Genom ölçekli ve çok miktarda çıktı veren deneyler yardımıyla bol miktarda protein-protein etkileşim verisi ortaya çıkarılmış olmasına rağmen, bu veri setleri hala tamam değildir ve çelişkilerle doludur. Bu çalışmada, yanlış eksi etkileşimleri tahmin ederek bu veri setlerinin kalitesini artırmak amaçlanmıştır. Bunun için PPE ağında sık bulunan örüntüler kullanılmıştır. PPE Ağında olmayan ama aday bir etkileşimin eklenmesiyle birlikte, var olan bir örüntünün yeni bir gömüntüsü ortaya çıkıyor ise, bu aday etkileşim için bir oy olarak kabul edimiştir. Bütün ağ taranarak, ağdaki bütün adayların hangi örüntülerden oy aldıkları belirlenmiştir. Adayların aldıkları oylar ve örüntülerin belirgin özelliklerine bağlı olan bir güven ölçütü belirlenmiştir. Bu ölçüt kullanılarak, girdi olarak verilmiş herhangi bir etiketli ağda etkileşimleri kestiren bir algoritma geliştirilmiştir. GO terimleri ile etiketlenmiş Hamur Mayası organizması ağı üzerinde yapılan deneylerle, geliştirilen algoritmanın pratikte etkili ve iyi bir kestirim performansına sahip olduğu gösterilmiştir.

Abstract:
In recent years, a considerable amount of research effort has been directed to the analysis of biological networks with the availability of genome-scale networks of genes and/or proteins of an increasing number of organisms. A protein-protein interaction (PPI) network is a particular type of a biological network, in which physically interacting pairs of proteins of an organism are connected with undirected links. Due to the difficulty of identifying patterns in an undirected network, most of the techniques developed for analysis of PPI networks have targeted finding clusters of highly interacting proteins or linear paths of interaction. In this work, we utilize the Gene Ontology annotations to assign non-unique labels to proteins of a PPI network, and identify frequently occurring interaction patterns. We map known functional annotations of proteins onto a PPI network in order to identify frequently occurring interaction patterns in the functional space. The patterns we identify are not necessarily clique-like highly interacting protein clusters; therefore, are ignored by cluster detection techniques.We propose a new frequent pattern identification technique, PPISpan, adapted specifically for PPI networks from a well-known frequent subgraph identification method, gSpan. We have applied PPISpan on protein-protein interaction networks of S. cerevisiae (Baker?s Yeast) and identified frequently occurring interaction patterns, providing further biological insights into the modular organization of protein-protein interaction networks.Although large amounts of protein-protein interaction (PPI) data have been identified using various genome-scale and high-throughput methods, these data sets are often incomplete and contradictory. We describe a method for improving the quality of these datasets by predicting false negative interactions, using common network motifs (interaction patterns) found in PPI networks. A motif votes for a missing interaction if an embedding of this motif can be realized with the addition of the missing interaction to the PPI network. We make a search in a given PPI network for interaction candidates that complete found motifs and rank them using a confidence measure based on motif votes and distinctive features of motifs such as z-scores and number of edges. We formulate a generic algorithm to apply this method to any labeled large-scale network. Our experiments on yeast PPI network labeled with GO terms indicate that the algorithm is efficient in practice and has good predictive performance.