Ontology type: schema:Chapter Open Access: True
2017-04-25
AUTHORSAlessio Conte , Roberto Grossi , Andrea Marino , Lorenzo Tattini , Luca Versari
ABSTRACTWe present a fast algorithm for finding large common subgraphs, which can be exploited for detecting structural and functional relationships between biological macromolecules. Many fast algorithms exist for finding a single maximum common subgraph. We show with an example that this gives limited information, motivating the less studied problem of finding many large common subgraphs covering different areas. As the latter is also hard, we give heuristics that improve performance by several orders of magnitude. As a case study, we validate our findings experimentally on protein graphs with thousands of atoms. More... »
PAGES62-74
Algorithms for Computational Biology
ISBN
978-3-319-58162-0
978-3-319-58163-7
http://scigraph.springernature.com/pub.10.1007/978-3-319-58163-7_4
DOIhttp://dx.doi.org/10.1007/978-3-319-58163-7_4
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1086868821
JSON-LD is the canonical representation for SciGraph data.
TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT
[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
"about": [
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0601",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Biochemistry and Cell Biology",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/06",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Biological Sciences",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "University of Pisa",
"id": "https://www.grid.ac/institutes/grid.5395.a",
"name": [
"Inria, Universit\u00e0 di Pisa and Erable, Pisa, Italy"
],
"type": "Organization"
},
"familyName": "Conte",
"givenName": "Alessio",
"id": "sg:person.013571166511.36",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013571166511.36"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "University of Pisa",
"id": "https://www.grid.ac/institutes/grid.5395.a",
"name": [
"Inria, Universit\u00e0 di Pisa and Erable, Pisa, Italy"
],
"type": "Organization"
},
"familyName": "Grossi",
"givenName": "Roberto",
"id": "sg:person.01062373707.91",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01062373707.91"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "University of Pisa",
"id": "https://www.grid.ac/institutes/grid.5395.a",
"name": [
"Inria, Universit\u00e0 di Pisa and Erable, Pisa, Italy"
],
"type": "Organization"
},
"familyName": "Marino",
"givenName": "Andrea",
"id": "sg:person.07515532766.37",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07515532766.37"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Institute of Research on Cancer and Aging in Nice",
"id": "https://www.grid.ac/institutes/grid.463830.a",
"name": [
"IRCAN, CNRS UMR, 7284, Nice, France"
],
"type": "Organization"
},
"familyName": "Tattini",
"givenName": "Lorenzo",
"id": "sg:person.0736724411.38",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0736724411.38"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Scuola Normale Superiore di Pisa",
"id": "https://www.grid.ac/institutes/grid.6093.c",
"name": [
"Scuola Normale Superiore, Pisa, Italy"
],
"type": "Organization"
},
"familyName": "Versari",
"givenName": "Luca",
"id": "sg:person.016171366611.54",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016171366611.54"
],
"type": "Person"
}
],
"citation": [
{
"id": "https://doi.org/10.1016/s0304-3975(00)00286-3",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1002396737"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/321921.321925",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1008268655"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0166-218x(95)00026-n",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1013152121"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11533719_73",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1017311354",
"https://doi.org/10.1007/11533719_73"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11533719_73",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1017311354",
"https://doi.org/10.1007/11533719_73"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1093/bioinformatics/btn307",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1025948952"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1006/jmbi.1994.1657",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1026428993"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1002/asi.20140",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1027402315"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1002/spe.588",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1027808390"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/s1359-6446(02)02411-x",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1032222306"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/s1359-6446(02)02411-x",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1032222306"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/1014052.1014123",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1035394118"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1002/spe.4380120103",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1039746604"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-55210-3_198",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1040657953",
"https://doi.org/10.1007/3-540-55210-3_198"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02575586",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1041808659",
"https://doi.org/10.1007/bf02575586"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02575586",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1041808659",
"https://doi.org/10.1007/bf02575586"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/362342.362367",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1049082651"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1093/bioinformatics/btn186",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1050561540"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0167-6377(90)90057-c",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1052413170"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0167-6377(90)90057-c",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1052413170"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1021/ci00056a002",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1055400933"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1021/ci9601675",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1055405148"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1021/ci9601675",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1055405148"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1089/cmb.1996.3.289",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1059245138"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1093/comjnl/45.6.631",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1059479450"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1504/ijbra.2013.054688",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1067439501"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.7155/jgaa.00139",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1073626425"
],
"type": "CreativeWork"
}
],
"datePublished": "2017-04-25",
"datePublishedReg": "2017-04-25",
"description": "We present a fast algorithm for finding large common subgraphs, which can be exploited for detecting structural and functional relationships between biological macromolecules. Many fast algorithms exist for finding a single maximum common subgraph. We show with an example that this gives limited information, motivating the less studied problem of finding many large common subgraphs covering different areas. As the latter is also hard, we give heuristics that improve performance by several orders of magnitude. As a case study, we validate our findings experimentally on protein graphs with thousands of atoms.",
"editor": [
{
"familyName": "Figueiredo",
"givenName": "Daniel",
"type": "Person"
},
{
"familyName": "Mart\u00edn-Vide",
"givenName": "Carlos",
"type": "Person"
},
{
"familyName": "Pratas",
"givenName": "Diogo",
"type": "Person"
},
{
"familyName": "Vega-Rodr\u00edguez",
"givenName": "Miguel A.",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-319-58163-7_4",
"inLanguage": [
"en"
],
"isAccessibleForFree": true,
"isFundedItemOf": [
{
"id": "sg:grant.6853177",
"type": "MonetaryGrant"
}
],
"isPartOf": {
"isbn": [
"978-3-319-58162-0",
"978-3-319-58163-7"
],
"name": "Algorithms for Computational Biology",
"type": "Book"
},
"name": "A Fast Algorithm for Large Common Connected Induced Subgraphs",
"pagination": "62-74",
"productId": [
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-319-58163-7_4"
]
},
{
"name": "readcube_id",
"type": "PropertyValue",
"value": [
"85a9d2a75643ce8eb1038d35a7e148d310c56f77b6ca4ad314372f449e3d5bef"
]
},
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1086868821"
]
}
],
"publisher": {
"location": "Cham",
"name": "Springer International Publishing",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-319-58163-7_4",
"https://app.dimensions.ai/details/publication/pub.1086868821"
],
"sdDataset": "chapters",
"sdDatePublished": "2019-04-16T05:02",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000325_0000000325/records_100819_00000000.jsonl",
"type": "Chapter",
"url": "https://link.springer.com/10.1007%2F978-3-319-58163-7_4"
}
]Download the RDF metadata as: json-ld nt turtle xml License info
JSON-LD is a popular format for linked data which is fully compatible with JSON.
curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-58163-7_4'
N-Triples is a line-based linked data format ideal for batch operations.
curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-58163-7_4'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-58163-7_4'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-58163-7_4'
This table displays all metadata directly associated to this object as RDF triples.
185 TRIPLES
23 PREDICATES
48 URIs
19 LITERALS
8 BLANK NODES