Global alignment of metabolic pathways and protein-protein interaction networks

Abstract

Metabolic pathways and protein interaction networks are essential at almost every function for living organisms. Simply, while reactions produce life energy within cells, protein interaction networks provide biological functions. Also, abnormal reactions or interactions cause various disorders. Thus, in bioinformatics, most of the studies are based on these networks in order to find hopeful results for these disorders and biological challenges. Solving alignment problem is one of these studies such that it tries to find similar reactions, proteins or functions. In this thesis, we focus on that problem within both metabolic pathways and protein interaction networks. Firstly, we propose a constrained alignment algorithm, CAMPways, for one-to-many alignment of metabolic pathways and we extend the framework, CAPPI, for one-to-one protein interaction network alignment with necessary changes. Afterwards, we provide the computational intractability of the problem and finally we compare our algorithm with different algorithms on actual metabolic pathways and protein interaction networks.

Metabolik yolaklar ve protein etkileşim ağları, yaşayan canlıların neredeyse tüm fonksiyonlarında hayati önem taşımaktadır. En basit haliyle, reaksiyonlar hücre içinde yaşam enerjisi üretirken, protein etkileşim ağları biyolojik fonksiyonların gerçekleşmesini sağlamaktadır. Ayrıca, normal olmayan reaksiyonlar ya da etkileşimler çeşitli hastalıklara neden olmaktadır. Bu nedenle, biyoinformatik alanındaki birçok çalışma, bu hastalıklara ve biyolojide çözülmesi gereken sorunlara umut verici sonuçlar alabilmek amacıyla, bu ağlara dayanmaktadır. Hizalama probleminin çözülmesi, bu çalışmalardan biridir ve bu problem, benzer reaksiyonları, proteinleri ya da fonksiyonları bulmaya çalışır. Bu tez kapsamında, hem metabolik yolaklar hem de protein etkileşim ağları için hizalama problemi ele alınmaktadır. Öncelikle metabolik yolakların bire-çok hizalanması için kısıtlandırılmış bir algoritma (CAMPways) sunulmakta, daha sonra bu algoritma protein etkileşim ağlarının bire-bir hizalanması için geliştirilmekte (CAPPI) ve gerekli değişiklikler uygulanmaktadır. Problemin işlemsel karmaşıklığı verilip, gerçek veriler üzerinde diğer algoritmalar ile karşılaştırmaları yapılmaktadır.