微信服务号

微信订阅号

2025-4-15- 3
Home > Archive>Volume 21, Issue 9, 2010 >2089-2106
PDF HTML XML Export Cite reminder
Models and Algorithms for Alignment of Biological Networks
Author:
Affiliation:

  • Article
    • | |
  • Metrics
    • |
  • Reference [95]
    • |
  • Related [20]
    • | | |
  • Comments
    Abstract:

    Biological network alignment is an important approach in the study of organisms’ structure, function and evolution. In this review, the recent studies in the field of biological network alignment are surveyed. First, a definition of biological network alignment is defined formally. Secondly, the methods for alignment are reviewed and described into three categories according to their mathematical properties. Some models and algorithms in every category are analyzed comprehensively and comparably. Next, tools for alignment are listed and analyzed. In the end, some applications and key problems in the field are highlighted, as well as the future progress of biological network alignment.

    Reference
    [1] Uetz P, Giot L, Cangney G, Mansfield TA, Judson RS, Knight JR, Lockshon D, Narayan V, Srinivasan M, Pochart P, Qureshi- Emili A, Li Y, Godwin B, Conover D, Kalbfleisch T, Vijayadamodar G, Yang MJ, Johnston M, Fields S, Rothberg JM. A comprehensive analysis of protein-protein interactions in Saccharomyces cerevisiae. Nature, 2000,403:623-627.
    [2] Stelzl U, Worm U, Lalowski M, Haenig C, Brembeck FH, Goehler H, Stroedicke M, Zenkner M, Schoenherr A, Koeppen S, Timm J, Mintzlaff S, Abraham C, Bock N, Kietzmann S, Goedde A, Toks?z E, Droege A, Krobitsch S, Korn B, Birchmeier W, Lehrach H, Wanker EE. A human protein-protein interaction network: A resource for annotating the proteome. Cell, 2005,122:957-968.
    [3] Ito T, Chiba T, Ozawa R, Yoshida M, Hattori M, Sakaki Y. A comprehensive two-hybrid analysis to explore the yeast protein interactome. Proceedings of the National Academy of Sciences, 2001,98:4569-4574. [doi: 10.1073/pnas.061034498]
    [4] Ho Y, Gruhler A, Heilbut A, Bader GD, Moore L, Adams SL, Millar A, Taylor P, Bennett K, Boutilier K, Yang L, Wolting C, Donaldson I, Schandorff S, Shewnarane J, Vo M, Taggart J, Goudreault M, Muskat B, Alfarano C, Dewar D, Lin Z, Michalickova K, Willems AR, Sassi H, Nielsen PA, Rasmussen KJ, Andersen JR, Johansen LE, Hansen LH, Jespersen H, Podtelejnikov A, Nielsen E, Crawford J, Poulsen V, S?rensen BD, Matthiesen J, Hendrickson RC, Gleeson F, Pawson T, Moran MF, Durocher D, Mann M, Hogue CW, Figeys D, Tyers M. System identification of protein complexes in Saccharomyces cerevisiae by mass spectrometry. Nature, 2002,415:180-183.
    [5] Iyer VR, Horak CE, Scafe CS, Botstein D, Snyder M, Brown PO. Genomic binding sites of the yeast cell-cycle transcription factors SBF and MBF. Nature, 2001,409:533-538. [doi: 10.1038/35054095]
    [6] Ren B, Robert F, Wyrick JJ, Aparicio O, Jennings EG, Simon I, Zeitlinger J, Schreiber J, Hannett N, Kanin E, Volkert TL, Wilson CJ, Bell SP, Young RA. Genome-Wide location and function of DNA binding proteins. Science, 2000,290:2306-2309. [doi: 10.1126/science.290.5500.2306]
    [7] Cheng YS, Liu JY. Tandem affinity purification technique and its application in proteomics. Progress in Biochemistry and Biophysics, 2004,31(4):379-383 (in Chinese with English abstract).
    [8] Gavin AC, Boèsche M, Krause R, Grandi P, Marzioch M, Bauer A, Schultz J, Rick JM, Michon AM, Cruciat CM, Remor M, Hoèfert C, Schelder M, Brajenovic M, Ruffner H, Merino A, Klein K, Hudak M, Dickson D, Rudi T, Gnau V, Bauch A, Sonja B, Huhse B, Leutwein C, Heurtier MA, Copley RR, Edelmann A, Querfurth E, Rybin V, Drewes G, Raida M, Bouwmeester T, Bork P, Seraphin B, Kuster B, Neubauer G, Furga GS. Functional organization of the yeast proteome by systematic analysis of protein complexes. Nature, 2002,415:141-147. [doi: 10.1038/415141a]
    [9] Liu KD, Zhao JL. Progress of protein chip technology. China Biotechnology, 2004,24(12):48-52,58 (in Chinese with English abstract).
    [10] Li M, Zhou ZC. Protein chip. Chemistry of Life, 2001,21(2):156-157 (in Chinese).
    [11] Zhong CY, Peng R, Peng JX, Hong HZ. Protein chip technology. Biotechnology Bulletin, 2004,2:34-37 (in Chinese with English abstract).
    [12] Yang HY, Ying WT, Qian XH. Current progress in proteome. Progress in Natural Science, 2002,12(1):13-17 (in Chinese).
    [13] Ma XJ, Hu R, Lü H, Wei KK, Zhang LL, Xue SX, Hou YD. Transformation of human interferon a1c/86D with phage display. Science in China (Series C), 1999,29(2):209-216 (in Chinese with English abstract).
    [14] Peri S, Navarro JD, Amanchy R, Kristiansen TZ, Jonnalagadda CK, Surendranath V, Niranjan V, Muthusamy B, Gandhi TKB, Gronborg M, Ibarrola N, Deshpande N, Shanker K, Shivashankar HN, Rashmi BP, Ramya MA, Zhao Z, Chandrika KN, Padma N, Harsha HC, Yatish AJ, Kavitha MP, Menezes M, Choudhury DR, Suresh S, Ghosh N, Saravana R, Chandran S, Krishna S, Joy M, Anand SK, Madavan V, Joseph A, Wong GW, Schiemann WP, Constantinescu SN, Huang L, Khosravi-Far R, Steen H, Tewari M, Ghaffari S, Blobe GC, Dang CV, Garcia JGN, Pevsner J, Jensen ON, Roepstorff P, Deshpande KS, Chinnaiyan AM, Hamosh A, Chakravarti A, Pandey A. Development of human protein reference database as an initial platform for approaching systems biology in humans. Genome Research, 2003,13:2363-2371. [doi: 10.1101/gr.1680803]
    [15] Sharan R, Ideker T. Modeling cellular machinery through biological network comparison. Nature Biotechnology, 2006,24(4): 427-433. [doi: 10.1038/nbt1196]
    [16] Almaas E. Biological impacts and context of network theory. The Journal of Experimental Biology, 2007,210:1548-1558. [doi: 10.1242/jeb.003731]
    [17] Silva E, Stumpf MPH. Complex networks and simple models in biology. Journal of The Royal Society Interface, 2005,2:419-430. [doi: 10.1098/rsif.2005.0067]
    [18] Srinivasan BS, Shah NH, Flannick JA, Abeliuk E, Novak AF, Batzoglou S. Current progress in network research: Toward reference networks for key model organisms. Brief in Bioinform 2007,8(5):318-332. http://bib.oxfordjournals.org/cgi/content/short/ bbm038v1
    [19] Sun JC, Xu JL, Li YX, Shi TL. Analysis and application of large-scale protein-protein interaction data. Chinese Science Bulletin, 2005,50(19):2055-2060 (in Chinese).
    [20] Guan W, Wang J, He FC. The advance in research methods for large-scale protein-protein interactions. Chinese Bulletin of Life Sciences, 2006,18(5):507-512 (in Chinese with English abstract).
    [21] Liu ZY, Li D, Zhu YP, He FC. Progress in the evolutionary analysis of protein interaction networks. Progress in Biochemistry and Biophysics, 2009,36(1):13-24 (in Chinese with English abstract).
    [22] Liu W, Li D, Zhu YP, He FC. Bioinformatics analysis in signal transduction network. Science in China (Series C), 2008,38(11): 999-1006 (in Chinese with English abstract).
    [23] Zhang S, Jin GX, Zhang XS, Chen LN. Discovering functions and revealing mechanisms at molecular level from biological networks. Proteomics, 2007,7:2856-2869. [doi: 10.1002/pmic.200700095]
    [24] Kolar M, Lassig M, Berg J. From protein interactions to functional annotation: Graph alignment in Herpes. BMC Systems Biology, 2008,2:90-99. [doi: 10.1186/1752-0509-2-90]
    [25] Sharan R, Suthranm S, Kelley RM, Kuhn T, McCuine S, Uetz P, Sittler T, Karp RM, Ideker T. Conserved patterns of protein interaction in multiple species. PNAS, 2005,102(6):1974-1979. [doi: 10.1073/pnas.0409522102]
    [26] Liang Z, Xu M, Teng MK, Niu LW. Comparison of protein interaction networks reveals species conservation and divergence. BMC Bioinformatics, 2006,7:457-472. [doi: 10.1186/1471-2105-7-457]
    [27] Singh R, Xu JB, Berger B. Global alignment of multiple protein interaction networks with application to functional orthology detection. PNAS, 2008,105(35):12763-12768. [doi: 10.1073/pnas.0806627105]
    [28] Sharan R, Ideker T, Kelley B, Shamir R, Karp RM. Identification of protein complexes by comparative analysis of yeast and bacterial protein interaction data. Journal of Computational Biology, 2005,12(6):835-846. [doi: 10.1089/cmb.2005.12.835]
    [29] Hirsh E, Sharan R. Identification of conserved protein complexes based on a model of protein network evolution. Bioinformatics, 2006,23:e170-e176. [doi: 10.1093/bioinformatics/btl295]
    [30] Tian WH, Samatova NF. Pairwise alignment of interaction networks by fast identification of maximal conserved patterns. Pacific Symposium on Biocomputing, 2009,14:99-110.
    [31] Koyuturk M, Kim Y, Topkara U, Subramaniam S, Szpankowski W, Grama A. Pairwise alignment of protein interaction networks. Journal of Computational Biology, 2006,13(2):182-199. [doi: 10.1089/cmb.2006.13.182]
    [32] Flannick J, Novak A, Srinivasan BS, McAdams HH, Batzoglou S. Graemlin: General and robust alignment of multiple large interaction networks. Genome Research, 2006,16:1169-1181. [doi: 10.1101/gr.5235706]
    [33] Flannick J, Novak A, Do ChB, Srinivasan BS, Batzoglou S. Automatic parameter learning for multiple network alignment. In: Proc. of the RECOMB 2008. LNBI 4955, 2008. 21-231. http://portal.acm.org/citation.cfm?id=1804334 [doi: 10.1089/cmb.2009.0099]
    [34] Narayanan M, Karp RM. Comparing protein interaction networks via a graph match-and-split algorithm. Journal of Computational Biology, 2007,14(7):892-907. [doi: 10.1089/cmb.2007.0025]
    [35] Ogata H, Fujibuchi W, Goto S, Kanehisa M. A heuristic graph comparison algorithm and its application to detect functionally related enzyme clusters. Nucleic Acids Research, 2000,28(20):4021-4028. [doi: 10.1093/nar/28.20.4021]
    [36] Kelley BP, Sharan R, Karp RM, Sittler T, Root DE, Stockwell BR. Conserved pathways within bacteria and yeast as revealed by global protein network alignment. PNAS, 2003,100(20):11394-11399. [doi: 10.1073/pnas.1534710100]
    [37] Kalaev M, Bafna V, Sharan R. Fast and accurate alignment of multiple protein interaction networks. Journal of computational biology, 2009, 16(8):989-999. [doi: 10.1089/cmb.2009.0136]
    [38] Bruckner S, Hüffner F, Karp RM, Shamir R, Sharan R. Topology-free querying of protein interaction networks. Journal of computational biology, 2010, 17(3):237-252. [doi: 10.1093/nar/gkp474]
    [39] Berg J, L?ssig M. Cross-Species analysis of biological networks by Bayesian alignment. PNAS, 2006,103(29):10967-10972. [doi: 10.1073/pnas.0602294103]
    [40] Li ZP, Zhang SH, Wang Y, Zhang XS, Chen LN. Alignment of molecular networks by integer quadratic programming. Bioinformatics, 2007,23(13):1631-1639. [doi: 10.1093/bioinformatics/btm156]
    [41] Klau GW. A new graph-based method for pairwise global network alignment. BMC Bioinformatics, 2009,10(Supp.):59-67. [doi: 10.1186/1471-2105-10-S1-S59]
    [42] Singh R, Xu JB, Berger B. Pairwise global alignment of protein interaction networks by matching neighborhood topology. In: Proc. of the RECOMB 2007. LNBI 4453, 2007. 16-31. http://portal.acm.org/citation.cfm?id=1758224
    [43] Pinter RY, Rokhlenko O, Lotem EY, Ukelson MZ. Alignment of metabolic pathways. Bioinformatics, 2005,21(162005):3401-3408. [doi: 10.1093/bioinformatics/bti554]
    [44] Shlomi T, Segal D, Ruppin E, Sharan R. QPath: A method for query pathways in a protein-protein interaction network. BMC Bioinformatics, 2006,7:199. [doi: 10.1186/1471-2105-7-199]
    [45] Blum T, Kohlbacher O. MetaRoute: Fast search for relevant metabolic routes for interactive network navigation and visualization. Bioinformatics, 2008,24(18):2108-2109. [doi: 10.1093/bioinformatics/btn360]
    [46] Li YL, Ridder D, Groot MJL, Reinders MJT. Metabolic pathway alignment between species using a comprehensive and flexible similarity measure. BMC Systems Biology, 2008,2:111. [doi: 10.1186/1752-0509-2-111]
    [47] Wernicke S, Rasche F. Simple and fast alignment of metabolic pathways by exploiting local diversity. Bioinformatics, 2007,23(25): 1978-1985. [doi: 10.1093/bioinformatics/btm279]
    [48] Tian Y, McEachin RC, Santos C, States DJ, Patel JM. SAGA: A subgraph matching tool for biological graphs. Bioinformatics, 2007,23(2):232-239. [doi: 10.1093/bioinformatics/btl571]
    [49] Yang QW, SZE SH. Path matching and graph matching in biological networks. Journal of Computational Biology, 2007,14(1): 56-57. [doi: 10.1089/cmb.2006.0076]
    [50] Brevier G, Rizzi R, Vialette S. Pattern matching in protein-protein interaction graphs. In: Proc. of the FCT 2007. LNCS 4639, 2007. 137-148. http://www.springerlink.com/content/q6v6j0g8527570l6/
    [51] Zhang SH, Zhang XS, Chen LN. Biomolecular network querying: A promising approach in systems biology. BMC Systems Biology, 2008,2:5. [doi: 10.1186/1752-0509-2-5]
    [52] Ali W, Deane CM. Functionally guided alignment of protein interaction networks for module detection. Bioinformatics, 2009, 25(23):3166-3173. [doi: 10.1093/bioinformatics/btp569]
    [53] Towfic F, Greenlee MHW, Honavar V. Aligning biomolecular networks using modular graph kernels. In: Proc. of the WABI 2009. LNBI 5724, 2009. 345-361. http://portal.acm.org/citation.cfm?id=1812935
    [54] Jancura P, Heringa J, Marchiori E. Divide, align and full-search for discovering conserved protein complexes. In: Proc. of the LNCS EvoBIO. 2008. 71-82. http://portal.acm.org/citation.cfm?id=1792681
    [55] Liao CS, Lu KH, Baym M, Singh R, Berger B. IsoRankN: Spectral methods for global alignment of multiple protein networks. Bioinformatics, 2009,25:i253-i258. [doi: 10.1093/bioinformatics/btp203]
    [56] Hartwell LH, Hopfield JJ, Leibler S, Murray AW. From molecular to modular cell biology. Nature, 1999,402:C47-C52. [doi: 10.1038/35011540]
    [57] Bader GD, Hogue CW. An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinformatics, 2003,4:2-28. [doi: 10.1186/1471-2105-4-2]
    [58] Adamcsek B, Palla G, Farkas IJ, Dereny I. CFinder: Locating cliques and overlapping modules in biological networks. Bioinformatics, 2006,22(8):1021-1023. [doi: 10.1093/bioinformatics/btl039]
    [59] Girvan M, Newman MEJ. Community structure in social and biological networks. PNAS, 2002,99(12):7821-7826. [doi: 10.1093/bioinformatics/btl039]
    [60] Kernighan BW, Lin S. A efficient heuristic procedure for partitioning graphs. Bell System Technical Journal, 1970,49(2):291-307.
    [61] Deniélou YP, Boyer F, Viari A, Sagot MF. Multiple alignment of biological networks: A flexible approach. In: Proc. of the CPM 2009. LNCS 5577, 2009. 263-273. http://portal.acm.org/citation.cfm?id=1574253
    [62] Guo X, Hartemink AJ. Domain-Oriented edge-based alignment of protein interaction networks. Bioinformatics, 2009,25:i240-i246. [doi: 10.1093/bioinformatics/btp202]
    [63] Fertin G, Rizzi R, Vialette S. Finding exact and maximum occurrences of protein complexes in protein-protein interaction graphs. Journal of Discrete Algorithms, 2009,7:90-101. [doi: 10.1016/j.jda.2008.11.003]
    [64] Zhang SJ, Li SR, Yang J. GADDI: Distance index based subgraph matching in biological networks. In: Proc. of the 12th Int’l Conf. on Extending Database Technology (EDBT 2009). 2009. 192-203. http://portal.acm.org/citation.cfm?id=1516384 [doi:10.1145/ 1516360.1516384]
    [65] Zaslavskiy M, Bach F, Vert JP. Global alignment of protein-protein interaction networks by graph matching methods. Bioinformatics, 2009,25:i259-i267. [doi: 10.1093/bioinformatics/btp196]
    [66] Cootes AP, Muggleton SH, Sternberg MJE. The identification of similarities between biological networks: Application to the metabolome and interactome. Journal of Molecular Biology, 2007,369:1126-1139. [doi: 10.1016/j.jmb.2007.03.013]
    [67] Qian XN, Sze SH, Yoon BJ. Querying pathways in protein interaction networks based on hidden markov models. Journal of Computational Biology, 2009,16(2): 145-157. [doi: 10.1089/cmb.2008.02TT]
    [68] Kelley BP, Yuan B, Lewitter F, Sharan R, Stockwell BR, Ideker T. PathBLAST: A tool for alignment of protein interaction networks. Nucleic Acids Research, 2004,32:W83-W88. [doi: 10.1093/nar/gkh411]
    [69] Chen M, Hofestadt R. An algorithm for linear metabolic pathway alignment. Silico Biology, 2005,5:111-128.
    [70] Kalaev M, Smoot M, Ideker T, Sharan R. NetworkBLAST: Comparative analysis of protein networks. Bioinformatics, 2008,24(4): 594-596. [doi: 10.1093/bioinformatics/btm630]
    [71] Liang Z, Xu M, Teng MK, Niu LW. NetAlign: A Web-based tool for comparison of protein interaction networks. Bioinformatics, 2006,22(17):2175-2177. [doi: 10.1093/bioinformatics/btl287]
    [72] Xenarios I, Salwínski L, Duan XJ, Higney P, Kim SM, Eisenberg D. DIP, the database of interacting proteins: A research tool for studying cellular networks of protein interactions. Nucleic Acids Research, 2002,30(1):303-305. [doi: 10.1093/nar/30.1.303]
    [73] Ogata H, Goto S, Sato F, Fujibuchi W, Bono H, Kanehisa M. KEGG: Kyoto encyclopedia of genes and genomes. Nucleic Acids Research, 1999,27(1):29-34. [doi: 10.1093/nar/27.1.29]
    [74] Liu GM, Li JY, Wong L. Assessing and predicting protein interactions using both local and global network topological metrics. In: Proc. of the 19th Int’l Conf. on Genome Informatics (GIW 2008). 2008. 138-149. http://eproceedings.worldscinet.com/ 9781848163324/9781848163324_0012.html
    [75] Chua HN, Wong L. Increasing the reliability of protein interactomes. Drug Discovery Today, 2008,13(15/16):652-658. [doi: 10.1016/j.drudis.2008.05.004]
    [76] Li D, Liu WL, Liu ZY, Wang J, Liu QJ, Zhu YP, He FC. PRINCESS, a protein interaction confidence evaluation system with multiple data sources. Molecular & Cellular Proteomics, 2008,7(6):1043-1052. [doi: 10.1074/mcp.M700287-MCP200]
    [77] Kuchaiev O, Rasajski M, Highm DJ, Przulj N. Geometric de-noising of protein-protein interaction networks. PLoS Computational Biology, 2009,5(8):e1000454. [doi: 10.1371/journal.pcbi.1000454]
    [78] Dutkowski J, Tiurn J. Identification of functional modules from conserved ancestral protein-protein interactions. Bioinformatics, 2007,23:i149-i158. [doi: 10.1093/bioinformatics/btm194]
    [79] Dittrich MT, Klau GW, Rosenwald A. Identifying functional modules in protein-protein interaction networks: An integrated exact approach. Bioinformatics, 2008,24:223-231. [doi: 10.1093/bioinformatics/btn161]
    [80] Rivera CG, Murali TM. Identifying evolutionarily conserved protein interaction modules using GraphHopper. In: Proc. of the BICoB 2009. LNBI 5462, 2009. 67-68. http://portal.acm.org/citation.cfm?id=1537782. [doi: 10.1007/978-3-642-00727-9_9]
    [81] Milenkovic T, Pr?ulj N. Uncovering biological network function via graphlet degree signatures. Cacer Informatics, 2008,6: 257-273.
    [82] Yosef N, Sharan N, Noble WS. Improved network-based identification of protein orthologs. Bioinformatics, 2008,24:i200-i206. [doi: 10.1093/bioinformatics/btn277]
    [83] Erten S, Li X, Bebek G, Li J, Koyuturk. Phylogenetic analysis of modularity in protein interaction networks. BMC Bioinformatics, 2009,10:333. [doi: 10.1186/1471-2105-10-333]
    [84] Karni S, Soreq H, Sharan R. A network-based method for predicting disease-causing genes. Journal of Computational Biology, 2009,16(2):181-189.
    [85] Ideker T, Sharan R. Protein networks in disease. Genome Research, 2008,18:644-652. [doi: 10.1101/gr.071852.107]
    附中文参考文献: [7] 程永升,刘进元.串联亲和纯化(TAP)技术在蛋白质组学中的应用.生物化学与生物物理进展,2004,31(4):379-383.
    [9] 刘康栋,赵建龙.蛋白质芯片技术进展.中国生物工程杂志,2004,24(12):48-52,58.
    [10] 李民,周宗灿.蛋白质芯片.生命的化学,2001,21(2):156-157.
    [11] 钟春英,彭蓉,彭建新,洪华珠.蛋白质芯片技术.生物技术通报,2004,2:34-37.
    [12] 杨何义,应万涛,钱小红.蛋白质组技术的研究进展.自然科学进展,2002,12(1):13-17.
    [13] 马学军,胡荣,吕海,魏开坤,张丽兰,薛水星,侯云德.噬菌体显示技术改造人干扰素α1c/86D的研究.中国科学(C辑:生命科学),1999,29(2):209-216.
    [19] 孙景春,徐晋麟,李亦学,石铁流.大规模蛋白质相互作用数据的分析与应用.科学通报,2005,50(19):2055-2060.
    [20] 关薇,王建,贺福初.大规模蛋白质相互作用研究方法进展.生命科学,2006,18(5):507-512.
    [21] 刘中扬,李栋,朱云平,贺福初.蛋白质相互作用网络进化分析研究进展.生物化学与生物物理进展,2009,36(1):13-24.
    [22] 刘伟,李栋,朱云平,贺福初.信号传导网络的生物信息学分析.中国科学(C辑:生命科学),2008,38(11):999-1006.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

郭杏莉,高琳,陈新.生物网络比对的模型与算法.软件学报,2010,21(9):2089-2106

Copy
Share
Article Metrics
  • Abstract:8023
  • PDF: 14149
  • HTML: 0
  • Cited by: 0
History
  • Received:June 18,2009
  • Revised:March 30,2010
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2035067Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063