Message-Passing Based Algorithm for the Global Alignment of Clustered Pairwise Ppi Networks

Abstract

Constrained global network alignments on pairwise protein-protein interaction (PPI) networks involve matchings between two organisms where proteins are grouped together in a great number of clusters, produced by algorithms that seek functionally ortholog ones and these organisms are represented as graphs. Unlike balanced global network alignments, this has not gained much popularity in bioinformatics. Only a few methods have been proposed thus far; by assuming specific structures of networks including the clusters themselves and the density of the PPI networks are not too large, then optimal alignments can be encountered. Here, we introduce a general-purpose algorithm that is able to work on any kind of graph structures while taking advantage of the message-passing method, based on propagation between clusters. When these graphs satisfy conditions like continuous interaction connectivity of proteins across all neighbored clusters, in addition to previous explanations, the optimality of alignments can still be achieved. Convergence of the cluster network can occur at the point where the maximum number of conserved interactions are detected. Many experiments were made with balanced GNA algorithms and our algorithm may find more conservations and more importantly, alignments have higher biological quality than other ones in various instances.

İkili protein-protein etkileşim ağları üzerinde kısıtlanmış global ağ hizalaması, işlevsel olarak ortak proteinleri arayan algoritmalar tarafından üretilen çok sayıdaki küme içerisinde gruplanmış olan iki organizmanın proteinleri arasında en iyi eşleşmeleri içerir ve bu organizmalar graph yapısı olarak gösterilirler. Dengeli global ağ hizalamanın aksine biyoenformatik alanında fazla popülerlik kazanmamıştır. Şu ana kadar sadece birkaç yöntem önerilmiştir; kümelerin kendileri de dahil özel ağ yapıları ve protein-protein etkileşim ağlarının yoğunluğunun çok büyük olmadığı varsayılırsa, en iyi hizalamalarla karşılaşılabilir. Burada, her tür graph yapısı üzerinde çalışabilen ve kümeler arasında yayılıma dayalı mesaj verme yönteminden faydalanan genel amaçlı bir algoritmayı sunuyoruz. Bu graphlar önceki varsayımlarla beraber birbirine komşu tüm kümeler boyunca proteinlerin devamlı etkileşim bağlantıları olması gibi koşulları sağlarlarsa, hizalamaların en iyisine halen ulaşılabilir. En çok sayıda korunmuş etkileşimlerin bulunduğu noktada küme ağının yakınsaması meydana gelebilir. Dengeli global ağ hizalama algoritmaları ile birçok deney yapılmıştır ve bizim algoritmamız diğerlerinden daha fazla korunmuş etkileşimi bulabilir ve daha da önemlisi, değişik örneklerde hizalamalar daha yüksek biyolojik kaliteye sahip olabilir.