{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T07:01:45Z","timestamp":1761807705027},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642248542"},{"type":"electronic","value":"9783642248559"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-24855-9_20","type":"book-chapter","created":{"date-parts":[[2011,10,28]],"date-time":"2011-10-28T07:05:26Z","timestamp":1319785526000},"page":"225-236","source":"Crossref","is-referenced-by-count":26,"title":["Lagrangian Relaxation Applied to Sparse Global Network Alignment"],"prefix":"10.1007","author":[{"given":"Mohammed","family":"El-Kebir","sequence":"first","affiliation":[]},{"given":"Jaap","family":"Heringa","sequence":"additional","affiliation":[]},{"given":"Gunnar W.","family":"Klau","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"20_CR1","doi-asserted-by":"crossref","unstructured":"Adams, W.P., Johnson, T.: Improved linear programming-based lower bounds for the quadratic assignment problem. DIMACS Series in Discrete Mathematics and Theoretical Computer Science (1994)","DOI":"10.1090\/dimacs\/016\/02"},{"issue":"6","key":"20_CR2","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1038\/nrg2102","volume":"8","author":"U. Alon","year":"2007","unstructured":"Alon, U.: Network motifs: theory and experimental approaches. Nat. Rev. Genet.\u00a08(6), 450\u2013461 (2007)","journal-title":"Nat. Rev. Genet."},{"key":"20_CR3","doi-asserted-by":"crossref","unstructured":"Ashburner, M., Ball, C.A., Blake, J.A., et al.: Gene ontology: tool for the unification of biology. Nat. Genet.\u00a025 (2000)","DOI":"10.1038\/75556"},{"issue":"3","key":"20_CR4","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1089\/cmb.2010.0280","volume":"18","author":"F. Ay","year":"2011","unstructured":"Ay, F., Kellis, M., Kahveci, T.: SubMAP: Aligning Metabolic Pathways with Subnetwork Mappings.. J. Comput. Biol.\u00a018(3), 219\u2013235 (2011)","journal-title":"J. Comput. Biol."},{"key":"20_CR5","doi-asserted-by":"publisher","first-page":"730","DOI":"10.1287\/opre.47.5.730","volume":"47","author":"A. Caprara","year":"1999","unstructured":"Caprara, A., Fischetti, M., Toth, P.: A heuristic method for the set cover problem. Oper. Res.\u00a047, 730\u2013743 (1999)","journal-title":"Oper. Res."},{"key":"20_CR6","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J. Edmonds","year":"1965","unstructured":"Edmonds, J.: Path, trees, and flowers. Canadian J. Math.\u00a017, 449\u2013467 (1965)","journal-title":"Canadian J. Math."},{"key":"20_CR7","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J. Edmonds","year":"1972","unstructured":"Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. J.ACM\u00a019, 248\u2013264 (1972)","journal-title":"J.ACM"},{"issue":"9","key":"20_CR8","doi-asserted-by":"publisher","first-page":"1169","DOI":"10.1101\/gr.5235706","volume":"16","author":"J. Flannick","year":"2006","unstructured":"Flannick, J., Novak, A., Srinivasan, B.S., McAdams, H.H., Batzoglou, S.: Graemlin: general and robust alignment of multiple large interaction networks.. Genome Res.\u00a016(9), 1169\u20131181 (2006)","journal-title":"Genome Res."},{"key":"20_CR9","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/BF02579036","volume":"11","author":"M. Guignard","year":"2003","unstructured":"Guignard, M.: Lagrangean relaxation. Top\u00a011, 151\u2013200 (2003)","journal-title":"Top"},{"key":"20_CR10","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1007\/BF01584070","volume":"1","author":"M. Held","year":"1971","unstructured":"Held, M., Karp, R.M.: The traveling-salesman problem and minimum spanning trees: Part II. Math. Program\u00a01, 6\u201325 (1971)","journal-title":"Math. Program"},{"issue":"1","key":"20_CR11","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1186\/1471-2164-11-717","volume":"11","author":"S. Jaeger","year":"2010","unstructured":"Jaeger, S., Sers, C., Leser, U.: Combining modularity, conservation, and interactions of proteins significantly increases precision and coverage of protein function prediction. BMC Genomics\u00a011(1), 717 (2010)","journal-title":"BMC Genomics"},{"key":"20_CR12","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1093\/nar\/gkj102","volume":"34","author":"M. Kanehisa","year":"2006","unstructured":"Kanehisa, M., Goto, S., Hattori, M., et al.: From genomics to chemical genomics: new developments in KEGG. Nucleic Acids Res.\u00a034, 354\u2013357 (2006)","journal-title":"Nucleic Acids Res."},{"key":"20_CR13","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"20","key":"20_CR14","doi-asserted-by":"publisher","first-page":"11394","DOI":"10.1073\/pnas.1534710100","volume":"100","author":"B.P. Kelley","year":"2003","unstructured":"Kelley, B.P., Sharan, R., Karp, R.M., et al.: Conserved pathways within bacteria and yeast as revealed by global protein network alignment. P. Natl. Acad. Sci. USA\u00a0100(20), 11394\u201311399 (2003)","journal-title":"P. Natl. Acad. Sci. USA"},{"issue":"suppl.1","key":"20_CR15","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1186\/1471-2105-10-S1-S59","volume":"10","author":"G.W. Klau","year":"2009","unstructured":"Klau, G.W.: A new graph-based method for pairwise global network alignment.. BMC Bioinform.\u00a010(suppl.1), S59 (2009)","journal-title":"BMC Bioinform."},{"issue":"2","key":"20_CR16","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1089\/cmb.2006.13.182","volume":"13","author":"M. Koyut\u00fcrk","year":"2006","unstructured":"Koyut\u00fcrk, M., Kim, Y., Topkara, U., et al.: Pairwise alignment of protein interaction networks.. J. Comput. Biol.\u00a013(2), 182\u2013199 (2006)","journal-title":"J. Comput. Biol."},{"issue":"50","key":"20_CR17","doi-asserted-by":"publisher","first-page":"1341","DOI":"10.1098\/rsif.2010.0063","volume":"7","author":"O. Kuchaiev","year":"2010","unstructured":"Kuchaiev, O., Milenkovic, T., Memisevic, V., Hayes, W., Przulj, N.: Topological network alignment uncovers biological function and phylogeny.. J. R. Soc. Interface\u00a07(50), 1341\u20131354 (2010)","journal-title":"J. R. Soc. Interface"},{"issue":"1-2","key":"20_CR18","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1002\/nav.3800020109","volume":"2","author":"H.W. Kuhn","year":"1955","unstructured":"Kuhn, H.W.: The Hungarian method for the assignment problem. Nav. Res. Logist. Q\u00a02(1-2), 83\u201397 (1955)","journal-title":"Nav. Res. Logist. Q"},{"issue":"4","key":"20_CR19","doi-asserted-by":"publisher","first-page":"586","DOI":"10.1287\/mnsc.9.4.586","volume":"9","author":"E.L. Lawler","year":"1963","unstructured":"Lawler, E.L.: The quadratic assignment problem. Manage. Sci.\u00a09(4), 586\u2013599 (1963)","journal-title":"Manage. Sci."},{"key":"20_CR20","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1137\/0105003","volume":"5","author":"J. Munkres","year":"1957","unstructured":"Munkres, J.: Algorithms for the assignment and transportation problems. SIAM J. Appl. Math.\u00a05, 32\u201338 (1957)","journal-title":"SIAM J. Appl. Math."},{"issue":"4","key":"20_CR21","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1038\/nbt1196","volume":"24","author":"R. Sharan","year":"2006","unstructured":"Sharan, R., Ideker, T.: Modeling cellular machinery through biological network comparison.. Nat. Biotechnol.\u00a024(4), 427\u2013433 (2006)","journal-title":"Nat. Biotechnol."},{"issue":"6","key":"20_CR22","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1089\/cmb.2005.12.835","volume":"12","author":"R. Sharan","year":"2005","unstructured":"Sharan, R., Ideker, T., Kelley, B., Shamir, R., Karp, R.M.: Identification of protein complexes by comparative analysis of yeast and bacterial protein interaction data. J. Comput. Biol.\u00a012(6), 835\u2013846 (2005)","journal-title":"J. Comput. Biol."},{"issue":"35","key":"20_CR23","doi-asserted-by":"publisher","first-page":"12763","DOI":"10.1073\/pnas.0806627105","volume":"105","author":"R. Singh","year":"2008","unstructured":"Singh, R., Xu, J., Berger, B.: Global alignment of multiple protein interaction networks with application to functional orthology detection.. P. Natl. Acad. Sci. USA\u00a0105(35), 12763\u201312768 (2008)","journal-title":"P. Natl. Acad. Sci. USA"},{"key":"20_CR24","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1093\/nar\/gkq973","volume":"39","author":"D. Szklarczyk","year":"2010","unstructured":"Szklarczyk, D., Franceschini, A., Kuhn, M., et al.: The STRING database in 2011: functional interaction networks of proteins, globally integrated and scored. Nucleic Acids Res.\u00a039, 561\u2013568 (2010)","journal-title":"Nucleic Acids Res."},{"key":"20_CR25","doi-asserted-by":"crossref","unstructured":"Wohlers, I., Andonov, R., Klau, G.W.: Algorithm engineering for optimal alignment of protein structure distance matrices. Optim. Lett. (2011)","DOI":"10.1007\/s11590-011-0313-3"}],"container-title":["Lecture Notes in Computer Science","Pattern Recognition in Bioinformatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-24855-9_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,14]],"date-time":"2019-04-14T10:03:24Z","timestamp":1555236204000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-24855-9_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642248542","9783642248559"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-24855-9_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}