[1]LIU Fu,JIANG Yihan,ZOU Qingyu.Advances in algorithms for construction alignment of complex networks research[J].CAAI Transactions on Intelligent Systems,2015,10(4):508-517.[doi:10.3969/j.issn.1673-4785.201408006]
Copy

Advances in algorithms for construction alignment of complex networks research

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 10 Number of periods: 2015 4 Page number: 508-517 Column: 综述 Public date: 2015-08-25
Title:
Advances in algorithms for construction alignment of complex networks research
Author(s):
LIU Fu1;  JIANG Yihan1;  ZOU Qingyu2
1. Communication Engineering, Jilin University, Changchun 130022 China;
2. Electric & Information Engineering, Beihua University, jilin, 132000 China
Keywords:
complex networks; quadratic programming; topology identification; graph theory; alignment; network analysis; node cluster; dynamic analysis
CLC:
TP391;O212
DOI:
10.3969/j.issn.1673-4785.201408006
Abstract:
The construction alignment of complex networks problems in biological science、computer science、social science and other fields have practical signification. In recent years, different types of construction alignment of complex networks have been sprung up. In this paper, we mainly analysed the construction alignment algorithms based on graph and construction alignment algorithms and mathematical framework.Illustrating the key problem in the study of the networks alignment algorithm is analyzed and compared the algorithms of construction alignment. We explained their advantages and disadvantages,at last we forecast the future progress of algorithms for construction alignment of complex networks.
References:
[1] STELZL U, WORM U, LALOWSKI M, et al. A human protein-protein interaction network: a resource for annotating the proteome[J]. Cell, 2005, 122 (6): 957-968.
[2] REN B, ROBERT F, WYRICK J J, et al. Genome-wide location and function of DNA binding proteins[J]. Science, 2000, 290 (5500): 2306-2309.
[3] MICHOEL T, NACHTERGAELE B. Alignment and integration of complex networks by hypergraph-based spectral clustering[J]. Physical Review E, 2012, 86 (5): 056111.
[4] ERDO S P, R NYI A. On the evolution of random graphs[J]. American Mathematical Society, 1960, 517-561.
[5] BONNICI V, GIUGNO R, PULVIRENTI A, et al. A subgraph isomorphism algorithm and its application to biochemical data[J]. BMC bioinformatics, 2013, 14 (Suppl 7): S13.
[6] KHAN A M, GLEICH D F, POTHEN A, et al. A multithreaded algorithm for network alignment via approximate matching[C]//2012 International Conference on proceedings of the High Performance Computing, Networking, Storage and Analysis (SC). 2012.
[7] TODOR A, DOBRA A, KAHVECI T. Probabilistic biological network alignment[J]. IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), 2013, 10 (1): 109-121.
[8] SHVAIKO P, EUZENAT J. Ontology matching: state of the art and future challenges[J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25 (1): 158-176.
[9] BOCK J, HETTENHAUSEN J. Discrete particle swarm optimisation for ontology alignment[J]. Information Sciences, 2012, 192: 152-173.
[10] HU W, JIAN N, QU Y, et al. Gmo: a graph matching for ontologies[C]//proceedings of the Proceedings of K-CAP Workshop on Integrating Ontologies. 2005: 42-48.
[11] MELNIK S, GARCIA-MOLINA H, RAHM E. Similarity flooding: a versatile graph matching algorithm and its application to schema matching[C]//Proceedings of the Proc 18th ICDE Conf(Best Student Paper award). 2002.
[12] KLAU G W. A new graph-based method for pairwise global network alignment[J]. BMC bioinformatics, 2009, 10(Suppl 1): S59.
[13] SINGH R, XU J, BERGER B. Pairwise global alignment of protein interaction networks by matching neighborhood topology[J]. 2007: 16-31.
[14] SINGH R, XU J, BERGER B. Global alignment of multiple protein interaction networks with application to functional orthology detection[J]. Proceedings of the National Academy of Sciences, 2008, 105 (35): 12763-12768.
[15] LAWLER E L. The quadratic assignment problem[J]. Management Science, 1963, 9 (4): 586-599.
[16] MISENER R, FLOUDAS C A. GloMIQO: Global mixed-integer quadratic optimizer[J]. Journal of Global Optimization, 2012, 57 (1):
[17] RIECK J, ZIMMERMANN J, GATHER T. Mixed-integer linear programming for resource leveling problems[J]. European Journal of Operational Research, 2012, 221 (1): 27-37.
[18] BRADDE S, BRAUNSTEIN A, MAHMOUDI H, et al. Aligning graphs and finding substructures by a cavity approach[J]. EPL (Europhysics Letters), 2010, 89 (3): 37009.
[19] BAYATI M, GERRITSEN M, GLEICH D F, et al. Algorithms for large, sparse network alignment problems[J]. 2009, 705-710.
[20] EL-KEBIR M, HERINGA J, KLAU G W. Lagrangian relaxation applied to sparse global network alignment[M]. Springer. 2011: 225-236.
[21] GUIGNARD M, KIM S. Lagrangean decomposition: a model yielding stronger Lagrangean bounds[J]. Mathematical Programming, 1987, 39 (2): 215-228.
[22] SINGH R, XU J, BERGER B. Global alignment of multiple protein interaction networks with application to functional orthology detection[J]. Proceedings of the National Academy of Sciences of the United States of America, 2008, 105 (35): 12763-12768.
[23] KECECIOGLU J. The maximum weight trace problem in multiple sequence alignment[C]//proceedings of the Combinatorial pattern matching. Springer.1993: 106-119.
[24] SAMATOVA N F. Global alignment of pairwise protein interaction networks for maximal common conserved patterns[J]. International Journal of Genomics, 2013: 670623.
[25] BAUER M, KLAU G W, REINERT K, et al. Accurate multiple sequence-structure alignment of RNA sequences[J]. BMC Bioinformatics, 2009: 15-33.
[26] BAYATI M, SHAH D, SHARMA M. Max-product for maximum weight matching: convergence, correctness, and LP duality[J]. IEEE Transactions on Information Theory, 2008, 54 (3): 1241-1251.
[27] BAYATI M, GERRITSEN M, GLEICH D F, et al. Algorithms for large, sparse network alignment problems[C]//09 Ninth IEEE International Conference on proceedings of the Data Mining, 2009: 705-710.
[28] PEARL J. Reverend Bayes on inference engines: a distributed hierarchical approach[C]//proceedings of the AAAI. 1982: 133-136.
[29] SANGHAVI S, MALIOUTOV D M, WILLSKY A S. Linear programming analysis of loopy belief propagation for weighted matching[C]//proceedings of the NIPS, 2007:.
[30] DAGUM L, MENON R. OpenMP: an industry standard API for shared-memory programming[J]. IEEE Transactions on Computational Science & Engineering, 1998, 5 (1): 46-55.
[31] JUNG J, MORI T, SUGITA Y. Midpoint cell method for hybrid (MPI+OpenMP) parallelization of molecular dynamics simulations[J]. Journal of computational chemistry, 2014: 1064-1072.
[32] THOMAN P, JORDAN H, PELLEGRINI S, et al. Automatic OpenMP loop scheduling: a combined compiler and runtime approach[M]. Springer, 2012: 88-101.
[33] GOUVEIA A, SILVA N, ROCHA J, et al. Iterative ontology alignment debugging using a scenario-and strategy-driven approach[C]// International Workshop on proceedings of the Database and Expert Systems Applications (DEXA), 2012\: 254-258.
[34] PAGE L, BRIN S, MOTWANI R, et al. The PageRank citation ranking: bringing order to the web[J]. 1999: 102-109.
[35] LIAO C-S, LU K, BAYM M, et al. IsoRankN: spectral methods for global alignment of multiple protein networks[J]. Bioinformatics, 2009, 25 (12): i253-i258.
[36] ANDERSEN R, CHUNG F, LANG K. Local graph partitioning using pagerank vectors[C]//47th Annual IEEE Symposium on proceedings of the Foundations of Computer Science, 2006 2006:.
[37] ALADAG A E, ERTEN C. SPINAL: scalable protein interaction network alignment[J]. Bioinformatics, 2013, 29 (7): 917-924.
[38] KELLEY B P, YUAN B, LEWITTER F, et al. PathBLAST: a tool for alignment of protein interaction networks[J]. Nucleic acids research, 2004, 32 (suppl 2): W83-W88.
[39] SHARAN R, SUTHRAM S, KELLEY R M, et al. Conserved patterns of protein interaction in multiple species[J]. Proceedings of the National Academy of Sciences of the United States of America, 2005, 102 (6): 1974-1979.
[40] KOYUT RK M, KIM Y, TOPKARA U, et al. Pairwise alignment of protein interaction networks[J]. Journal of Computational Biology, 2006, 13 (2): 182-199.
[41] FLANNICK J, NOVAK A, SRINIVASAN B S, et al. Graemlin: general and robust alignment of multiple large interaction networks[J]. Genome Research, 2006, 16 (9): 1169-1181.
[42] FLANNICK J, NOVAK A, DO C B, et al. Automatic parameter learning for multiple network alignment[C]//Proceedings of the Research in Computational Molecular Biology, F, 2008: 214-231.
[43] WANG B, GAO L. Seed selection strategy in global network alignment without destroying the entire structures of functional modules[J]. Proteome science, 2012, 10 (Suppl 1): S16.
[44] KOV CS I A, PALOTAI R, SZALAY M S, et al. Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics[J]. PloS one, 2010, 5 (9): e12528.
[45] MILENKOVIC T, ADVISER-PRZULJ N. From topological network analyses and alignments to biological function, disease, and evolution[M]. California State University at Long Beach, 2010
[46] ATIAS N, SHARAN R. Comparative analysis of protein networks: hard problems, practical solutions[J]. Communications of the ACM, 2012, 55 (5): 88-97.
[47] MILENKOVI C T, PRZULJ N. Uncovering biological network function via graphlet degree signatures[J]. Cancer informatics, 2008, (6): 56-65.
[48] MILLS-TETTEY G A, STENTZ A, DIAS M B. The dynamic hungarian algorithm for the assignment problem with changing costs[J]. 2007: 1-19.
[49] WEST D B. Introduction to graph theory[M]. Prentice hall Upper Saddle River, 2001: 178-185.
[50] MEMI?EVIC V, PRZULJ N. C-GRAAL: Common-neighbors-based global GRAph ALignment of biological networks[J]. Integrative Biology, 2012, 4 (7): 734-743.
[51] DUAN R, PETTIE S. Linear-Time Approximation for Maximum Weight Matching[J]. Journal of the ACM (JACM), 2014, 61 (1): 1.
[52] KOLLIAS G, MOHAMMADI S, GRAMA A. Network Similarity Decomposition (NSD): A fast and scalable approach to network alignment[J]. Knowledge and Data Engineering, IEEE Transactions on, 2012, 24 (12): 2232-2243.
[53] HUANG Q, WU L-Y, ZHANG X-S. Corbi: A new R package for biological network alignment and querying[J]. BMC Systems Biology, 2013, 7 (2): 1-9.
[54] PIJPERS V, DE LEENHEER P, GORDIJN J, et al. Using conceptual models to explore business-ICT alignment in networked value constellations[J]. Requirements Engineering, 2012, 17 (3): 203-226.
[55] KEARNS M, SINGH S. Near-optimal reinforcement learning in polynomial time[J]. Machine Learning, 2002, 49 (2-3): 209-232.
[56] LIU G, LI J, WONG L. Assessing and predicting protein interactions using both local and global network topological metrics[J]. Genome Informatics, 2008, 22 138-149.
[57] KUCHAIEV O, RA?AJSKI M, HIGHAM D J, et al. Geometric de-noising of protein-protein interaction networks[J]. PLoS computational biology, 2009, 5 (8): e1000454.
[58] CHUA H N, SUNG W-K, WONG L. Exploiting indirect neighbours and topological weight to predict protein function from protein-protein interactions[J]. Bioinformatics, 2006, 22 (13): 1623-1630.
[59] NABIEVA E, JIM K, AGARWAL A, et al. Whole-proteome prediction of protein function via graph-theoretic analysis of interaction maps[J]. Bioinformatics, 2005, 21 (suppl 1): i302-i310.
[60] ALI W, DEANE C M. Functionally guided alignment of protein interaction networks for module detection[J]. Bioinformatics, 2009, 25 (23): 3166-3173.
[61] CLAUSET A, MOORE C, NEWMAN M E. Hierarchical structure and the prediction of missing links in networks[J]. Nature, 2008, 453 (7191): 98-101.
[62] PR?ULJ N. Biological network comparison using graphlet degree distribution[J]. Bioinformatics, 2007, 23 (2): e177-e183.
[63] ZHU L, YOU Z-H, HUANG D-S. Increasing the reliability of protein-protein interaction networks via non-convex semantic embedding[J]. Neurocomputing, 2013, v121,p99-107.
[64] TERRADOT L, DURNELL N, LI M, et al. Biochemical Characterization of Protein Complexes from the Helicobacter pylori Protein Interaction Map Strategies for Complex Formation and Evidence for Novel Interactions Within Type IV Secretion Systems[J]. Molecular & Cellular Proteomics, 2004, 3 (8): 809-819.
[65] SUN P G, GAO L, SHAN HAN S. Identification of overlapping and non-overlapping community structure by fuzzy clustering in complex networks[J]. Information Sciences, 2011, 181 (6): 1060-1071.
[66] HAVEMANN F, GL SER J, HEINZ M, et al. Identifying overlapping and hierarchical thematic structures in networks of scholarly papers: A comparison of three approaches[J]. PloS one, 2012, 7 (3): e33255.
[67] LEE C, REID F, MCDAID A, et al. Seeding for pervasively overlapping communities[J]. Physical Review E, 2011, 83 (6).
[68] DENT J E, YANG X, NARDINI C. SPNConverter: a new link between static and dynamic complex network analysis[J]. Bioinformatics, 2013, 29 (19): 2507-2508.
[69] WANG J, PENG X, PENG W, et al. Dynamic protein interaction network construction and applications[J]. Proteomics, 2014, 14 (4-5): 338-352.
[70] VAN DEN HOF P M, DANKERS A, HEUBERGER P S, et al. Identification of dynamic models in complex networks with prediction error methods—Basic methods for consistent module estimates[J]. Automatica, 2013, 49 (10): 2994-3006.
[71] MA’AYAN A. Insights into the organization of biochemical regulatory networks using graph theory analyses[J]. Journal of biological chemistry, 2009, 284 (9): 5451-5455.
Similar References:

Memo

-

Last Update: 2015-08-28

Copyright © CAAI Transactions on Intelligent Systems