Home Tsinghua Science and Technology Article
PDF (497.5 KB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript
Open Access

PBNA: An Improved Probabilistic Biological Network Alignment Method

School of Computer Science and Engineering, and also with MOE Key Laboratory of Computer Network and Information Integration, Southeast University, Nanjing 210096, China.
Division of Math and Computer Science, University of South Carolina Upstate, Spartanburg, SC 29303, USA,
Show Author Information

Abstract

Biological network alignment is an important research topic in the field of bioinformatics. Nowadays almost every existing alignment method is designed to solve the deterministic biological network alignment problem. However, it is worth noting that interactions in biological networks, like many other processes in the biological realm, are probabilistic events. Therefore, more accurate and better results can be obtained if biological networks are characterized by probabilistic graphs. This probabilistic information, however, increases difficulties in analyzing networks and only few methods can handle the probabilistic information. Therefore, in this paper, an improved Probabilistic Biological Network Alignment (PBNA) is proposed. Based on IsoRank, PBNA is able to use the probabilistic information. Furthermore, PBNA takes advantages of Contributor and Probability Generating Function (PGF) to improve the accuracy of node similarity value and reduce the computational complexity of random variables in similarity matrix. Experimental results on dataset of the Protein-Protein Interaction (PPI) networks provided by Todor demonstrate that PBNA can produce some alignment results that ignored by the deterministic methods, and produce more biologically meaningful alignment results than IsoRank does in most of the cases based on the Gene Ontology Consistency (GOC) measure. Compared with Prob method, which is designed exactly to solve the probabilistic alignment problem, PBNA can obtain more biologically meaningful mappings in less time.

Keywords

probabilistic biological networknetwork alignmentprotein interaction network

References

[1]
R. Singh, J. Xu, and B. Berger, Global alignment of multiple protein interaction networks with application to functional orthology detection, PNAS, vol. 105, no. 35, pp. 12763-12768, 2008.
Crossref Google Scholar
[2]
X. L. Guo, L. Gao, and X. Chen, Models and algorithms for alignment of biological networks, (in Chinese), Journal of Software, vol. 21, no. 9, pp. 2089-2106, 2010.
Google Scholar
[3]
H. Ogata, W. Fujibuchi, and S. Goto, A heuristic graph comparison algorithm and its application to detect functionally related enzyme clusters, Nucleic Acids Research, vol. 28, no. 20, pp. 4021-4028, 2000.
Crossref Google Scholar
[4]
E. Hirsh and R. Sharan, Identification of conserved protein complexes based on a model of protein network evolution, Bioinformatics, vol. 23, no 2, pp. e170-e176, 2007.
Crossref Google Scholar
[5]
R. Singh, J. Xu, and B. Berger, Pairwise global alignment of protein interaction networks by matching neighborhood topology, in Research in Computational Molecular Biology. Springer Berlin Heidelberg, 2007, pp. 16-31.
[6]
M. Narayanan and R. M. Karp, Comparing protein interaction networks via a graph match-and-split algorithm, Journal of Computational Biology, vol. 14, no. 7, pp. 892-907, 2007.
Crossref Google Scholar
[7]
A. Todor, A. Dobra, and T. Kahveci, Probabilistic biological network alignment, IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol. 10, no. 1, pp. 109-121, 2013.
Crossref Google Scholar
[8]
Z. Liang, M. Xu, M. Teng, and L. Niu, Comparison of protein interaction networks reveals species conservation and divergence, BMC Bioinformatics, vol. 7, no. 1, pp. 457-472, 2006.
Crossref Google Scholar
[9]
A. Chatr-Aryamontri, A. Ceol, L. M. Montecchi, G. Nardelli, M. Schenider, L. Castagnoli, and G. Cesareni, MINT: The molecular interaction database, Nucleic Acids Research, vol. 35, no. s1, pp. 572-574, 2007.
Crossref Google Scholar
[10]
M. Koyuturk, Y. Kim, U. Topkara, S. Subramaniam, W. Szpankowski, and A. Grama, Pairwise alignment of protein interaction networks, Journal of Computational Biology, vol. 13, no. 2, pp. 182-199, 2006.
Crossref Google Scholar
[11]
M. Ashburner, C. A. Ball, J. A. Blake, D. Botstein, and H. Butler, Gene ontology: Tool for the unification of biology, Nat. Genet., vol. 25, no. 1, pp. 25-29, 2000.
Crossref Google Scholar
[12]
W. Tian and N. F. Samatova, Pairwise alignment of interaction networks by fast identification of maximal conserved patterns, Pacific Symposium on Biocomputing, vol. 14, pp. 99-110, 2009.
Google Scholar
[13]
E. Almaas, Biological impacts and context of network theory, The Journal of Experimental Biology, vol. 210, pp. 1548-1558, 2007.
Crossref Google Scholar
[14]
G. W. Klau, A new graph-based method for pairwise global network alignment, BMC Bioinformatics, vol 10, pp. 59-67, 2009.
Crossref Google Scholar
[15]
F. Towfic, M. H. W. Greenlee, and V. Honavar, Aligning biomolecular networks using modular graph kernels, in Algorithms in Bioinformatics. Springer Berlin Heidelberg, 2009, pp. 345-361.
Crossref
[16]
W. Guan, J. Wang, and F. He, The advance in research methods for large-scale protein-protein interactions (in Chinese), Chinese Bulletin of Life Sciences, vol. 18, no. 5, pp. 507-512, 2006.
Google Scholar
[17]
E. Silva and M. P. H. Stumpf, Complex networks and simple models in biology, Journal of The Royal Society Interface, vol. 2, no. 5, pp. 419-430, 2005.
Crossref Google Scholar
[18]
J. Sun, J. Xu, Y. Li, and T. Shi, Analysis and application of large-scale protein-protein interaction data, (in Chinese), Chinese Science Bulletin, vol. 50, no. 19, pp. 2055-2060, 2005.
Crossref Google Scholar
[19]
P. Jancura, J. Heringa, and E. Marchiori, Divide, align and full-search for discovering conserved protein complexes, in Machine Learning and Data Mining in Bioinformatics. Springer Berlin Heidelberg, 2008, pp. 71-82.
[20]
A. E. Aladag and C. Erten, SPINAL: Scalable protein interaction network alignment, Bioinformatics, vol. 29, no. 7, pp. 917-924, 2013.
Crossref Google Scholar
[21]
H. W. Kuhn, The Hungarian method for the assignment problem, Naval Research Logistics Quarterly, vol. 2, nos. 1-2, pp. 83-97, 1955.
Crossref Google Scholar
[22]
M. Kanehisa, S. Goto, S. Kawashima, Y. Okuno, and M. Hattori, The KEGG resource for deciphering the genome, Nucleic Acids Research, vol. 32, no. s1, pp. D277-D280, 2004.
Crossref Google Scholar
Tsinghua Science and Technology
Volume 19 Issue 6,
December 2014
Pages 658-667
DOI: 10.1109/TST.2014.6961034
Cite this article:
Zhao M, Zhong W, He J. PBNA: An Improved Probabilistic Biological Network Alignment Method. Tsinghua Science and Technology, 2014, 19(6): 658-667. https://doi.org/10.1109/TST.2014.6961034
Metrics & Citations  
Article History
Copyright
Return