{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T23:04:24Z","timestamp":1773270264043,"version":"3.50.1"},"reference-count":33,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2015,11,18]],"date-time":"2015-11-18T00:00:00Z","timestamp":1447804800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Data on molecular interactions is increasing at a tremendous pace, while the development of solid methods for analyzing this network data is still lagging behind. This holds in particular for the field of comparative network analysis, where one wants to identify commonalities between biological networks. Since biological functionality primarily operates at the network level, there is a clear need for topology-aware comparison methods. We present a method for global network alignment that is fast and robust and can flexibly deal with various scoring schemes taking both node-to-node correspondences as well as network topologies into account. We exploit that network alignment is a special case of the well-studied quadratic assignment problem (QAP). We focus on sparse network alignment, where each node can be mapped only to a typically small subset of nodes in the other network. This corresponds to a QAP instance with a symmetric and sparse weight matrix. We obtain strong upper and lower bounds for the problem by improving a Lagrangian relaxation approach and introduce the open source software tool Natalie 2.0, a publicly available implementation of our method. In an extensive computational study on protein interaction networks for six different species, we find that our new method outperforms alternative established and recent state-of-the-art methods.<\/jats:p>","DOI":"10.3390\/a8041035","type":"journal-article","created":{"date-parts":[[2015,11,18]],"date-time":"2015-11-18T10:35:12Z","timestamp":1447842912000},"page":"1035-1051","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":23,"title":["Natalie 2.0: Sparse Global Network Alignment as a Special Case of Quadratic Assignment"],"prefix":"10.3390","volume":"8","author":[{"given":"Mohammed","family":"El-Kebir","sequence":"first","affiliation":[{"name":"Life Sciences Group, Centrum Wiskunde & Informatica (CWI), Science Park 123, 1098 XG Amsterdam, The Netherlands"},{"name":"Centre for Integrative Bioinformatics VU (IBIVU), VU University Amsterdam, De Boelelaan 1081A, 1081 HV Amsterdam, The Netherlands"},{"name":"Center for Computational Molecular Biology and Department of Computer Science, Brown University, Providence, RI 02912, USA"}]},{"given":"Jaap","family":"Heringa","sequence":"additional","affiliation":[{"name":"Centre for Integrative Bioinformatics VU (IBIVU), VU University Amsterdam, De Boelelaan 1081A, 1081 HV Amsterdam, The Netherlands"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6340-0090","authenticated-orcid":false,"given":"Gunnar","family":"Klau","sequence":"additional","affiliation":[{"name":"Life Sciences Group, Centrum Wiskunde & Informatica (CWI), Science Park 123, 1098 XG Amsterdam, The Netherlands"},{"name":"Centre for Integrative Bioinformatics VU (IBIVU), VU University Amsterdam, De Boelelaan 1081A, 1081 HV Amsterdam, The Netherlands"}]}],"member":"1968","published-online":{"date-parts":[[2015,11,18]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Szklarczyk, D., Franceschini, A., Wyder, S., Forslund, K., Heller, D., Huerta-Cepas, J., Simonovic, M., Roth, A., Santos, A., and Tsafou, K.P. (2015). STRING v10: Protein-protein interaction networks, integrated over the tree of life. Nucleic Acids Res., 43.","DOI":"10.1093\/nar\/gku1003"},{"key":"ref_2","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":"ref_3","doi-asserted-by":"crossref","unstructured":"Kanehisa, M., Goto, S., Hattori, M., Aoki-Kinoshita, K.F., Itoh, M., Kawashima, S., Katayama, T., Araki, M., and Hirakawa, M. (2006). From genomics to chemical genomics: New developments in KEGG. Nucleic Acids Res., 34.","DOI":"10.1093\/nar\/gkj102"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"450","DOI":"10.1038\/nrg2102","article-title":"Network motifs: Theory and experimental approaches","volume":"8","author":"Alon","year":"2007","journal-title":"Nat. Rev. Genet."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Elmsallati, A., Clark, C., and Kalita, J. (2015). Global alignment of protein-protein interaction networks: A survey. IEEE\/ACM Trans. Comput. Biol. Bioinf., 99.","DOI":"10.1109\/TCBB.2015.2474391"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"12763","DOI":"10.1073\/pnas.0806627105","article-title":"Global alignment of multiple protein interaction networks with application to functional orthology detection","volume":"105","author":"Singh","year":"2008","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Klau, G.W. (2009). A new graph-based method for pairwise global network alignment. BMC Bioinf., 10.","DOI":"10.1186\/1471-2105-10-S1-S59"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1341","DOI":"10.1098\/rsif.2010.0063","article-title":"Topological network alignment uncovers biological function and phylogeny","volume":"7","author":"Kuchaiev","year":"2010","journal-title":"J. R. Soc. Interface"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"3105","DOI":"10.1093\/bioinformatics\/bts592","article-title":"Global network alignment using multiscale spectral signatures","volume":"28","author":"Patro","year":"2012","journal-title":"Bioinformatics"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1654","DOI":"10.1093\/bioinformatics\/btt202","article-title":"NETAL: A new graph-based method for global alignment of protein-protein interaction networks","volume":"29","author":"Neyshabur","year":"2013","journal-title":"Bioinformatics"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"917","DOI":"10.1093\/bioinformatics\/btt071","article-title":"SPINAL: Scalable protein interaction network alignment","volume":"29","author":"Erten","year":"2013","journal-title":"Bioinformatics"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"2765","DOI":"10.1093\/bioinformatics\/btt486","article-title":"Optimizing a global alignment of protein interaction networks","volume":"29","author":"Chindelevitch","year":"2013","journal-title":"Bioinformatics"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"i438","DOI":"10.1093\/bioinformatics\/btu450","article-title":"HubAlign: An accurate and efficient method for global alignment of protein-protein interaction networks","volume":"30","author":"Hashemifar","year":"2014","journal-title":"Bioinformatics"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Vijayan, V., Saraph, V., and Milenkovi\u0107, T. (2015). MAGNA++: Maximizing accuracy in global network alignment via both node and edge conservation. Bioinformatics, 31.","DOI":"10.1093\/bioinformatics\/btv161"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1988","DOI":"10.1093\/bioinformatics\/btv063","article-title":"A multiobjective memetic algorithm for PPI network alignment","volume":"31","author":"Clark","year":"2015","journal-title":"Bioinformatics"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"2182","DOI":"10.1093\/bioinformatics\/btv130","article-title":"L-GRAAL: Lagrangian graphlet-based network aligner","volume":"31","author":"Przulj","year":"2015","journal-title":"Bioinformatics"},{"key":"ref_17","unstructured":"Natalie 2.0. Available online: http:\/\/software.cwi.nl\/natalie."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"El-Kebir, M., Brandt, B.W., Heringa, J., and Klau, G.W. (2014). NatalieQ: A web server for protein-protein interaction network querying. BMC Syst. Biol., 8.","DOI":"10.1186\/1752-0509-8-40"},{"key":"ref_19","unstructured":"NatalieQ. Available online: http:\/\/www.ibi.vu.nl\/programs\/natalieq\/."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Miller, R.E., and Thatcher, J.W. (1972). Complexity of Computer Computations, Plenum Press.","DOI":"10.1007\/978-1-4684-2001-2"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"586","DOI":"10.1287\/mnsc.9.4.586","article-title":"The quadratic assignment problem","volume":"9","author":"Lawler","year":"1963","journal-title":"Manage Sci."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1090\/dimacs\/016\/02","article-title":"Improved linear programming-based lower bounds for the quadratic assignment problem","volume":"16","author":"Adams","year":"1994","journal-title":"DIMACS Ser. Discr. Math. Theor. Comput. Sci."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1002\/nav.3800020109","article-title":"The Hungarian method for the assignment problem","volume":"2","author":"Kuhn","year":"1955","journal-title":"Naval Res. Logist. Q."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1137\/0105003","article-title":"Algorithms for the assignment and transportation problems","volume":"5","author":"Munkres","year":"1957","journal-title":"SIAM J. Appl. Math."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1145\/321694.321699","article-title":"Theoretical improvements in algorithmic efficiency for network flow problems","volume":"19","author":"Edmonds","year":"1972","journal-title":"J. ACM"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","article-title":"Path, trees, and flowers","volume":"17","author":"Edmonds","year":"1965","journal-title":"Can. J Math"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BF02579036","article-title":"Lagrangean relaxation","volume":"11","author":"Guignard","year":"2003","journal-title":"Top"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1007\/BF01584070","article-title":"The traveling-salesman problem and minimum spanning trees: Part II","volume":"1","author":"Held","year":"1971","journal-title":"Math. Progr."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"730","DOI":"10.1287\/opre.47.5.730","article-title":"A heuristic method for the set cover problem","volume":"47","author":"Caprara","year":"1999","journal-title":"Oper. Res."},{"key":"ref_30","unstructured":"Egerv\u00e1ry Research Group on Combinatorial Optimization LEMON Graph Library. Available online: http:\/\/lemon.cs.elte.hu\/."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1038\/75556","article-title":"Gene Ontology: Tool for the unification of biology","volume":"25","author":"Ashburner","year":"2000","journal-title":"Nat. Genet."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/j.datak.2006.05.003","article-title":"Measuring Semantic Similarity between Gene Ontology Terms","volume":"61","author":"Couto","year":"2007","journal-title":"Data Knowl. Eng."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1007\/s11590-011-0313-3","article-title":"Algorithm Engineering for optimal alignment of protein structure distance matrices","volume":"5","author":"Wohlers","year":"2011","journal-title":"Optim. Lett."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/8\/4\/1035\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T20:52:20Z","timestamp":1760215940000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/8\/4\/1035"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11,18]]},"references-count":33,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2015,12]]}},"alternative-id":["a8041035"],"URL":"https:\/\/doi.org\/10.3390\/a8041035","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,11,18]]}}}