{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T04:11:00Z","timestamp":1772165460769,"version":"3.50.1"},"reference-count":70,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,4,22]],"date-time":"2021-04-22T00:00:00Z","timestamp":1619049600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"},{"start":{"date-parts":[[2021,4,22]],"date-time":"2021-04-22T00:00:00Z","timestamp":1619049600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100007364","name":"Fondazione CRT","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100007364","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007364","name":"Fondazione CRT","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100007364","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100012740","name":"Gruppo Nazionale per l\u2019Analisi Matematica, la Probabilit\u00e0e le loro Applicazioni","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100012740","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100012740","name":"Gruppo Nazionale per l\u2019Analisi Matematica, la Probabilit\u00e0e le loro Applicazioni","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100012740","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Background<\/jats:title>\n                    <jats:p>Graphs are mathematical structures widely used for expressing relationships among elements when representing biomedical and biological information. On top of these representations, several analyses are performed. A common task is the search of one substructure within one graph, called target. The problem is referred to as one-to-one subgraph search, and it is known to be NP-complete. Heuristics and indexing techniques can be applied to facilitate the search. Indexing techniques are also exploited in the context of searching in a collection of target graphs, referred to as one-to-many subgraph problem. Filter-and-verification methods that use indexing approaches provide a fast pruning of target graphs or parts of them that do not contain the query. The expensive verification phase is then performed only on the subset of promising targets. Indexing strategies extract graph features at a sufficient granularity level for performing a powerful filtering step. Features are memorized in data structures allowing an efficient access. Indexing size, querying time and filtering power are key points for the development of efficient subgraph searching solutions.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>An existing approach, GRAPES, has been shown to have good performance in terms of speed-up for both one-to-one and one-to-many cases. However, it suffers in the size of the built index. For this reason, we propose GRAPES-DD, a modified version of GRAPES in which the indexing structure has been replaced with a Decision Diagram. Decision Diagrams are a broad class of data structures widely used to encode and manipulate functions efficiently. Experiments on biomedical structures and synthetic graphs have confirmed our expectation showing that GRAPES-DD has substantially reduced the memory utilization compared to GRAPES without worsening the searching time.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Conclusion<\/jats:title>\n                    <jats:p>The use of Decision Diagrams for searching in biochemical and biological graphs is completely new and potentially promising thanks to their ability to encode compactly sets by exploiting their structure and regularity, and to manipulate entire sets of elements at once, instead of exploring each single element explicitly. Search strategies based on Decision Diagram makes the indexing for biochemical graphs, and not only, more affordable allowing us to potentially deal with huge and ever growing collections of biochemical and biological structures.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1186\/s12859-021-04129-0","type":"journal-article","created":{"date-parts":[[2021,4,22]],"date-time":"2021-04-22T06:07:13Z","timestamp":1619071633000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["GRAPES-DD: exploiting decision diagrams for index-driven search in biological graph databases"],"prefix":"10.1186","volume":"22","author":[{"given":"Nicola","family":"Licheri","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1637-7545","authenticated-orcid":false,"given":"Vincenzo","family":"Bonnici","sequence":"additional","affiliation":[]},{"given":"Marco","family":"Beccuti","sequence":"additional","affiliation":[]},{"given":"Rosalba","family":"Giugno","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,4,22]]},"reference":[{"key":"4129_CR1","volume-title":"Chemical graph theory: introduction and fundamentals","author":"D Bonchev","year":"1991","unstructured":"Bonchev D. Chemical graph theory: introduction and fundamentals, vol. 1. Boca Raton: CRC Press; 1991."},{"issue":"1","key":"4129_CR2","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1093\/nar\/gkg034","volume":"31","author":"Cv Mering","year":"2003","unstructured":"Mering Cv, Huynen M, Jaeggi D, Schmidt S, Bork P, Snel B. STRING: a database of predicted functional associations between proteins. Nucleic Acids Res. 2003;31(1):258\u201361.","journal-title":"Nucleic Acids Res"},{"issue":"10","key":"4129_CR3","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1186\/s12859-018-2298-8","volume":"19","author":"V Bonnici","year":"2018","unstructured":"Bonnici V, De Caro G, Constantino G, Liuni S, D\u2019Elia D, Bombieri N, Licciulli F, Giugno R. Arena-Idb: a platform to build human non-coding RNA interaction networks. BMC Bioinform. 2018;19(10):350.","journal-title":"BMC Bioinform"},{"issue":"21","key":"4129_CR4","doi-asserted-by":"publisher","first-page":"8685","DOI":"10.1073\/pnas.0701361104","volume":"104","author":"K-I Goh","year":"2007","unstructured":"Goh K-I, Cusick ME, Valle D, Childs B, Vidal M, Barab\u00e1si A-L. The human disease network. Proc Nat Acad Sci. 2007;104(21):8685\u201390.","journal-title":"Proc Nat Acad Sci"},{"key":"4129_CR5","doi-asserted-by":"crossref","unstructured":"Grochow JA, Kellis M. Network motif discovery using subgraph enumeration and symmetry-breaking. In: Annual international conference on research in computational molecular biology. Springer; 2007. p. 92\u2013106.","DOI":"10.1007\/978-3-540-71681-5_7"},{"key":"4129_CR6","doi-asserted-by":"crossref","unstructured":"Rinnone F, Micale G, Bonnici V, Bader GD, Shasha D, Ferro A, Pulvirenti A, Giugno R. NetMatchStar: an enhanced Cytoscape network querying app. F1000Research 2015;4","DOI":"10.12688\/f1000research.6656.1"},{"key":"4129_CR7","doi-asserted-by":"publisher","first-page":"304","DOI":"10.3389\/fonc.2020.00304","volume":"10","author":"M Sadeghi","year":"2020","unstructured":"Sadeghi M, Ordway B, Rafiei I, Borad P, Fang B, Koomen JL, Zhang C, Yoder S, Johnson J, Damaghi M. Integrative analysis of breast cancer cells reveals an epithelial-mesenchymal transition role in adaptation to acidic microenvironment. Front Oncol. 2020;10:304.","journal-title":"Front Oncol"},{"issue":"3","key":"4129_CR8","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1093\/bib\/bbu021","volume":"16","author":"NTL Tran","year":"2015","unstructured":"Tran NTL, Mohan S, Xu Z, Huang C-H. Current innovations and future challenges of network motif detection. Brief Bioinform. 2015;16(3):497\u2013525.","journal-title":"Brief Bioinform"},{"issue":"2","key":"4129_CR9","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1093\/bib\/bbr033","volume":"13","author":"E Wong","year":"2012","unstructured":"Wong E, Baur B, Quader S, Huang C-H. Biological network motif detection: principles and practice. Brief Bioinform. 2012;13(2):202\u201315.","journal-title":"Brief Bioinform"},{"issue":"1","key":"4129_CR10","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1038\/ng881","volume":"31","author":"SS Shen-Orr","year":"2002","unstructured":"Shen-Orr SS, Milo R, Mangan S, Alon U. Network motifs in the transcriptional regulation network of Escherichia coli. Nat Genet. 2002;31(1):64\u20138.","journal-title":"Nat Genet"},{"key":"4129_CR11","doi-asserted-by":"publisher","first-page":"400","DOI":"10.3389\/fchem.2019.00400","volume":"7","author":"JR Allison","year":"2019","unstructured":"Allison JR, Welsh ID. CherryPicker: an algorithm for the automated parameterisation of large biomolecules for molecular simulation. Front Chem. 2019;7:400.","journal-title":"Front Chem"},{"issue":"suppl\u20132","key":"4129_CR12","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1093\/nar\/gkh411","volume":"32","author":"BP Kelley","year":"2004","unstructured":"Kelley BP, Yuan B, Lewitter F, Sharan R, Stockwell BR, Ideker T. PathBLAST: a tool for alignment of protein interaction networks. Nucl Acids Res. 2004;32(suppl\u20132):83\u20138.","journal-title":"Nucl Acids Res"},{"issue":"1","key":"4129_CR13","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1089\/cmb.2006.0076","volume":"14","author":"Q Yang","year":"2007","unstructured":"Yang Q, Sze S-H. Path matching and graph matching in biological networks. J Comput Biol. 2007;14(1):56\u201367.","journal-title":"J Comput Biol"},{"issue":"1","key":"4129_CR14","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1038\/msb4100129","volume":"3","author":"R Sharan","year":"2007","unstructured":"Sharan R, Ulitsky I, Shamir R. Network-based prediction of protein function. Mol Syst Biol. 2007;3(1):88.","journal-title":"Mol Syst Biol"},{"issue":"6","key":"4129_CR15","doi-asserted-by":"publisher","first-page":"98750","DOI":"10.1371\/journal.pone.0098750","volume":"9","author":"G Micale","year":"2014","unstructured":"Micale G, Pulvirenti A, Giugno R, Ferro A. GASOLINE: a greedy and stochastic algorithm for optimal local multiple alignment of interaction networks. PLoS ONE. 2014;9(6):98750.","journal-title":"PLoS ONE"},{"issue":"13","key":"4129_CR16","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1093\/bioinformatics\/btr203","volume":"27","author":"G G\u00fclsoy","year":"2011","unstructured":"G\u00fclsoy G, Kahveci T. RINQ: reference-based indexing for network queries. Bioinformatics. 2011;27(13):149\u201358.","journal-title":"Bioinformatics"},{"issue":"7","key":"4129_CR17","doi-asserted-by":"publisher","first-page":"1004259","DOI":"10.1371\/journal.pcbi.1004259","volume":"11","author":"DS Himmelstein","year":"2015","unstructured":"Himmelstein DS, Baranzini SE. Heterogeneous network edge prediction: a data integration approach to prioritize disease-associated genes. PLoS Comput Biol. 2015;11(7):1004259.","journal-title":"PLoS Comput Biol"},{"key":"4129_CR18","doi-asserted-by":"publisher","first-page":"26726","DOI":"10.7554\/eLife.26726","volume":"6","author":"DS Himmelstein","year":"2017","unstructured":"Himmelstein DS, Lizee A, Hessler C, Brueggeman L, Chen SL, Hadley D, Green A, Khankhanian P, Baranzini SE. Systematic integration of biomedical knowledge prioritizes drugs for repurposing. Elife. 2017;6:26726.","journal-title":"Elife"},{"issue":"4","key":"4129_CR19","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1089\/cmb.2009.0144","volume":"18","author":"V Fionda","year":"2011","unstructured":"Fionda V, Palopoli L. Biological network querying techniques: analysis and comparison. J Comput Biol. 2011;18(4):595\u2013625.","journal-title":"J Comput Biol"},{"key":"4129_CR20","doi-asserted-by":"crossref","unstructured":"Cook SA. The complexity of theorem-proving procedures. In: Proceedings of the Third Annual ACM Symposium on Theory of Computing, 1971. p. 151\u20138.","DOI":"10.1145\/800157.805047"},{"key":"4129_CR21","unstructured":"Cordella LP, Foggia P, Sansone C, Vento M. An improved algorithm for matching large graphs. In: 3rd IAPR-TC15 Workshop on Graph-based Representations in Pattern Recognition, 2001. p. 149\u201359."},{"key":"4129_CR22","doi-asserted-by":"crossref","unstructured":"Carletti V, Foggia P, Saggese A, Vento M. Introducing VF3: a new algorithm for subgraph isomorphism. In: International Workshop on Graph-Based Representations in Pattern Recognition. Springer; 2017. p. 128\u201339.","DOI":"10.1007\/978-3-319-58961-9_12"},{"issue":"1","key":"4129_CR23","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1109\/TCBB.2016.2515595","volume":"14","author":"V Bonnici","year":"2016","unstructured":"Bonnici V, Giugno R. On the variable ordering in subgraph isomorphism algorithms. IEEE\/ACM Trans Comput Biol Bioinf. 2016;14(1):193\u2013203.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinf"},{"key":"4129_CR24","unstructured":"He H, Singh AK. Graphs-at-a-time: query language and access methods for graph databases. In: Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, 2008. p. 405\u201318."},{"key":"4129_CR25","unstructured":"Han W-S, Lee J, Lee J-H. Turboiso: towards ultrafast and robust subgraph isomorphism search in large graph databases. In: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, 2013. p. 337\u2013348."},{"key":"4129_CR26","doi-asserted-by":"crossref","unstructured":"Bi F, Chang L, Lin X, Qin L, Zhang W. Efficient subgraph matching by postponing cartesian products. In: Proceedings of the 2016 International Conference on Management of Data, 2016. p. 1199\u2013214.","DOI":"10.1145\/2882903.2915236"},{"key":"4129_CR27","doi-asserted-by":"crossref","unstructured":"Giugno R, Shasha D. Graphgrep: A fast and universal method for querying graphs. In: Object Recognition Supported by User Interaction for Service Robots, vol. 2. IEEE; 2002. pp. 112\u20135.","DOI":"10.1109\/ICPR.2002.1048250"},{"key":"4129_CR28","doi-asserted-by":"crossref","unstructured":"Bonnici V, Ferro A, Giugno R, Pulvirenti A, Shasha D. Enhancing graph database indexing by suffix tree structure. In: IAPR International Conference on Pattern Recognition in Bioinformatics. Springer; 2010. p. 195\u2013203.","DOI":"10.1007\/978-3-642-16001-1_17"},{"key":"4129_CR29","doi-asserted-by":"crossref","unstructured":"Giugno R, Bonnici V, Bombieri N, Pulvirenti A, Ferro A, Shasha D. Grapes: A software for parallel searching on biological graphs targeting multi-core architectures. PloS ONE. 2013;8(10).","DOI":"10.1371\/journal.pone.0076911"},{"issue":"1","key":"4129_CR30","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1186\/1471-2105-11-96","volume":"11","author":"R Di Natale","year":"2010","unstructured":"Di Natale R, Ferro A, Giugno R, Mongiov\u00ec M, Pulvirenti A, Shasha D. Sing: Subgraph search in non-homogeneous graphs. BMC Bioinform. 2010;11(1):96.","journal-title":"BMC Bioinform"},{"key":"4129_CR31","doi-asserted-by":"crossref","unstructured":"Klein K, Kriege N, Mutzel P. CT-index: Fingerprint-based graph indexing combining cycles and trees. In: 2011 IEEE 27th International Conference on Data Engineering. IEEE; 2011. p. 1115\u201326.","DOI":"10.1109\/ICDE.2011.5767909"},{"key":"4129_CR32","doi-asserted-by":"crossref","unstructured":"Williams DW, Huan J, Wang W. Graph database indexing using structured graph decomposition. In: 2007 IEEE 23rd International Conference on Data Engineering. IEEE. 2007. p. 976\u2013985.","DOI":"10.1109\/ICDE.2007.368956"},{"key":"4129_CR33","doi-asserted-by":"crossref","unstructured":"Zou L, Chen L, Yu JX, Lu Y. A novel spectral coding in a large graph database. In: Proceedings of the 11th International Conference on Extending Database Technology: Advances in Database Technology, 2008. p. 181\u201392.","DOI":"10.1145\/1353343.1353369"},{"issue":"1","key":"4129_CR34","doi-asserted-by":"publisher","first-page":"364","DOI":"10.14778\/1453856.1453899","volume":"1","author":"H Shang","year":"2008","unstructured":"Shang H, Zhang Y, Lin X, Yu JX. Taming verification hardness: an efficient algorithm for testing subgraph isomorphism. Proc VLDB Endow. 2008;1(1):364\u201375.","journal-title":"Proc VLDB Endow"},{"key":"4129_CR35","doi-asserted-by":"crossref","unstructured":"Zhang S, Hu M, Yang J. Treepi: A novel graph indexing method. In: 2007 IEEE 23rd International Conference on Data Engineering. IEEE; 2007. p. 966\u201375.","DOI":"10.1109\/ICDE.2007.368955"},{"key":"4129_CR36","first-page":"938","volume":"7","author":"P Zhao","year":"2007","unstructured":"Zhao P, Yu JX, Philip SY. Graph indexing: Tree+ Delta>= Graph. VLDB. 2007;7:938\u201349.","journal-title":"VLDB"},{"key":"4129_CR37","unstructured":"Xie Y, Yu PS. CP-index: on the efficient indexing of large graphs. In: Proceedings of the 20th ACM International Conference on Information and Knowledge Management, 2011. p. 1795\u2013804."},{"key":"4129_CR38","unstructured":"Yan X, Yu PS, Han J. Graph indexing: a frequent structure-based approach. In: Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data, 2004. p. 335\u201346."},{"key":"4129_CR39","unstructured":"Cheng J, Ke Y, Ng W, Lu A. Fg-index: towards verification-free query processing on graph databases. In: Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data, 2007. p. 857\u201372."},{"issue":"2","key":"4129_CR40","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/s00778-012-0284-8","volume":"22","author":"D Yuan","year":"2013","unstructured":"Yuan D, Mitra P. Lindex: a lattice-based index for graph databases. VLDB J. 2013;22(2):229\u201352.","journal-title":"VLDB J"},{"issue":"6","key":"4129_CR41","doi-asserted-by":"publisher","first-page":"1112","DOI":"10.1016\/j.jcss.2016.04.002","volume":"82","author":"D Pal","year":"2016","unstructured":"Pal D, Rao P, Slavov V, Katib A. Fast processing of graph queries on a large database of small and medium-sized data graphs. J Comput Syst Sci. 2016;82(6):1112\u201343.","journal-title":"J Comput Syst Sci"},{"key":"4129_CR42","doi-asserted-by":"crossref","unstructured":"Katsarou F, Ntarmos N, Triantafillou P. Hybrid algorithms for subgraph pattern queries in graph databases. In: 2017 IEEE International Conference on Big Data (Big Data). IEEE. 2017. p. 656\u2013665.","DOI":"10.1109\/BigData.2017.8257981"},{"key":"4129_CR43","doi-asserted-by":"crossref","unstructured":"Sun S, Luo Q. Scaling Up Subgraph Query Processing with Efficient Subgraph Matching. In: 2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE; 2019. p. 220\u201331.","DOI":"10.1109\/ICDE.2019.00028"},{"key":"4129_CR44","unstructured":"Wang J, Ntarmos N, Triantafillou P. Indexing query graphs to speed up graph query processing, 2016."},{"key":"4129_CR45","unstructured":"Wang J, Ntarmos N, Triantafillou P. GraphCache: a caching system for graph queries, 2017."},{"key":"4129_CR46","doi-asserted-by":"crossref","unstructured":"Gouda K, Hassaan M. Compressed feature-based filtering and verification approach for subgraph search. In: Proceedings of the 16th International Conference on Extending Database Technology, 2013. p. 287\u201398.","DOI":"10.1145\/2452376.2452411"},{"key":"4129_CR47","unstructured":"Luaces D, Viqueira JR, Pena TF, Cotos JM. Leveraging Bitmap Indexing for Subgraph Searching. In: EDBT, 2019. p. 49\u201360."},{"issue":"12","key":"4129_CR48","doi-asserted-by":"publisher","first-page":"1566","DOI":"10.14778\/2824032.2824054","volume":"8","author":"F Katsarou","year":"2015","unstructured":"Katsarou F, Ntarmos N, Triantafillou P. Performance and scalability of indexed subgraph query processing methods. Proc VLDB Endow. 2015;8(12):1566\u201377.","journal-title":"Proc VLDB Endow"},{"key":"4129_CR49","volume-title":"Daylight theory manual","author":"CA James","year":"1995","unstructured":"James CA, Weininger D, Delany J. Daylight theory manual. Irvine: Daylight Chemical Information Systems. Inc.; 1995."},{"key":"4129_CR50","unstructured":"S\u00e6ther AA. Path-based Graph Indexing for Keyword Search on RDF data-Discovering Concepts Through Community Detection. Master\u2019s thesis, NTNU, 2017."},{"issue":"2","key":"4129_CR51","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1016\/0890-5401(92)90017-A","volume":"98","author":"JR Burch","year":"1992","unstructured":"Burch JR, Clarke EM, McMillan KL, Dill DL, Hwang L-J. Symbolic model checking: 1020 states and beyond. Inf Comput. 1992;98(2):142\u201370.","journal-title":"Inf Comput"},{"key":"4129_CR52","unstructured":"Veeraraghavan M, Trivedi KS. An improved algorithm for the symbolic reliability analysis of networks. In: Proceedings Ninth Symposium on Reliable Distributed Systems. IEEE; 1990. p. 34\u201343."},{"key":"4129_CR53","doi-asserted-by":"crossref","unstructured":"Ciardo G, Zhao Y, Jin X. Ten years of saturation: A Petri net perspective. In: Transactions on Petri Nets and Other Models of Concurrency V. New York: Springer. 2012. p. 51\u201395","DOI":"10.1007\/978-3-642-29072-5_3"},{"key":"4129_CR54","doi-asserted-by":"crossref","unstructured":"Miner A, Parker D. Symbolic representations and analysis of large probabilistic systems. In: Validation of Stochastic Systems. Springer; 2004. p. 296\u2013338.","DOI":"10.1007\/978-3-540-24611-4_9"},{"issue":"9","key":"4129_CR55","doi-asserted-by":"publisher","first-page":"993","DOI":"10.1109\/12.537122","volume":"45","author":"B Bollig","year":"1996","unstructured":"Bollig B, Wegener I. Improving the variable ordering of OBDDs is NP-complete. IEEE Trans Comput. 1996;45(9):993\u20131002.","journal-title":"IEEE Trans Comput"},{"key":"4129_CR56","doi-asserted-by":"crossref","unstructured":"Brace KS, Rudell RL, Bryant RE: Efficient implementation of a BDD package. In: 27th ACM\/IEEE Design Automation Conference, IEEE; 1990. p. 40\u20135.","DOI":"10.1145\/123186.123222"},{"key":"4129_CR57","unstructured":"Somenzi, F.: CUDD: CU decision diagram package release 2.3. 0. University of Colorado at Boulder. 1998."},{"key":"4129_CR58","first-page":"1","volume-title":"Tools and algorithms for the construction and analysis of systems","author":"Y Thierry-Mieg","year":"2009","unstructured":"Thierry-Mieg Y, Poitrenaud D, Hamez A, Kordon F. Hierarchical set decision diagrams and regular models. In: Kowalewski S, Philippou A, editors. Tools and algorithms for the construction and analysis of systems. Berlin: Springer; 2009. p. 1\u201315."},{"key":"4129_CR59","doi-asserted-by":"crossref","unstructured":"Babar J, Miner A. Meddly: Multi-terminal and edge-valued decision diagram library. In: 2010 Seventh International Conference on the Quantitative Evaluation of Systems, IEEE; 2010. p. 195\u2013196.","DOI":"10.1109\/QEST.2010.34"},{"issue":"S7","key":"4129_CR60","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1186\/1471-2105-14-S7-S13","volume":"14","author":"V Bonnici","year":"2013","unstructured":"Bonnici V, Giugno R, Pulvirenti A, Shasha D, Ferro A. A subgraph isomorphism algorithm and its application to biochemical data. BMC Bioinform. 2013;14(S7):13.","journal-title":"BMC Bioinform"},{"key":"4129_CR61","doi-asserted-by":"crossref","unstructured":"Carletti V, Foggia P, Vento M. Performance comparison of five exact graph matching algorithms on biological databases. In: International Conference on Image Analysis and Processing, 2013;pp. 409\u2013417. Springer","DOI":"10.1007\/978-3-642-41190-8_44"},{"key":"4129_CR62","unstructured":"cancer institute, N.: National cancer institute. http:\/\/www.nci.nih.gov\/. Accessed 2013 March 10"},{"issue":"6","key":"4129_CR63","doi-asserted-by":"publisher","first-page":"899","DOI":"10.1107\/S0907444902003451","volume":"58","author":"HM Berman","year":"2002","unstructured":"Berman HM, Battistuz T, Bhat TN, Bluhm WF, Bourne PE, Burkhardt K, Feng Z, Gilliland GL, Iype L, Jain S, et al. The protein data bank. Acta Crystallogr D Biol Crystallogr. 2002;58(6):899\u2013907.","journal-title":"Acta Crystallogr D Biol Crystallogr"},{"key":"4129_CR64","doi-asserted-by":"crossref","unstructured":"Huehne R, Suehnel J. The Jena Library of Biological Macromolecules-JenaLib. Nature Precedings. 2009;1.","DOI":"10.1038\/npre.2009.3114.1"},{"issue":"11","key":"4129_CR65","doi-asserted-by":"publisher","first-page":"1573","DOI":"10.1093\/bioinformatics\/btr163","volume":"27","author":"C Vehlow","year":"2011","unstructured":"Vehlow C, Stehr H, Winkelmann M, Duarte JM, Petzold L, Dinse J, Lappe M. CMView: interactive contact map visualization and analysis. Bioinformatics. 2011;27(11):1573\u20134.","journal-title":"Bioinformatics"},{"issue":"suppl-1","key":"4129_CR66","first-page":"561","volume":"39","author":"D Szklarczyk","year":"2010","unstructured":"Szklarczyk D, Franceschini A, Kuhn M, Simonovic M, Roth A, Minguez P, Doerks T, Stark M, Muller J, Bork P, et al. The STRING database in 2011: functional interaction networks of proteins, globally integrated and scored. Nucleic Acids Res. 2010;39(suppl-1):561\u20138.","journal-title":"Nucleic Acids Res"},{"issue":"5439","key":"4129_CR67","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"A.-L. Barab\u00e1si","year":"1999","unstructured":"Barab\u00e1si A.-L., Albert R. Emergence of scaling in random networks. Science. 1999;286(5439):509\u201312.","journal-title":"Science"},{"key":"4129_CR68","unstructured":"Leskovec J, Kleinberg J, Faloutsos C. Graphs over time: densification laws, shrinking diameters and possible explanations. In: Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, 2005. p. 177\u201387."},{"issue":"1","key":"4129_CR69","first-page":"21","volume":"11","author":"A Aparo","year":"2019","unstructured":"Aparo A, Bonnici V, Micale G, Ferro A, Shasha D, Pulvirenti A, Giugno R. Fast subgraph matching strategies based on pattern-only heuristics. Interdiscip Sci: Comput Life Sci. 2019;11(1):21\u201332.","journal-title":"Interdisciplinary Sciences: Computational Life Sciences"},{"key":"4129_CR70","unstructured":"Merkel D. Docker: Lightweight Linux Containers for Consistent Development and Deployment. Linux J. 2014;2014(239)."}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-021-04129-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s12859-021-04129-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-021-04129-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,28]],"date-time":"2024-08-28T22:46:57Z","timestamp":1724885217000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/s12859-021-04129-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,22]]},"references-count":70,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["4129"],"URL":"https:\/\/doi.org\/10.1186\/s12859-021-04129-0","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-48943\/v1","asserted-by":"object"}]},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,22]]},"assertion":[{"value":"24 July 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 April 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 April 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to publish"}},{"value":"The authors declare that they have no competing interests.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"209"}}