{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T01:15:34Z","timestamp":1769044534075,"version":"3.49.0"},"reference-count":28,"publisher":"Oxford University Press (OUP)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008,3,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Comparison and classification of folding patterns from a database of protein structures is crucial to understand the principles of protein architecture, evolution and function. Current search methods for proteins with similar folding patterns are slow and computationally intensive. The sharp growth in the number of known protein structures poses severe challenges for methods of structural comparison. There is a need for methods that can search the database of structures accurately and rapidly.<\/jats:p>\n               <jats:p>We provide several methods to search for similar folding patterns using a concise tableau representation of proteins that encodes the relative geometry of secondary structural elements. Our first approach allows the extraction of identical and very closely-related protein folding patterns in constant-time (per hit). Next, we address the hard computational problem of extraction of maximally-similar subtableaux, when comparing two tableaux. We solve the problem using Quadratic and Linear integer programming formulations and demonstrate their power to identify subtle structural similarities, especially when protein structures significantly diverge. Finally, we describe a rapid and accurate method for comparing a query structure against a database of protein domains, TableauSearch. TableauSearch is rapid enough to search the entire structural database in seconds on a standard desktop computer. Our analysis of TableauSearch on many queries shows that the method is very accurate in identifying similarities of folding patterns, even between distantly related proteins.<\/jats:p>\n               <jats:p>Availability: A web server implementing the TableauSearch is available from http:\/\/hollywood.bx.psu.edu\/TabSearch<\/jats:p>\n               <jats:p>Contact: \u00a0arun@bx.psu.edu, aml25@psu.edu<\/jats:p>\n               <jats:p>Supplementary information: Supplementary Data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btm641","type":"journal-article","created":{"date-parts":[[2008,1,6]],"date-time":"2008-01-06T01:14:04Z","timestamp":1199582044000},"page":"645-651","source":"Crossref","is-referenced-by-count":30,"title":["Structural search and retrieval using a tableau representation of protein folding patterns"],"prefix":"10.1093","volume":"24","author":[{"given":"Arun S.","family":"Konagurthu","sequence":"first","affiliation":[{"name":"1 Department of Biochemistry and Molecular Biology and The Huck Institute for Genomics, Proteomics and Bioinformatics, The Pennsylvania State University, University Park, PA 16802, USA, 2Department of Computer Science and Software Engineering and 3NICTA Victoria Laboratories, The University of Melbourne, Victoria 3010, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter J.","family":"Stuckey","sequence":"additional","affiliation":[{"name":"1 Department of Biochemistry and Molecular Biology and The Huck Institute for Genomics, Proteomics and Bioinformatics, The Pennsylvania State University, University Park, PA 16802, USA, 2Department of Computer Science and Software Engineering and 3NICTA Victoria Laboratories, The University of Melbourne, Victoria 3010, Australia"},{"name":"1 Department of Biochemistry and Molecular Biology and The Huck Institute for Genomics, Proteomics and Bioinformatics, The Pennsylvania State University, University Park, PA 16802, USA, 2Department of Computer Science and Software Engineering and 3NICTA Victoria Laboratories, The University of Melbourne, Victoria 3010, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arthur M.","family":"Lesk","sequence":"additional","affiliation":[{"name":"1 Department of Biochemistry and Molecular Biology and The Huck Institute for Genomics, Proteomics and Bioinformatics, The Pennsylvania State University, University Park, PA 16802, USA, 2Department of Computer Science and Software Engineering and 3NICTA Victoria Laboratories, The University of Melbourne, Victoria 3010, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2008,1,5]]},"reference":[{"key":"2023020210111783100_B1","doi-asserted-by":"crossref","first-page":"1267","DOI":"10.1080\/07391102.1988.10506469","article-title":"A simple qualitative representation of polypeptide chain folds: comparison of protein tertiary structures","volume":"5","author":"Abagyan","year":"1988","journal-title":"J. Biomol. Struct. Dyn"},{"key":"2023020210111783100_B2","doi-asserted-by":"crossref","first-page":"617","DOI":"10.1021\/ci00010a007","article-title":"Similarity searching in databases of three-dimensional molecules and macromolecules","volume":"32","author":"Artymiuk","year":"1992","journal-title":"J. Chem. Inf. Comput. Sci"},{"key":"2023020210111783100_B3","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1016\/0014-5793(92)80475-V","article-title":"Three-dimensional structural resemblance between leucine aminopeptidase and carboxypeptidase A revealed by graph-theoretical techniques","volume":"303","author":"Artymiuk","year":"1992","journal-title":"FEBS Lett"},{"key":"2023020210111783100_B4","volume-title":"Dynamic Programming.","author":"Bellman","year":"1957"},{"issue":"Pt 6 No 1","key":"2023020210111783100_B5","doi-asserted-by":"crossref","first-page":"899","DOI":"10.1107\/S0907444902003451","article-title":"The Protein Data Bank","volume":"58","author":"Berman","year":"2002","journal-title":"Acta Crystallogr. D Biol. Crystallogr"},{"issue":"Database issue","key":"2023020210111783100_B6","article-title":"The ASTRAL compendium in 2004","volume":"32","author":"Chandonia","year":"2004","journal-title":"Nucleic Acids Res"},{"key":"2023020210111783100_B7","doi-asserted-by":"crossref","first-page":"707","DOI":"10.1006\/jmbi.1993.1074","article-title":"Identification of tertiary structure resemblance in proteins using a maximal common subgraph isomorphism algorithm","volume":"229","author":"Grindley","year":"1993","journal-title":"J. Mol. Biol"},{"key":"2023020210111783100_B8","doi-asserted-by":"crossref","first-page":"1748","DOI":"10.1093\/bioinformatics\/btg240","article-title":"Recognizing the fold of a protein structure","volume":"19","author":"Harrison","year":"2003","journal-title":"Bioinformatics"},{"key":"2023020210111783100_B9","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1006\/jmbi.1993.1489","article-title":"Protein structure comparison by alignment of distance matrices","volume":"233","author":"Holm","year":"1993","journal-title":"J. Mol. Biol"},{"key":"2023020210111783100_B10","doi-asserted-by":"crossref","first-page":"2577","DOI":"10.1002\/bip.360221211","article-title":"Dictionary of protein secondary structure: pattern recognition of hydrogen-bonded and geometrical features","volume":"22","author":"Kabsch","year":"1983","journal-title":"Biopolymers"},{"key":"2023020210111783100_B11","doi-asserted-by":"crossref","first-page":"869","DOI":"10.1002\/prot.21241","article-title":"Contact patterns between helices and strands of sheet define protein folding patterns","volume":"66","author":"Kamat","year":"2007","journal-title":"Proteins: Struct. Funct. Bioinform"},{"key":"2023020210111783100_B12","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1089\/cmb.1996.3.289","article-title":"An algorithm for finding maximal common subtopologies in a set of protein structures","volume":"3","author":"Koch","year":"1996","journal-title":"J. Comput. Biol"},{"key":"2023020210111783100_B13","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1002\/prot.20921","article-title":"MUSTANG: a multiple structural alignment algorithm","volume":"64","author":"Konagurthu","year":"2006","journal-title":"Proteins: Struct. Funct. Bioinform"},{"key":"2023020210111783100_B14","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/0022-2836(80)90373-3","article-title":"How different amino acid sequences determine similar protein structures: the structure and evolutionary dynamics of the globins","volume":"136","author":"Lesk","year":"1980","journal-title":"J. Mol. Biol"},{"key":"2023020210111783100_B15","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/0263-7855(95)00037-7","article-title":"Systematic representation of protein folding patterns","volume":"13","author":"Lesk","year":"1995","journal-title":"J. Mol. Graphics"},{"key":"2023020210111783100_B16","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1093\/nar\/28.1.257","article-title":"SCOP: a structural classification of proteins database","volume":"28","author":"Lo Conte","year":"2000","journal-title":"Nucleic Acids Res"},{"key":"2023020210111783100_B17","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1002\/prot.340230309","article-title":"Threading a database of protein cores","volume":"23","author":"Madej","year":"1995","journal-title":"Proteins"},{"key":"2023020210111783100_B18","doi-asserted-by":"crossref","first-page":"D251","DOI":"10.1093\/nar\/gkh060","article-title":"TOPS: an enhanced database of protein structural topology","volume":"32","author":"Michalopoulos","year":"2004","journal-title":"Nucleic Acid Res"},{"key":"2023020210111783100_B19","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1093\/protein\/8.4.353","article-title":"Comparison of spatial arrangements of secondary structural elements in proteins","volume":"8","author":"Mizuguchi","year":"1995","journal-title":"Protein Eng"},{"key":"2023020210111783100_B20","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","article-title":"A general method applicable to the search for similarities in the amino acid sequence of two proteins","volume":"48","author":"Needleman","year":"1970","journal-title":"J. Mol. Biol"},{"key":"2023020210111783100_B21","doi-asserted-by":"crossref","first-page":"1093","DOI":"10.1016\/S0969-2126(97)00260-8","article-title":"CATH\u2013a hierarchic classification of protein domain structures","volume":"5","author":"Orengo","year":"1997","journal-title":"Structure"},{"key":"2023020210111783100_B22","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1016\/S0022-5193(05)80263-2","article-title":"A rapid method for protein structure alignment","volume":"147","author":"Orengo","year":"1990","journal-title":"J. Theor. Biol"},{"key":"2023020210111783100_B23","volume-title":"Combinatorial Optimization: Algorithms and Complexity.","author":"Papadimitriou","year":"1998"},{"key":"2023020210111783100_B24","article-title":"The MD5 message digest algorithm, RFC 1321. MIT and RSA Data Security, Inc","author":"Rivest","year":"1992"},{"key":"2023020210111783100_B25","doi-asserted-by":"crossref","first-page":"1548","DOI":"10.1126\/science.1144706","article-title":"A common fold mediates vertebrate defense and bacterial attack","volume":"317","author":"Rosado","year":"2007","journal-title":"Science"},{"key":"2023020210111783100_B26","doi-asserted-by":"crossref","DOI":"10.1007\/BF00124346","article-title":"Structure-based identification and clustering of protein families and super-families","volume":"8","author":"Rufino","year":"1994","journal-title":"J. Computer Aided Mol. Design"},{"key":"2023020210111783100_B27","doi-asserted-by":"crossref","first-page":"739","DOI":"10.1093\/protein\/11.9.739","article-title":"Protein structure alignment by incremental combinatorial extension (CE) of the optimal path","volume":"11","author":"Shindyalov","year":"1998","journal-title":"Protein Eng"},{"key":"2023020210111783100_B28","doi-asserted-by":"crossref","first-page":"1331","DOI":"10.1093\/bioinformatics\/btm121","article-title":"Searching for three-dimensional secondary structural patterns in proteins with ProSMoS","volume":"23","author":"Shi","year":"2007","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/24\/5\/645\/49052779\/bioinformatics_24_5_645.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/24\/5\/645\/49052779\/bioinformatics_24_5_645.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T11:47:48Z","timestamp":1675338468000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/24\/5\/645\/201270"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1,5]]},"references-count":28,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2008,3,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btm641","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2008,3,1]]},"published":{"date-parts":[[2008,1,5]]}}}