{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,16]],"date-time":"2026-09-16T21:01:10Z","timestamp":1789592470146,"version":"build-2803163510"},"reference-count":30,"publisher":"Oxford University Press (OUP)","issue":"13","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: With more and more data on molecular networks (e.g. protein interaction networks, gene regulatory networks and metabolic networks) available, the discovery of conserved patterns or signaling pathways by comparing various kinds of networks among different species or within a species becomes an increasingly important problem. However, most of the conventional approaches either restrict comparative analysis to special structures, such as pathways, or adopt heuristic algorithms due to computational burden.<\/jats:p>\n               <jats:p>Results: In this article, to find the conserved substructures, we develop an efficient algorithm for aligning molecular networks based on both molecule similarity and architecture similarity, by using integer quadratic programming (IQP). Such an IQP can be relaxed into the corresponding quadratic programming (QP) which almost always ensures an integer solution, thereby making molecular network alignment tractable without any approximation. The proposed framework is very flexible and can be applied to many kinds of molecular networks including weighted and unweighted, directed and undirected networks with or without loops.<\/jats:p>\n               <jats:p>Availability: Matlab code and data are available from http:\/\/zhangroup.aporc.org\/bioinfo\/MNAligner or http:\/\/intelligent.eic.osaka-sandai.ac.jp\/chenen\/software\/MNAligner, or upon request from authors.<\/jats:p>\n               <jats:p>Contact: zxs@amt.ac.cn, chen@eic.osaka-sandai.ac.jp<\/jats:p>\n               <jats:p>Supplementary information: Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btm156","type":"journal-article","created":{"date-parts":[[2007,4,28]],"date-time":"2007-04-28T00:14:37Z","timestamp":1177719277000},"page":"1631-1639","source":"Crossref","is-referenced-by-count":78,"title":["Alignment of molecular networks by integer quadratic programming"],"prefix":"10.1093","volume":"23","author":[{"given":"Zhenping","family":"Li","sequence":"first","affiliation":[{"name":"1 Beijing Wuzi University, Beijing 101149, China, 2Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100080, China, 3Graduate University of Chinese Academy of Sciences, Beijing 100049, China, 4Institute of Systems Biology, Shanghai University, Shanghai 200444, China, 5Osaka Sangyo University, Osaka 574-8530, Japan, 6ERATO Aihara Complexity Modelling Project, JST, Tokyo 153-8530, Japan and 7Institite of Industrial Science, The University of Tokyo, Tokyo 153-8505, Japan"},{"name":"1 Beijing Wuzi University, Beijing 101149, China, 2Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100080, China, 3Graduate University of Chinese Academy of Sciences, Beijing 100049, China, 4Institute of Systems Biology, Shanghai University, Shanghai 200444, China, 5Osaka Sangyo University, Osaka 574-8530, Japan, 6ERATO Aihara Complexity Modelling Project, JST, Tokyo 153-8530, Japan and 7Institite of Industrial Science, The University of Tokyo, Tokyo 153-8505, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shihua","family":"Zhang","sequence":"additional","affiliation":[{"name":"1 Beijing Wuzi University, Beijing 101149, China, 2Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100080, China, 3Graduate University of Chinese Academy of Sciences, Beijing 100049, China, 4Institute of Systems Biology, Shanghai University, Shanghai 200444, China, 5Osaka Sangyo University, Osaka 574-8530, Japan, 6ERATO Aihara Complexity Modelling Project, JST, Tokyo 153-8530, Japan and 7Institite of Industrial Science, The University of Tokyo, Tokyo 153-8505, Japan"},{"name":"1 Beijing Wuzi University, Beijing 101149, China, 2Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100080, China, 3Graduate University of Chinese Academy of Sciences, Beijing 100049, China, 4Institute of Systems Biology, Shanghai University, Shanghai 200444, China, 5Osaka Sangyo University, Osaka 574-8530, Japan, 6ERATO Aihara Complexity Modelling Project, JST, Tokyo 153-8530, Japan and 7Institite of Industrial Science, The University of Tokyo, Tokyo 153-8505, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yong","family":"Wang","sequence":"additional","affiliation":[{"name":"1 Beijing Wuzi University, Beijing 101149, China, 2Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100080, China, 3Graduate University of Chinese Academy of Sciences, Beijing 100049, China, 4Institute of Systems Biology, Shanghai University, Shanghai 200444, China, 5Osaka Sangyo University, Osaka 574-8530, Japan, 6ERATO Aihara Complexity Modelling Project, JST, Tokyo 153-8530, Japan and 7Institite of Industrial Science, The University of Tokyo, Tokyo 153-8505, Japan"},{"name":"1 Beijing Wuzi University, Beijing 101149, China, 2Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100080, China, 3Graduate University of Chinese Academy of Sciences, Beijing 100049, China, 4Institute of Systems Biology, Shanghai University, Shanghai 200444, China, 5Osaka Sangyo University, Osaka 574-8530, Japan, 6ERATO Aihara Complexity Modelling Project, JST, Tokyo 153-8530, Japan and 7Institite of Industrial Science, The University of Tokyo, Tokyo 153-8505, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiang-Sun","family":"Zhang","sequence":"additional","affiliation":[{"name":"1 Beijing Wuzi University, Beijing 101149, China, 2Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100080, China, 3Graduate University of Chinese Academy of Sciences, Beijing 100049, China, 4Institute of Systems Biology, Shanghai University, Shanghai 200444, China, 5Osaka Sangyo University, Osaka 574-8530, Japan, 6ERATO Aihara Complexity Modelling Project, JST, Tokyo 153-8530, Japan and 7Institite of Industrial Science, The University of Tokyo, Tokyo 153-8505, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Luonan","family":"Chen","sequence":"additional","affiliation":[{"name":"1 Beijing Wuzi University, Beijing 101149, China, 2Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100080, China, 3Graduate University of Chinese Academy of Sciences, Beijing 100049, China, 4Institute of Systems Biology, Shanghai University, Shanghai 200444, China, 5Osaka Sangyo University, Osaka 574-8530, Japan, 6ERATO Aihara Complexity Modelling Project, JST, Tokyo 153-8530, Japan and 7Institite of Industrial Science, The University of Tokyo, Tokyo 153-8505, Japan"},{"name":"1 Beijing Wuzi University, Beijing 101149, China, 2Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100080, China, 3Graduate University of Chinese Academy of Sciences, Beijing 100049, China, 4Institute of Systems Biology, Shanghai University, Shanghai 200444, China, 5Osaka Sangyo University, Osaka 574-8530, Japan, 6ERATO Aihara Complexity Modelling Project, JST, Tokyo 153-8530, Japan and 7Institite of Industrial Science, The University of Tokyo, Tokyo 153-8505, Japan"},{"name":"1 Beijing Wuzi University, Beijing 101149, China, 2Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100080, China, 3Graduate University of Chinese Academy of Sciences, Beijing 100049, China, 4Institute of Systems Biology, Shanghai University, Shanghai 200444, China, 5Osaka Sangyo University, Osaka 574-8530, Japan, 6ERATO Aihara Complexity Modelling Project, JST, Tokyo 153-8530, Japan and 7Institite of Industrial Science, The University of Tokyo, Tokyo 153-8505, Japan"},{"name":"1 Beijing Wuzi University, Beijing 101149, China, 2Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100080, China, 3Graduate University of Chinese Academy of Sciences, Beijing 100049, China, 4Institute of Systems Biology, Shanghai University, Shanghai 200444, China, 5Osaka Sangyo University, Osaka 574-8530, Japan, 6ERATO Aihara Complexity Modelling Project, JST, Tokyo 153-8530, Japan and 7Institite of Industrial Science, The University of Tokyo, Tokyo 153-8505, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2007,4,27]]},"reference":[{"key":"2023062708444465400_B1","doi-asserted-by":"crossref","DOI":"10.1201\/9781420011432","article-title":"An introduction to systems biology: design principles of biological circuits","author":"Alon","year":"2006"},{"key":"2023062708444465400_B2","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1186\/1471-2105-4-2","article-title":"An automated method for finding molecular complexes in large protein interaction networks","volume":"4","author":"Bader","year":"2003","journal-title":"BMC Bioinformatics"},{"key":"2023062708444465400_B3","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1038\/nbt924","article-title":"Gaining confidence in high-throughput protein interaction networks","volume":"22","author":"Bader","year":"2004","journal-title":"Nat. Biotechnol"},{"key":"2023062708444465400_B4","doi-asserted-by":"crossref","first-page":"428","DOI":"10.1101\/gr.4526006","article-title":"Systematic identification of functional orthologs based on protein network comparison","volume":"16","author":"Bandyopadhyay","year":"2006","journal-title":"Genome Res"},{"key":"2023062708444465400_B5","doi-asserted-by":"crossref","first-page":"14689","DOI":"10.1073\/pnas.0305199101","article-title":"Local graph algorithm and motif search in biological networks","volume":"101","author":"Berg","year":"2004","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023062708444465400_B6","doi-asserted-by":"crossref","first-page":"10967","DOI":"10.1073\/pnas.0602294103","article-title":"Cross\u2013species analysis of biological networks by Bayesian alignment","volume":"103","author":"Berg","year":"2006","journal-title":"PNAS"},{"key":"2023062708444465400_B7","doi-asserted-by":"crossref","first-page":"011909","DOI":"10.1103\/PhysRevE.70.011909","article-title":"Dynamics of gene regulatory networks with cell division cycle","volume":"70","author":"Chen","year":"2004","journal-title":"Phys. Rev. E"},{"key":"2023062708444465400_B8","doi-asserted-by":"crossref","first-page":"2722","DOI":"10.1093\/bioinformatics\/bti392","article-title":"Noise\u2013induced cooperative behavior in a multi\u2013cell system","volume":"21","author":"Chen","year":"2005","journal-title":"Bioinformatics"},{"key":"2023062708444465400_B9","doi-asserted-by":"crossref","first-page":"833","DOI":"10.1002\/prot.20783","article-title":"Inferring protein interactions from experimental data by association probabilistic method","volume":"62","author":"Chen","year":"2006","journal-title":"Proteins"},{"key":"2023062708444465400_B10","doi-asserted-by":"crossref","first-page":"D311","DOI":"10.1093\/nar\/gkh033","article-title":"Saccharomyces Genome Database (SGD) provides tools to identify and analyze sequences from Saccharomyces cerevisiae and related sequences from other organisms","volume":"32","author":"Christie","year":"2004","journal-title":"Nucleic Acids Res"},{"key":"2023062708444465400_B11","first-page":"140","article-title":"Assessment of the reliability of protein\u2013protein interactions and protein function prediction","volume":"8","author":"Deng","year":"2003","journal-title":"Pac. Symp. Biocomput"},{"key":"2023062708444465400_B12","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511790492","volume-title":"Biological Sequence Analyses: Probabilitic Methods of Proteins and Nucleic Acids","author":"Durbin","year":"1998"},{"key":"2023062708444465400_B13","doi-asserted-by":"crossref","first-page":"C47","DOI":"10.1038\/35011540","article-title":"From molecular to modular cell biology","volume":"402","author":"Hartwell","year":"1999","journal-title":"Nature"},{"key":"2023062708444465400_B14","doi-asserted-by":"crossref","first-page":"11394","DOI":"10.1073\/pnas.1534710100","article-title":"Conserved pathways within bacteria and yeast as revealed by global protein network alignment","volume":"100","author":"Kelley","year":"2003","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023062708444465400_B15","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1093\/nar\/gkh411","article-title":"PathBLAST: a tool for alignment of protein interaction networks","volume":"32","author":"Kelley","year":"2004","journal-title":"Nucleic Acids Res"},{"key":"2023062708444465400_B16","first-page":"48","article-title":"Pairwise local alignment of protein interaction network guided by models of evolution","volume":"3500","author":"Koyut\u00fcrk","year":"2005","journal-title":"RECOM 2005 LNBI"},{"key":"2023062708444465400_B17","first-page":"25","article-title":"The E.coli EcoCyc Database: no longer just a metabolic pathway database","volume":"70","author":"Karp","year":"2004","journal-title":"ASM News"},{"key":"2023062708444465400_B18","doi-asserted-by":"crossref","first-page":"1555","DOI":"10.1126\/science.1099511","article-title":"A probabilistic functional network of yeast genes","volume":"306","author":"Lee","year":"2004","journal-title":"Science"},{"key":"2023062708444465400_B19","doi-asserted-by":"crossref","first-page":"910","DOI":"10.1126\/science.1065103","article-title":"Specificity and stability in topology of protein networks","volume":"296","author":"Maslov","year":"2002","journal-title":"Science"},{"key":"2023062708444465400_B20","doi-asserted-by":"crossref","first-page":"4021","DOI":"10.1093\/nar\/28.20.4021","article-title":"A heuristic graph comparison algorithm and its application to detect functionally related enzyme clusters","volume":"28","author":"Ogata","year":"2000","journal-title":"Nucleic Acids Res"},{"key":"2023062708444465400_B21","first-page":"42","article-title":"Sensitive sequence comparison as protein function predictor","volume":"5","author":"Pawlowski","year":"2000","journal-title":"Pac. Symp. Biocomput"},{"key":"2023062708444465400_B22","doi-asserted-by":"crossref","first-page":"3401","DOI":"10.1093\/bioinformatics\/bti554","article-title":"Alignment of metabolic pathways","volume":"21","author":"Pinter","year":"2005","journal-title":"Bioinformatics"},{"key":"2023062708444465400_B23","doi-asserted-by":"crossref","first-page":"1041","DOI":"10.1006\/jmbi.2000.5197","article-title":"Automatic clustering of orthologs and in\u2013paralogs from pairs species comparisons","volume":"314","author":"Remm","year":"2001","journal-title":"J. Mol. Biol"},{"key":"2023062708444465400_B24","doi-asserted-by":"crossref","first-page":"1128","DOI":"10.1073\/pnas.0237338100","article-title":"Modular organization of cellular networks","volume":"100","author":"Rives","year":"2003","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023062708444465400_B25","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1038\/nbt1196","article-title":"Modeling cellular machinery through biological network comparison","volume":"24","author":"Sharan","year":"2006","journal-title":"Nat. Biotechnol"},{"key":"2023062708444465400_B26","first-page":"376","article-title":"A multiple alignment algorithm for metabolic pathway analysis using enzyme hierarchy","author":"Tohsato","year":"2000"},{"key":"2023062708444465400_B27","doi-asserted-by":"crossref","first-page":"e74","DOI":"10.1371\/journal.pcbi.0010074","article-title":"Functional alignment of regulatory networks: a study of temerate phages","volume":"1","author":"Trusina","year":"2005","journal-title":"PLoS Comput. Biol"},{"key":"2023062708444465400_B28","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1177\/0748730405275653","article-title":"Synchronizing genetic oscillators by signalling molecules","volume":"20","author":"Wang","year":"2005","journal-title":"J. Biol. Rhythms"},{"key":"2023062708444465400_B29","doi-asserted-by":"crossref","first-page":"2413","DOI":"10.1093\/bioinformatics\/btl396","article-title":"Inferring gene regulatory networks from multiple microarray datasets","volume":"22","author":"Wang","year":"2006","journal-title":"Bioinformatics"},{"key":"2023062708444465400_B30","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1007\/BF01580903","article-title":"On affine-scaling algorithm for nonconvex quadratic programming","volume":"56","author":"Ye","year":"1992","journal-title":"Math. Programm"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/23\/13\/1631\/50716609\/bioinformatics_23_13_1631.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/23\/13\/1631\/50716609\/bioinformatics_23_13_1631.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,27]],"date-time":"2023-06-27T08:46:48Z","timestamp":1687855608000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/23\/13\/1631\/223138"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,4,27]]},"references-count":30,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2007,7,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btm156","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2007,7]]},"published":{"date-parts":[[2007,4,27]]}}}