Global many- to - many aligment of multiple protein-protein interaction networks

Abstract

Proteins are essential parts of organisms and almost every biological process within a living cell is mediated by proteins and their interactions. Due to such importance, proteins are at the core of many researches in systems biology and evolutionary biology. In particular, defining the function of a protein and identfying functionally orthologous proteins are crucially important in many research areas and precise function of a protein can only be defined by biochemical and structural studies. However, many computational methods are also developed for such purposes and they use the sequence and interaction data of proteins since it provides a presumption about the chemical structure of a protein. For example, network alignment studies aims to find clusters of functionally related proteins across given protein interaction networks usually by implementing the given networks as graphs and employing some graph theoretical approaches. In this thesis, we focused on the problem of global many-to-many alignment of multiple protein-protein interaction networks. We define the problem as an optimization problem and this is the first combinatorial definition that is given for the problem in the literature. Then, we prove the computational intractability of this problem and we propose a new heurictic algorithm for the solution. We test the proposed algorithm BEAMS on both actual and synthetic PPI networks and it outperforms the existing algorithms, that serve at similar purpose, in terms of many evaluation aspects.Proteinler canlı organizmaların temel yapıtaşlarını oluşturur ve hücreler içerisindeki birçok biyolojik süreci düzenlerler. Bu büyük önemleri nedeniyle de sistem biyolojisi ve evrimsel biyoloji alanlarında birçok araştırmanın odağı halindedirler. Özellikle proteinlerin fonksiyonlarının tanımlanması ve fonksiyonel olarak benzer proteinlerin gruplanması birçok araştırma alanı için büyük önem taşımaktadır. Fakat bir proteinin kesin fonksiyonu ancak biyokimyasal ve yapısal analizlerle bulunabilmektedir. Bununla beraber proteinlerin dizilim ve etkileşim bilgilerini kullanarak bu amaçlara hizmet eden hesapsal yöntemler de geliştirilmektedir. Örneğin ağ hizalama çalışmaları bunlardan biridir ve verilen protein ağları içerisinden fonksiyonel olarak birbirine benzeyen proteinleri kümelemeyi amaçlar. Bu çalışmalar genellikle verilen ağların çizgeler olarak tanımlanmasını ve bu çizgeler üzerinde çeşitli çizge teorik yaklaşımlar uygulanmasını içerirler. Bu tez kapsamında ise birden çok protein ağının çoka çok olarak hizalanması problemi ele alınmaktadır. Bu tez ile bu hizalama problemi bir optimizasyon problemi olarak tanımlanmakta ve bu tanım bu problem için literatürde verilmiş olan ilk kombinatöryel tanımdır. Daha sonra bu problemin işlemsel karmaşıklığı analiz edilmekte ve problemin çözümü için bir buluşsal algoritma önerilmektedir. Sunulmuş olan BEAMS algoritmasının hem gerçek hem de sentetik ağlar üzerindeki test sonuçları sunulmakta ve bu sonuçlar literatürde aynı amaca hizmet eden diğer algoritmalar ile karşılaştırıldığında, BEAMS algoritmasının birçok açıdan diğer benzer algoritmalardan daha etkili çalıştığı görülmektedir.