{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T23:25:26Z","timestamp":1771025126681,"version":"3.50.1"},"reference-count":41,"publisher":"Oxford University Press (OUP)","issue":"23","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012,12,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Protein interaction networks provide an important system-level view of biological processes. One of the fundamental problems in biological network analysis is the global alignment of a pair of networks, which puts the proteins of one network into correspondence with the proteins of another network in a manner that conserves their interactions while respecting other evidence of their homology. By providing a mapping between the networks of different species, alignments can be used to inform hypotheses about the functions of unannotated proteins, the existence of unobserved interactions, the evolutionary divergence between the two species and the evolution of complexes and pathways.<\/jats:p>\n               <jats:p>Results: We introduce GHOST, a global pairwise network aligner that uses a novel spectral signature to measure topological similarity between subnetworks. It combines a seed-and-extend global alignment phase with a local search procedure and exceeds state-of-the-art performance on several network alignment tasks. We show that the spectral signature used by GHOST is highly discriminative, whereas the alignments it produces are also robust to experimental noise. When compared with other recent approaches, we find that GHOST is able to recover larger and more biologically significant, shared subnetworks between species.<\/jats:p>\n               <jats:p>Availability: An efficient and parallelized implementation of GHOST, released under the Apache 2.0 license, is available at http:\/\/cbcb.umd.edu\/kingsford_group\/ghost<\/jats:p>\n               <jats:p>Contact: \u00a0rob@cs.umd.edu<\/jats:p>","DOI":"10.1093\/bioinformatics\/bts592","type":"journal-article","created":{"date-parts":[[2012,10,10]],"date-time":"2012-10-10T08:45:27Z","timestamp":1349858727000},"page":"3105-3114","source":"Crossref","is-referenced-by-count":167,"title":["Global network alignment using multiscale spectral signatures"],"prefix":"10.1093","volume":"28","author":[{"given":"Rob","family":"Patro","sequence":"first","affiliation":[]},{"given":"Carl","family":"Kingsford","sequence":"additional","affiliation":[]}],"member":"286","published-online":{"date-parts":[[2012,10,9]]},"reference":[{"key":"2023062411494503400_bts592-B1","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":"2023062411494503400_bts592-B2","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1038\/75556","article-title":"Gene Ontology: tool for the unification of biology. The Gene Ontology Consortium","volume":"25","author":"Ashburner","year":"2000","journal-title":"Nat. Genet."},{"key":"2023062411494503400_bts592-B3","doi-asserted-by":"crossref","DOI":"10.1145\/800070.802206","article-title":"Isomorphism of graphs with bounded eigenvalue multiplicity","volume-title":"Proceeding of the 14th Annual ACM Symposium on Theory of Computing","author":"Babai","year":"1982"},{"key":"2023062411494503400_bts592-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":"2023062411494503400_bts592-B5","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1016\/j.biosystems.2011.11.004","article-title":"Structural distance and evolutionary relationship of networks","volume":"107","author":"Banerjee","year":"2012","journal-title":"Biosystems"},{"key":"2023062411494503400_bts592-B6","first-page":"123","article-title":"Local optimization for global alignment of protein interaction networks","volume":"132","author":"Chindelevitch","year":"2010","journal-title":"Pac. Symp. Biocomput."},{"key":"2023062411494503400_bts592-B7","volume-title":"Spectral Graph Theory","author":"Chung","year":"1997"},{"key":"2023062411494503400_bts592-B8","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1074\/mcp.M600381-MCP200","article-title":"Toward a comprehensive atlas of the physical interactome of Saccharomyces cerevisiae","volume":"6","author":"Collins","year":"2007","journal-title":"Mol. Cell Proteomics"},{"key":"2023062411494503400_bts592-B9","first-page":"2383","article-title":"A tensor-based algorithm for high-order graph matching. IEEE Trans. Pattern Anal","volume":"33","author":"Duchenne","year":"2011","journal-title":"Mach. Intell."},{"key":"2023062411494503400_bts592-B10","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/978-3-642-24855-9_20","article-title":"Lagrangian relaxation applied to sparse global network alignment","volume-title":"Pattern Recognition in Bioinformatics","author":"El-Kebir","year":"2011"},{"key":"2023062411494503400_bts592-B11","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1038\/340245a0","article-title":"A novel genetic system to detect protein-protein interactions","volume":"340","author":"Fields","year":"1989","journal-title":"Nature"},{"key":"2023062411494503400_bts592-B12","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":"2023062411494503400_bts592-B13","doi-asserted-by":"crossref","first-page":"1001","DOI":"10.1089\/cmb.2009.0099","article-title":"Automatic parameter learning for multiple local network alignment","volume":"16","author":"Flannick","year":"2009","journal-title":"J. Computat. Biol."},{"key":"2023062411494503400_bts592-B14","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1038\/nature04532","article-title":"Proteome survey reveals modularity of the yeast cell machinery","volume":"440","author":"Gavin","year":"2006","journal-title":"Nature"},{"key":"2023062411494503400_bts592-B15","doi-asserted-by":"crossref","first-page":"717","DOI":"10.1186\/1471-2164-11-717","article-title":"Combining modularity, conservation, and interactions of proteins significantly increases precision and coverage of protein function prediction","volume":"11","author":"Jaeger","year":"2010","journal-title":"BMC Genomics"},{"key":"2023062411494503400_bts592-B16","doi-asserted-by":"crossref","first-page":"1497","DOI":"10.1126\/science.1141319","article-title":"Genome-wide mapping of in vivo protein-DNA interactions","volume":"316","author":"Johnson","year":"2007","journal-title":"Science"},{"key":"2023062411494503400_bts592-B17","doi-asserted-by":"crossref","first-page":"D277","DOI":"10.1093\/nar\/gkh063","article-title":"The KEGG resource for deciphering the genome","volume":"32","author":"Kanehisa","year":"2004","journal-title":"Nucleic Acids Res."},{"key":"2023062411494503400_bts592-B18","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":"2023062411494503400_bts592-B19","doi-asserted-by":"crossref","first-page":"1","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":"2023062411494503400_bts592-B20","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":"2023062411494503400_bts592-B21","doi-asserted-by":"crossref","first-page":"1094","DOI":"10.1137\/0613066","article-title":"Estimating the largest eigenvalue by the power and lanczos algorithms with a random start","volume":"4","author":"Kuczynski","year":"1992","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"2023062411494503400_bts592-B22","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":"Nav. Res. Logist. Q."},{"key":"2023062411494503400_bts592-B23","first-page":"1482","article-title":"A spectral technique for correspondence problems using pairwise constraints","volume-title":"Tenth IEEE International Conference on Computer Vision ICCV05","author":"Leordeanu","year":"2005"},{"key":"2023062411494503400_bts592-B24","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":"2023062411494503400_bts592-B25","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\u00e7","year":"2010","journal-title":"Cancer Inform."},{"key":"2023062411494503400_bts592-B26","doi-asserted-by":"crossref","DOI":"10.1109\/SIBGRAPI.2010.33","article-title":"Sparse representations for efficient shape matching","volume-title":"Graphics, Patterns and Images (SIBGRAPI)","author":"Noma","year":"2010"},{"key":"2023062411494503400_bts592-B27","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1186\/1756-0381-1-11","article-title":"Fast gene ontology based clustering for microarray experiments","volume":"1","author":"Ovaska","year":"2008","journal-title":"BioData Min."},{"key":"2023062411494503400_bts592-B28","doi-asserted-by":"crossref","DOI":"10.1145\/301250.301389","article-title":"The complexity of the matrix eigenproblem","volume-title":"Proceedings of the Thirty-first Annual ACM Symposium on Theory of Computing","author":"Pan","year":"1999"},{"key":"2023062411494503400_bts592-B29","doi-asserted-by":"crossref","first-page":"D295","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":"2023062411494503400_bts592-B30","doi-asserted-by":"crossref","first-page":"R130","DOI":"10.1186\/gb-2007-8-7-r130","article-title":"A proteome-wide protein interaction map for Campylobacter jejuni","volume":"8","author":"Parrish","year":"2007","journal-title":"Genome Biol."},{"key":"2023062411494503400_bts592-B31","doi-asserted-by":"crossref","first-page":"D744","DOI":"10.1093\/nar\/gkq897","article-title":"HitPredict: a database of quality assessed protein\u2013protein interactions in nine species","volume":"39","author":"Patil","year":"2011","journal-title":"Nucleic Acids Res."},{"key":"2023062411494503400_bts592-B32","doi-asserted-by":"crossref","first-page":"e1000523","DOI":"10.1371\/journal.pcbi.1000523","article-title":"The modular organization of protein interactions in Escherichia coli","volume":"5","author":"Peregr\u00edn-Alvarez","year":"2009","journal-title":"PLoS Comput. Biol."},{"key":"2023062411494503400_bts592-B33","doi-asserted-by":"crossref","first-page":"e1000443","DOI":"10.1371\/journal.pcbi.1000443","article-title":"Semantic similarity in biomedical ontologies","volume":"5","author":"Pesquita","year":"2009","journal-title":"PLoS Comput. Biol."},{"key":"2023062411494503400_bts592-B34","doi-asserted-by":"crossref","first-page":"2686","DOI":"10.1109\/CDC.2010.5717228","article-title":"From local measurements to network spectral properties: beyond degree distributions","volume-title":"49th IEEE Conference on Decision and Control","author":"Preciado","year":"2010"},{"key":"2023062411494503400_bts592-B35","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":"2023062411494503400_bts592-B36","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1093\/dnares\/dsm028","article-title":"A large scale analysis of protein\u2013protein interactions in the nitrogen-fixing bacterium Mesorhizobium loti","volume":"15","author":"Shimoda","year":"2008","journal-title":"DNA Res."},{"key":"2023062411494503400_bts592-B37","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":"2023062411494503400_bts592-B38","first-page":"99","article-title":"Pairwise alignment of interaction networks by fast identification of maximal conserved patterns","author":"Tian","year":"2009","journal-title":"Pac. Symp. Biocomput."},{"key":"2023062411494503400_bts592-B39","first-page":"596","article-title":"Feature correspondence via graph matching: models and global optimization","volume-title":"European Conference on Computer Vision","author":"Torresani","year":"2008"},{"key":"2023062411494503400_bts592-B40","doi-asserted-by":"crossref","first-page":"2833","DOI":"10.1016\/j.patcog.2008.03.011","article-title":"A study of graph spectra for comparing graphs and trees","volume":"41","author":"Wilson","year":"2008","journal-title":"Pattern Recogn."},{"key":"2023062411494503400_bts592-B41","doi-asserted-by":"crossref","first-page":"i259","DOI":"10.1093\/bioinformatics\/btp196","article-title":"Global alignment of protein\u2013protein 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\/28\/23\/3105\/50694929\/bioinformatics_28_23_3105.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/28\/23\/3105\/50694929\/bioinformatics_28_23_3105.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,25]],"date-time":"2023-06-25T00:26:58Z","timestamp":1687652818000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/28\/23\/3105\/195325"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,10,9]]},"references-count":41,"journal-issue":{"issue":"23","published-print":{"date-parts":[[2012,12,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bts592","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2012,12]]},"published":{"date-parts":[[2012,10,9]]}}}