{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T22:20:28Z","timestamp":1778797228886,"version":"3.51.4"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"S4","license":[{"start":{"date-parts":[[2006,12,1]],"date-time":"2006-12-01T00:00:00Z","timestamp":1164931200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/2.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2006,12]]},"DOI":"10.1186\/1471-2105-7-s4-s6","type":"journal-article","created":{"date-parts":[[2006,12,12]],"date-time":"2006-12-12T14:59:21Z","timestamp":1165935561000},"source":"Crossref","is-referenced-by-count":17,"title":["Maximum common subgraph: some upper bound and lower bound results"],"prefix":"10.1186","volume":"7","author":[{"given":"Xiuzhen","family":"Huang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jing","family":"Lai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Steven F","family":"Jennings","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2006,12,12]]},"reference":[{"key":"1329_CR1","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1023\/A:1021271615909","volume":"16","author":"JW Raymond","year":"2002","unstructured":"Raymond JW, Willett P: Maximum common subgraph isomorphism algorithms for the matching of chemical structures. Journal of Computer-aided Molecular Design 2002, 16: 521\u2013533.","journal-title":"Journal of Computer-aided Molecular Design"},{"issue":"11","key":"1329_CR2","doi-asserted-by":"publisher","first-page":"1168","DOI":"10.1109\/34.42855","volume":"11","author":"R Horaud","year":"1989","unstructured":"Horaud R, Skordas T: Stereo correspondence through feature grouping and maximal cliques. IEEE Trans Pattern Anal Mach Intell 1989, 11(11):1168\u20131180.","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"key":"1329_CR3","volume-title":"No. IDIAP-RR 00\u201315, Dalle Molle Institute for Perceptual Artificial Intelligence, Martigny, Valais, Switzerland","author":"K Shearer","year":"2000","unstructured":"Shearer K, Bunke H, Venkatesh S: Video indexing and similarity retrieval by largest common subgraph detection using decision trees. No. IDIAP-RR 00\u201315, Dalle Molle Institute for Perceptual Artificial Intelligence, Martigny, Valais, Switzerland 2000."},{"key":"1329_CR4","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1126\/science.1853201","volume":"253","author":"J Bowie","year":"1991","unstructured":"Bowie J, Luthy R, Eisenberg D: A method to identify protein sequences that fold into a known three-dimensional structure. Science 1991, 253: 164\u2013170.","journal-title":"Science"},{"key":"1329_CR5","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1016\/0959-440X(95)80082-4","volume":"5","author":"SH Bryant","year":"1995","unstructured":"Bryant SH, Altschul SF: Statistics of sequence-structure threading. Curr Opin Struct Biol 1995, 5: 236\u2013244.","journal-title":"Curr Opin Struct Biol"},{"issue":"3","key":"1329_CR6","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1089\/cmb.1998.5.597","volume":"5","author":"Y Xu","year":"1998","unstructured":"Xu Y, Xu D, Uberbacher EC: An efficient computational method for globally optimal threading. Journal of Computational Biology 1998, 5(3):597\u2013614.","journal-title":"Journal of Computational Biology"},{"key":"1329_CR7","volume-title":"Computational Methods in Molecular Biology, Salzberg, Searls","author":"RH Lathrop","year":"1998","unstructured":"Lathrop RH, Rogers RG Jr, Bienkowska J, Bryant BMK, Buturovic LJ, Gaitatzes C, Nambudripad R, White JV, Smith TF: Analysis and algorithms for protein sequencestructure alignment. In Computational Methods in Molecular Biology, Salzberg, Searls. Edited by: Kasif. Elsevier; 1998."},{"issue":"1","key":"1329_CR8","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1142\/S0219720003000186","volume":"1","author":"J Xu","year":"2003","unstructured":"Xu J, Li M, Kim D, Xu Y: RAPTOR: optimal protein threading by linear programming. J Bioinform Comput Biol 2003, 1(1):95\u2013117.","journal-title":"J Bioinform Comput Biol"},{"issue":"11 supp","key":"1329_CR9","doi-asserted-by":"publisher","first-page":"954","DOI":"10.1038\/80729","volume":"7","author":"JA Doudna","year":"2000","unstructured":"Doudna JA: Structural genomics of RNA. Nature Structural Biology 2000, 7(11 supp):954\u2013956.","journal-title":"Nature Structural Biology"},{"key":"1329_CR10","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/S0092-8674(02)00727-4","volume":"109","author":"SR Eddy","year":"2002","unstructured":"Eddy SR: Computational genomics of non-coding RNA genes. Cell 2002, 109: 137\u2013140.","journal-title":"Cell"},{"key":"1329_CR11","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1186\/1471-2105-2-8","volume":"2","author":"E Rivas","year":"2001","unstructured":"Rivas E, Eddy SR: Noncoding RNA gene detection using comparative sequence analysis. BMC Bioinformatics 2001, 2: 8.","journal-title":"BMC Bioinformatics"},{"key":"1329_CR12","doi-asserted-by":"publisher","first-page":"955","DOI":"10.1093\/nar\/25.5.0955","volume":"25","author":"TM Lowe","year":"1997","unstructured":"Lowe TM, Eddy SR: tRNAscan-SE: A Program for improved detection of transfer RNA genes in genomic sequence. Nucleic Acids Research 1997, 25: 955\u2013964.","journal-title":"Nucleic Acids Research"},{"key":"1329_CR13","first-page":"376","volume":"3692","author":"Y Song","year":"2005","unstructured":"Song Y, Liu C, Huang X, Malmberg R, Xu Y, Cai L: Efficient parameterized algorithm for biopolymer structure-sequence alignment. Proceedings of 5th Workshop on Algorithms in BioInformatics (WABI 2005), Lecture Notes in Bioinformatics 2005, 3692: 376\u2013388.","journal-title":"Proceedings of 5th Workshop on Algorithms in BioInformatics (WABI 2005), Lecture Notes in Bioinformatics"},{"key":"1329_CR14","volume-title":"a Guide to the Theory of NP-Completeness","author":"MR Gary","year":"1979","unstructured":"Gary MR, Johnson DS, Computers and Intractability: a Guide to the Theory of NP-Completeness. WH. Freeman and Co; 1979."},{"key":"1329_CR15","first-page":"377","volume-title":"Proc 9th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science 577","author":"V Kann","year":"1992","unstructured":"Kann V: On the approximability of the maximum common subgraph problem. In Proc 9th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science 577. Springer-Verlag; 1992:377\u2013388."},{"key":"1329_CR16","first-page":"691","volume":"67","author":"J Cheetham","year":"2003","unstructured":"Cheetham J, Dehne F, Rau-Chaplin A, Stege U, Taillon PJ: Solving large FPT problems on coarse-grained parallel machines. JCSS 2003, 67: 691.","journal-title":"JCSS"},{"key":"1329_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R Downey","year":"1999","unstructured":"Downey R, Fellows M: Parameterized Complexity. Springer; 1999."},{"key":"1329_CR18","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0890-5401(03)00057-9","volume":"185","author":"JK Lanctot","year":"2003","unstructured":"Lanctot JK, Li M, Ma B, Wang S, Zhang L: Distinguishing string selection problems. Inf Comput 2003, 185: 41.","journal-title":"Inf Comput"},{"key":"1329_CR19","volume-title":"Complexity and Approximation, Combinatorial Optimization Problems and Their Approximability Properties","author":"G Ausiello","year":"1999","unstructured":"Ausiello G, Crescenzi P, Gambosi G, Kann V, Marchetti-Spaccamela A, Protasi M: Complexity and Approximation, Combinatorial Optimization Problems and Their Approximability Properties. New York: Springer-Verlag; 1999."},{"key":"1329_CR20","first-page":"740","volume":"2380","author":"X Deng","year":"2002","unstructured":"Deng X, Li G, Li Z, Ma B, Wang L: A PTAS for distinguishing (sub)string selection. LNCS 2002, 2380: 740.","journal-title":"LNCS"},{"key":"1329_CR21","doi-asserted-by":"publisher","first-page":"1073","DOI":"10.1137\/S0097539701397825","volume":"32","author":"X Deng","year":"2003","unstructured":"Deng X, Li G, Li Z, Ma B, Wang L: Genetic design of drugs without side-effects. SIAM Journal on Computing 2003, 32: 1073.","journal-title":"SIAM Journal on Computing"},{"key":"1329_CR22","doi-asserted-by":"publisher","first-page":"1122","DOI":"10.1137\/S009753979223842X","volume":"24","author":"T Jiang","year":"1995","unstructured":"Jiang T, Li M: On the Approximation of shortest common Supersequences and longest Common subsequences. SIAM J Comput 1995, 24: 1122.","journal-title":"SIAM J Comput"},{"key":"1329_CR23","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1145\/506147.506150","volume":"49","author":"M Li","year":"2002","unstructured":"Li M, Ma B, Wang L: On the closest string and substring problems. Journal of the ACM 2002, 49: 157.","journal-title":"Journal of the ACM"},{"key":"1329_CR24","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1006\/jagm.2001.1186","volume":"41","author":"J Chen","year":"2001","unstructured":"Chen J, Kanj I, Jia W: Vertex cover: further observations and further improvements. Journal of Algorithms 2001, 41: 280\u2013301.","journal-title":"Journal of Algorithms"},{"key":"1329_CR25","volume-title":"JCSS","author":"C Papadimitriou","year":"1999","unstructured":"Papadimitriou C, Yannakakis M: On the complexity of database queries. JCSS 1999., 58:"},{"key":"1329_CR26","first-page":"49","volume":"11","author":"HL Bodlaender","year":"1995","unstructured":"Bodlaender HL, Downey RG, Fellows MR, Hallett MT, Wareham HT: Parameterized complexity analysis in computational biology. Comput Appl Biosci 1995, 11: 49\u201357.","journal-title":"Comput Appl Biosci"},{"key":"1329_CR27","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/0304-3975(94)00251-D","volume":"147","author":"H Bodlaender","year":"1995","unstructured":"Bodlaender H, Downey R, Fellows M, Wareham M: The parameterized complexity of sequence alignment and consensus. Theoretical Computer Science 1995, 147: 31.","journal-title":"Theoretical Computer Science"},{"key":"1329_CR28","first-page":"262","volume":"2285","author":"M Fellows","year":"2002","unstructured":"Fellows M, Gramm J, Niedermeier R: Parameterized intractability of motif search problems. LNCS 2002, 2285: 262.","journal-title":"LNCS"},{"key":"1329_CR29","volume-title":"An Integrated Complexity Analysis of Problems for Computational Biology","author":"M Hallett","year":"1996","unstructured":"Hallett M: An Integrated Complexity Analysis of Problems for Computational Biology. Ph.D. Thesis, University of Victoria; 1996."},{"key":"1329_CR30","first-page":"161","volume":"53","author":"C Papadimitriou","year":"1996","unstructured":"Papadimitriou C, Yannakakis M: On limited nondeterminism and the complexity of VC dimension. JCSS 1996, 53: 161.","journal-title":"JCSS"},{"key":"1329_CR31","first-page":"757","volume":"67","author":"K Pietrzak","year":"2003","unstructured":"Pietrzak K: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. JCSS 2003, 67: 757.","journal-title":"JCSS"},{"key":"1329_CR32","first-page":"150","volume-title":"Proc of the 19th Annual IEEE Conference on Computational Complexity","author":"J Chen","year":"2004","unstructured":"Chen J, Chor B, Fellows M, Huang X, Juedes D, Kanj I, Xia G: Tight lower bounds for parameterized NP-hard problems. Proc of the 19th Annual IEEE Conference on Computational Complexity 2004, 150\u2013160."},{"key":"1329_CR33","first-page":"212","volume-title":"Proc of the 36th ACM Symposium on Theory of Computing","author":"J Chen","year":"2004","unstructured":"Chen J, Huang X, Kanj I, Xia G: Linear FPT reductions and computational lower bounds. Proc of the 36th ACM Symposium on Theory of Computing 2004, 212\u2013221."},{"key":"1329_CR34","volume-title":"Parameterized Complexity and Polynomial-time Approximation Schemes","author":"X Huang","year":"2004","unstructured":"Huang X: Parameterized Complexity and Polynomial-time Approximation Schemes. Ph.D. Dissertation, Texas A&M University; 2004."},{"key":"1329_CR35","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1006\/jcss.1997.1490","volume":"54","author":"L Cai","year":"1997","unstructured":"Cai L, Chen J: On Fixed-Parameter Tractability and Approximability of NP Optimization Problems. J Comput Syst Sci 1997, 54: 465\u2013474.","journal-title":"J Comput Syst Sci"},{"key":"1329_CR36","first-page":"975","volume":"3595","author":"J Chen","year":"2005","unstructured":"Chen J, Huang X, Kanj I, Xia G: W-hardness linear FPT-reductions: structural properties and further applications. Proceedings of the Eleventh International Computing and Combinatorics Conference (COCOON 2005), Lecture Notes in Computer Science 2005, 3595: 975\u2013984.","journal-title":"Proceedings of the Eleventh International Computing and Combinatorics Conference (COCOON 2005), Lecture Notes in Computer Science"},{"key":"1329_CR37","volume-title":"Electr Notes Theor Comput Sci","author":"R Downey","year":"2003","unstructured":"Downey R, Estivill-Castro V, Fellows M, Prieto E, Rosamond F: Cutting up is hard to do: the parameterized complexity of k-Cut and related Problems. Electr Notes Theor Comput Sci 2003., 78:"},{"key":"1329_CR38","first-page":"438","volume-title":"WABI2004","author":"S-H Sze","year":"2004","unstructured":"Sze S-H, Lu S, Chen J: Integrating sample-driven and pattern-driven approaches in motif finding. WABI2004 2004, 438\u2013449."},{"key":"1329_CR39","volume-title":"Lectures notes of Special Topics in Computational Biology, Fall","author":"S-H Sze","year":"2002","unstructured":"Sze S-H: Lectures notes of Special Topics in Computational Biology, Fall. 2002."},{"key":"1329_CR40","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2001","unstructured":"Cormen TH, Leiserson CE, Rivest RL, Stein C: Introduction to Algorithms. 2nd edition. MIT Press; 2001.","edition":"2"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-7-S4-S6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/1471-2105-7-S4-S6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-7-S4-S6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,1,23]],"date-time":"2019-01-23T02:56:44Z","timestamp":1548212204000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-7-S4-S6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,12]]},"references-count":40,"journal-issue":{"issue":"S4","published-print":{"date-parts":[[2006,12]]}},"alternative-id":["1329"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-7-s4-s6","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,12]]},"article-number":"S6"}}