{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,2]],"date-time":"2026-10-02T03:56:03Z","timestamp":1790913363921,"version":"4.1.0"},"reference-count":17,"publisher":"Oxford University Press (OUP)","issue":"23","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005,12,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Motivation: Modern comparative genomics does not restrict to sequence but involves the comparison of metabolic pathways or protein\u2013protein interactions as well. Central in this approach is the concept of neighbourhood between entities (genes, proteins, chemical compounds). Therefore there is a growing need for new methods aiming at merging the connectivity information from different biological sources in order to infer functional coupling.<\/jats:p><jats:p>Results: We present a generic approach to merge the information from two or more graphs representing biological data. The method is based on two concepts. The first one, the correspondence multigraph, precisely defines how correspondence is performed between the primary data-graphs. The second one, the common connected components, defines which property of the multigraph is searched for. Although this problem has already been informally stated in the past few years, we give here a formal and general statement together with an exact algorithm to solve it.<\/jats:p><jats:p>Availability: The algorithm presented in this paper has been implemented in C. Source code is freely available for download at:<\/jats:p><jats:p>Contact: Alain.Viari@inrialpes.fr<\/jats:p>","DOI":"10.1093\/bioinformatics\/bti711","type":"journal-article","created":{"date-parts":[[2005,10,11]],"date-time":"2005-10-11T00:23:46Z","timestamp":1128990226000},"page":"4209-4215","source":"Crossref","is-referenced-by-count":51,"title":["Syntons, metabolons and interactons: an exact graph-theoretical approach for exploring neighbourhood between genomic and functional data"],"prefix":"10.1093","volume":"21","author":[{"given":"Fr\u00e9d\u00e9ric","family":"Boyer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anne","family":"Morgat","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Laurent","family":"Labarre","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jo\u00ebl","family":"Pothier","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alain","family":"Viari","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2005,10,10]]},"reference":[{"key":"2023061009524783900_b1","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/S0959-440X(03)00031-9","article-title":"Biological networks","volume":"13","author":"Alm","year":"2003","journal-title":"Curr. Opin. Struct. Biol."},{"key":"2023061009524783900_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":"2023061009524783900_b3","article-title":"Identifying common connected components of graphs","volume-title":"Report RR-LIRMM-03016","author":"Gai","year":"2003"},{"key":"2023061009524783900_b4","doi-asserted-by":"crossref","first-page":"609","DOI":"10.1038\/76443","article-title":"Who's your neighbor? New computational approaches for functional genomics","volume":"18","author":"Galperin","year":"2000","journal-title":"Nat. Biotechnol."},{"key":"2023061009524783900_b5","first-page":"359","article-title":"Maximal common connected sets of interval graphs","author":"Habib","year":"2004"},{"key":"2023061009524783900_b6","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":"2023061009524783900_b7","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":"2023061009524783900_b8","doi-asserted-by":"crossref","first-page":"751","DOI":"10.1126\/science.285.5428.751","article-title":"Detecting protein function and protein\u2013protein interactions from genome sequences","volume":"285","author":"Marcotte","year":"1999","journal-title":"Science"},{"key":"2023061009524783900_b9","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":"2023061009524783900_b10","doi-asserted-by":"crossref","first-page":"2896","DOI":"10.1073\/pnas.96.6.2896","article-title":"The use of gene clusters to infer functional coupling","volume":"96","author":"Overbeek","year":"1999","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023061009524783900_b11","doi-asserted-by":"crossref","first-page":"D303","DOI":"10.1093\/nar\/gkh140","article-title":"RegulonDB (version 4.0): transcriptional regulation, operon organization and growth conditions in Escherichia coli K-12","volume":"32","author":"Salgado","year":"2004","journal-title":"Nucleic Acids Res."},{"key":"2023061009524783900_b12","doi-asserted-by":"crossref","first-page":"D449","DOI":"10.1093\/nar\/gkh086","article-title":"The database of interacting proteins: 2004 update","volume":"32","author":"Salwinski","year":"2004","journal-title":"Nucleic Acids Res."},{"key":"2023061009524783900_b13","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":"2023061009524783900_b14","doi-asserted-by":"crossref","first-page":"5890","DOI":"10.1073\/pnas.092632599","article-title":"The identification of functional modules from the genomic association of genes","volume":"99","author":"Snel","year":"2002","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023061009524783900_b15","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1126\/science.278.5338.631","article-title":"A genomic perspective on protein families","volume":"278","author":"Tatusov","year":"1997","journal-title":"Science"},{"key":"2023061009524783900_b16","doi-asserted-by":"crossref","DOI":"10.1186\/gb-2002-3-11-research0064","article-title":"The society of genes: networks of functional links between genes from comparative genomics","volume":"3","author":"Yanai","year":"2002","journal-title":"Genome Biol."},{"key":"2023061009524783900_b17","doi-asserted-by":"crossref","first-page":"1221","DOI":"10.1101\/gr.200602","article-title":"Computational identification of operons in microbial genomes","volume":"12","author":"Zheng","year":"2002","journal-title":"Genome Res."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/21\/23\/4209\/50567317\/bioinformatics_21_23_4209.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/21\/23\/4209\/50567317\/bioinformatics_21_23_4209.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,30]],"date-time":"2024-01-30T21:43:58Z","timestamp":1706651038000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/21\/23\/4209\/195480"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,10,10]]},"references-count":17,"journal-issue":{"issue":"23","published-print":{"date-parts":[[2005,12,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bti711","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2005,12]]},"published":{"date-parts":[[2005,10,10]]}}}