{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,25]],"date-time":"2026-01-25T19:46:37Z","timestamp":1769370397269,"version":"3.49.0"},"reference-count":43,"publisher":"Oxford University Press (OUP)","issue":"7","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013,4,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Given protein\u2013protein interaction (PPI) networks of a pair of species, a pairwise global alignment corresponds to a one-to-one mapping between their proteins. Based on the presupposition that such a mapping provides pairs of functionally orthologous proteins accurately, the results of the alignment may then be used in comparative systems biology problems such as function prediction\/verification or construction of evolutionary relationships.<\/jats:p>\n               <jats:p>Results: We show that the problem is NP-hard even for the case where the pair of networks are simply paths. We next provide a polynomial time heuristic algorithm, SPINAL, which consists of two main phases. In the first coarse-grained alignment phase, we construct all pairwise initial similarity scores based on pairwise local neighborhood matchings. Using the produced similarity scores, the fine-grained alignment phase produces the final one-to-one mapping by iteratively growing a locally improved solution subset. Both phases make use of the construction of neighborhood bipartite graphs and the contributors as a common primitive. We assess the performance of our algorithm on the PPI networks of yeast, fly, human and worm. We show that based on the accuracy measures used in relevant work, our method outperforms the state-of-the-art algorithms. Furthermore, our algorithm does not suffer from scalability issues, as such accurate results are achieved in reasonable running times as compared with the benchmark algorithms.<\/jats:p>\n               <jats:p>Availability: Supplementary Document, open source codes, useful scripts, all the experimental data and the results are freely available at http:\/\/code.google.com\/p\/spinal\/.<\/jats:p>\n               <jats:p>Contact: \u00a0cesim@khas.edu.tr<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btt071","type":"journal-article","created":{"date-parts":[[2013,2,15]],"date-time":"2013-02-15T04:03:00Z","timestamp":1360900980000},"page":"917-924","source":"Crossref","is-referenced-by-count":111,"title":["SPINAL: scalable protein interaction network alignment"],"prefix":"10.1093","volume":"29","author":[{"given":"Ahmet E.","family":"Alada\u011f","sequence":"first","affiliation":[{"name":"1 Department of Computer Engineering, Bogazi\u00e7i University, Bebek, Istanbul 34342 and 2Department of Computer Engineering, Kadir Has University, Cibali, Istanbul 34083 Turkey"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cesim","family":"Erten","sequence":"additional","affiliation":[{"name":"1 Department of Computer Engineering, Bogazi\u00e7i University, Bebek, Istanbul 34342 and 2Department of Computer Engineering, Kadir Has University, Cibali, Istanbul 34083 Turkey"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2013,2,14]]},"reference":[{"key":"2023020303304883200_btt071-B1","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1038\/nature01511","article-title":"Mass spectrometry-based proteomics","volume":"422","author":"Aebersold","year":"2003","journal-title":"Nature"},{"key":"2023020303304883200_btt071-B2","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","article-title":"Basic local alignment search tool","volume":"215","author":"Altschul","year":"1990","journal-title":"J. Mol. Biol."},{"key":"2023020303304883200_btt071-B3","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":"2023020303304883200_btt071-B4","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1089\/cmb.2010.0280","article-title":"Submap: aligning metabolic pathways with subnetwork mappings","volume":"18","author":"Ay","year":"2011","journal-title":"J. Comput. Biol."},{"key":"2023020303304883200_btt071-B5","doi-asserted-by":"crossref","first-page":"991","DOI":"10.1038\/nbt1002-991","article-title":"Analyzing yeast protein-protein interaction data obtained from different sources","volume":"20","author":"Bader","year":"2002","journal-title":"Nat. Biotechnol."},{"key":"2023020303304883200_btt071-B6","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":"2023020303304883200_btt071-B7","doi-asserted-by":"crossref","first-page":"R138","DOI":"10.1186\/gb-2008-9-9-r138","article-title":"NetGrep: fast network schema searches in interactomes","volume":"9","author":"Banks","year":"2008","journal-title":"Genome Biol."},{"key":"2023020303304883200_btt071-B8","article-title":"Extracting information from biological networks","author":"Chindelevitch","year":"2010"},{"key":"2023020303304883200_btt071-B9","first-page":"123","article-title":"Local optimization for global alignment of protein interaction networks","volume-title":"Pacific Symposium on Biocomputing","author":"Chindelevitch","year":"2010"},{"key":"2023020303304883200_btt071-B10","doi-asserted-by":"crossref","first-page":"913","DOI":"10.1089\/cmb.2007.0172","article-title":"QNet: a tool for querying protein interaction networks","volume":"15","author":"Dost","year":"2008","journal-title":"J. Comput. Biol."},{"key":"2023020303304883200_btt071-B11","doi-asserted-by":"crossref","first-page":"i149","DOI":"10.1093\/bioinformatics\/btm194","article-title":"Identification of functional modules from conserved ancestral protein\u2013protein interactions","volume":"23","author":"Dutkowski","year":"2007","journal-title":"Bioinformatics"},{"key":"2023020303304883200_btt071-B12","doi-asserted-by":"crossref","first-page":"12980","DOI":"10.1073\/pnas.91.26.12980","article-title":"Interaction mating reveals binary and ternary connections between drosophila cell cycle regulators","volume":"91","author":"Finley","year":"1994","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023020303304883200_btt071-B13","doi-asserted-by":"crossref","first-page":"1169","DOI":"10.1101\/gr.5235706","article-title":"Graemlin: general and robust alignment of multiple large interaction networks","volume":"16","author":"Flannick","year":"2006","journal-title":"Genome Res."},{"key":"2023020303304883200_btt071-B14","doi-asserted-by":"crossref","first-page":"1135","DOI":"10.1093\/bioinformatics\/btr099","article-title":"Connectedness of PPI network neighborhoods identifies regulatory hub proteins","volume":"27","author":"Fox","year":"2011","journal-title":"Bioinformatics"},{"key":"2023020303304883200_btt071-B15","volume-title":"Computers and Intractability: a Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"key":"2023020303304883200_btt071-B16","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0022-2836(02)01038-0","article-title":"Co-evolutionary analysis reveals insights into protein-protein interactions","volume":"324","author":"Goh","year":"2002","journal-title":"J. Mol. Biol."},{"key":"2023020303304883200_btt071-B17","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1038\/nature02555","article-title":"Evidence for dynamically organized modularity in the yeast proteinprotein interaction network","volume":"430","author":"Han","year":"2004","journal-title":"Nature"},{"key":"2023020303304883200_btt071-B18","article-title":"Molecular modeling: basic principles and applications","volume-title":"Methods and Principles in Medicinal Chemistry","author":"H\u00f6ltje","year":"1997"},{"key":"2023020303304883200_btt071-B19","doi-asserted-by":"crossref","first-page":"750","DOI":"10.1126\/science.1068696","article-title":"Evolutionary rate in the protein interaction network","volume":"296","author":"Hunter","year":"2002","journal-title":"Science"},{"key":"2023020303304883200_btt071-B20","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":"2023020303304883200_btt071-B21","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":"2023020303304883200_btt071-B22","doi-asserted-by":"crossref","first-page":"S59","DOI":"10.1186\/1471-2105-10-S1-S59","article-title":"A new graph-based method for pairwise global network alignment","volume":"10","author":"Klau","year":"2009","journal-title":"BMC Bioinformatics"},{"key":"2023020303304883200_btt071-B23","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1089\/cmb.2006.13.182","article-title":"Pairwise alignment of protein interaction networks","volume":"13","author":"Koyut\u00fcrk","year":"2006","journal-title":"J. Comput. Biol."},{"key":"2023020303304883200_btt071-B24","doi-asserted-by":"crossref","first-page":"1390","DOI":"10.1093\/bioinformatics\/btr127","article-title":"Integrative network alignment reveals large regions of global network similarity in yeast and human","volume":"27","author":"Kuchaiev","year":"2011","journal-title":"Bioinformatics"},{"key":"2023020303304883200_btt071-B25","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":"2023020303304883200_btt071-B26","doi-asserted-by":"crossref","first-page":"i253","DOI":"10.1093\/bioinformatics\/btp203","article-title":"IsoRankN: spectral methods for global alignment of multiple protein networks","volume":"25","author":"Liao","year":"2009","journal-title":"Bioinformatics"},{"key":"2023020303304883200_btt071-B27","doi-asserted-by":"crossref","first-page":"e7546","DOI":"10.1371\/journal.pone.0007546","article-title":"A statistical model of protein sequence similarity and function similarity reveals overly-specific function predictions","volume":"4","author":"Louie","year":"2009","journal-title":"PLoS One"},{"key":"2023020303304883200_btt071-B28","volume-title":"Leda: A Platform for Combinatorial and Geometric Computing","author":"Mehlhorn","year":"1999"},{"key":"2023020303304883200_btt071-B29","doi-asserted-by":"crossref","first-page":"734","DOI":"10.1039\/c2ib00140c","article-title":"C-graal: common-neighbors-based global graph alignment of biological networks","volume":"4","author":"Memi\u0161evi\u0107","year":"2012","journal-title":"Integr. Biol."},{"key":"2023020303304883200_btt071-B30","doi-asserted-by":"crossref","first-page":"121","DOI":"10.4137\/CIN.S4744","article-title":"Optimal network alignment with graphlet degree vectors","volume":"9","author":"Milenkovi\u0107","year":"2010","journal-title":"Cancer Inform."},{"key":"2023020303304883200_btt071-B31","doi-asserted-by":"crossref","first-page":"892","DOI":"10.1089\/cmb.2007.0025","article-title":"Comparing protein interaction networks via a graph match-and-split algorithm","volume":"14","author":"Narayanan","year":"2007","journal-title":"J. Comput. Biol."},{"key":"2023020303304883200_btt071-B32","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1093\/nar\/gkq1234","article-title":"IsoBase: a database of functionally related proteins across PPI networks","volume":"39","author":"Park","year":"2011","journal-title":"Nucleic Acids Res."},{"key":"2023020303304883200_btt071-B33","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":"2023020303304883200_btt071-B34","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1023\/A:1021271615909","article-title":"Maximum common subgraph isomorphism algorithms for the matching of chemical structures","volume":"16","author":"Raymond","year":"2002","journal-title":"J. Comput. Aided Mol. Des."},{"key":"2023020303304883200_btt071-B35","doi-asserted-by":"crossref","first-page":"1041","DOI":"10.1006\/jmbi.2000.5197","article-title":"Automatic clustering of orthologs and in-paralogs from pairwise species comparisons","volume":"314","author":"Remm","year":"2001","journal-title":"J. Mol. Biol."},{"key":"2023020303304883200_btt071-B36","doi-asserted-by":"crossref","first-page":"e41474","DOI":"10.1371\/journal.pone.0041474","article-title":"A network synthesis model for generating protein interaction network families","volume":"7","author":"Sahraeian","year":"2012","journal-title":"PLoS One"},{"key":"2023020303304883200_btt071-B37","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":"2023020303304883200_btt071-B38","doi-asserted-by":"crossref","first-page":"1974","DOI":"10.1073\/pnas.0409522102","article-title":"Conserved patterns of protein interaction in multiple species","volume":"102","author":"Sharan","year":"2005","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023020303304883200_btt071-B39","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1038\/msb4100129","article-title":"Network-based prediction of protein function","volume":"3","author":"Sharan","year":"2007","journal-title":"Mol. Syst. Biol."},{"key":"2023020303304883200_btt071-B40","first-page":"96","article-title":"Scalable multiple global network alignment for biological data","volume-title":"Proceedings of ACM-BCB","author":"Shih","year":"2011"},{"key":"2023020303304883200_btt071-B41","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1186\/1471-2105-7-199","article-title":"QPath: a method for querying pathways in a protein-protein interaction network","volume":"7","author":"Shlomi","year":"2006","journal-title":"BMC Bioinformatics"},{"key":"2023020303304883200_btt071-B42","first-page":"303","article-title":"Global alignment of multiple protein interaction networks","volume-title":"Pacific Symposium on Biocomputing","author":"Singh","year":"2008"},{"key":"2023020303304883200_btt071-B43","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1093\/bioinformatics\/btp196","article-title":"Global alignment of protein-protein interaction networks by graph matching methods","volume":"25","author":"Zaslavskiy","year":"2009","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/29\/7\/917\/49060828\/bioinformatics_29_7_917.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/29\/7\/917\/49060828\/bioinformatics_29_7_917.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,3]],"date-time":"2023-02-03T03:32:12Z","timestamp":1675395132000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/29\/7\/917\/253874"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,2,14]]},"references-count":43,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2013,4,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btt071","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2013,4,1]]},"published":{"date-parts":[[2013,2,14]]}}}