{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,2,1]],"date-time":"2024-02-01T18:41:29Z","timestamp":1706812889847},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,1,5]],"date-time":"2016-01-05T00:00:00Z","timestamp":1451952000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2016,1,5]],"date-time":"2016-01-05T00:00:00Z","timestamp":1451952000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"FONDECYT","award":["1141172"],"award-info":[{"award-number":["1141172"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"abstract":"<jats:title>Abstract<\/jats:title><jats:sec>\n                <jats:title>Background<\/jats:title>\n                <jats:p>The total number of known three-dimensional protein structures is rapidly increasing. Consequently, the need for fast structural search against complete databases without a significant loss of accuracy is increasingly demanding. Recently, TopSearch, an ultra-fast method for finding rigid structural relationships between a query structure and the complete Protein Data Bank (PDB), at the multi-chain level, has been released. However, comparable accurate flexible structural aligners to perform efficient whole database searches of multi-domain proteins are not yet available. The availability of such a tool is critical for a sustainable boosting of biological discovery.<\/jats:p>\n              <\/jats:sec><jats:sec>\n                <jats:title>Results<\/jats:title>\n                <jats:p>Here we report on the development of a new method for the fast and flexible comparison of protein structure chains. The method relies on the calculation of 2D matrices containing a description of the three-dimensional arrangement of secondary structure elements (angles and distances). The comparison involves the matching of an ensemble of substructures through a nested-two-steps dynamic programming algorithm. The unique features of this new approach are the integration and trade-off balancing of the following: 1) speed, 2) accuracy and 3) global and semiglobal flexible structure alignment by integration of local substructure matching. The comparison, and matching with competitive accuracy, of one medium sized (250-aa) query structure against the complete PDB database (216,322 protein chains) takes about 8\u00a0min using an average desktop computer. The method is at least 2\u20133 orders of magnitude faster than other tested tools with similar accuracy. We validate the performance of the method for fold and superfamily assignment in a large benchmark set of protein structures. We finally provide a series of examples to illustrate the usefulness of this method and its application in biological discovery.<\/jats:p>\n              <\/jats:sec><jats:sec>\n                <jats:title>Conclusions<\/jats:title>\n                <jats:p>The method is able to detect partial structure matching, rigid body shifts, conformational changes and tolerates substantial structural variation arising from insertions, deletions and sequence divergence, as well as structural convergence of unrelated proteins.<\/jats:p>\n              <\/jats:sec>","DOI":"10.1186\/s12859-015-0866-8","type":"journal-article","created":{"date-parts":[[2016,1,5]],"date-time":"2016-01-05T12:12:01Z","timestamp":1451995921000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Efficient and automated large-scale detection of structural relationships in proteins with a flexible aligner"],"prefix":"10.1186","volume":"17","author":[{"given":"Fernando I.","family":"Guti\u00e9rrez","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Felipe","family":"Rodriguez-Valenzuela","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ignacio L.","family":"Ibarra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Damien P.","family":"Devos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Francisco","family":"Melo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,1,5]]},"reference":[{"issue":"4","key":"866_CR1","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/S0962-8924(98)01237-9","volume":"8","author":"HP Erickson","year":"1998","unstructured":"Erickson HP. Atomic structures of tubulin and FtsZ. Trends Cell Biol. 1998;8(4):133\u20137.","journal-title":"Trends Cell Biol"},{"issue":"6851","key":"866_CR2","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1038\/35092500","volume":"413","author":"F van den Ent","year":"2001","unstructured":"van den Ent F, Amos LA, Lo\u00c8we J. Prokaryotic origin of the actin cytoskeleton. Nature. 2001;413(6851):39\u201344.","journal-title":"Nature"},{"issue":"3","key":"866_CR3","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1016\/j.sbi.2009.04.003","volume":"19","author":"H Hasegawa","year":"2009","unstructured":"Hasegawa H, Holm L. Advances and pitfalls of protein structural alignment. Curr Opin Struct Biol. 2009;19(3):341\u20138.","journal-title":"Curr Opin Struct Biol"},{"issue":"11","key":"866_CR4","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1016\/S0968-0004(00)89105-7","volume":"20","author":"L Holm","year":"1995","unstructured":"Holm L, Sander C. Dali: a network tool for protein structure comparison. Trends Biochem Sci. 1995;20(11):478\u201380.","journal-title":"Trends Biochem Sci"},{"key":"866_CR5","first-page":"59","volume":"4","author":"M Gerstein","year":"1996","unstructured":"Gerstein M, Levitt M. Using iterative dynamic programming to obtain accurate pairwise and multiple alignments of protein structures. Proc Int Conf Intell Syst Mol Biol. 1996;4:59\u201367.","journal-title":"Proc Int Conf Intell Syst Mol Biol"},{"issue":"4","key":"866_CR6","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1016\/j.str.2012.01.024","volume":"20","author":"MJ Sippl","year":"2012","unstructured":"Sippl MJ, Wiederstein M. Detection of spatial correlations in protein structures and molecular complexes. Structure (London, England : 1993). 2012;20(4):718\u201328.","journal-title":"Structure (London, England : 1993)"},{"issue":"11","key":"866_CR7","doi-asserted-by":"publisher","first-page":"2606","DOI":"10.1110\/ps.0215902","volume":"11","author":"AR Ortiz","year":"2002","unstructured":"Ortiz AR, Strauss CEM, Olmea O. MAMMOTH (matching molecular models obtained from theory): an automated method for model comparison. Protein Sci. 2002;11(11):2606\u201321.","journal-title":"Protein Sci"},{"issue":"9","key":"866_CR8","doi-asserted-by":"publisher","first-page":"739","DOI":"10.1093\/protein\/11.9.739","volume":"11","author":"IN Shindyalov","year":"1998","unstructured":"Shindyalov IN, Bourne PE. Protein structure alignment by incremental combinatorial extension (CE) of the optimal path. Protein Eng. 1998;11(9):739\u201347.","journal-title":"Protein Eng"},{"issue":"3","key":"866_CR9","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1002\/prot.20921","volume":"64","author":"AS Konagurthu","year":"2006","unstructured":"Konagurthu AS, Whisstock JC, Stuckey PJ, Lesk AM. MUSTANG: a multiple structural alignment algorithm. Proteins: Struct, Funct, Bioinf. 2006;64(3):559\u201374.","journal-title":"Proteins: Struct, Funct, Bioinf"},{"issue":"suppl 2","key":"866_CR10","doi-asserted-by":"publisher","first-page":"ii246","DOI":"10.1093\/bioinformatics\/btg1086","volume":"19","author":"Y Ye","year":"2003","unstructured":"Ye Y, Godzik A. Flexible structure alignment by chaining aligned fragment pairs allowing twists. Bioinformatics. 2003;19 suppl 2:ii246\u201355.","journal-title":"Bioinformatics"},{"issue":"7","key":"866_CR11","doi-asserted-by":"publisher","first-page":"2302","DOI":"10.1093\/nar\/gki524","volume":"33","author":"Y Zhang","year":"2005","unstructured":"Zhang Y, Skolnick J. TM-align: a protein structure alignment algorithm based on the TM-score. Nucleic Acids Res. 2005;33(7):2302\u20139.","journal-title":"Nucleic Acids Res"},{"issue":"3","key":"866_CR12","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1016\/S0959-440X(96)80058-3","volume":"6","author":"J-F Gibrat","year":"1996","unstructured":"Gibrat J-F, Madej T, Bryant SH. Surprising similarities in structure comparison. Curr Opin Struct Biol. 1996;6(3):377\u201385.","journal-title":"Curr Opin Struct Biol"},{"key":"866_CR13","doi-asserted-by":"crossref","unstructured":"Orengo CA, Taylor WR. SSAP: sequential structure alignment program for protein structure comparison. Computer methods for macromolecular sequence analysis. 1996.","DOI":"10.1016\/S0076-6879(96)66038-8"},{"issue":"8","key":"866_CR14","doi-asserted-by":"publisher","first-page":"1374","DOI":"10.1110\/ps.035469.108","volume":"17","author":"A Guerler","year":"2008","unstructured":"Guerler A, Knapp EW. Novel protein folds and their nonsequential structural analogs. Protein Sci. 2008;17(8):1374\u201382.","journal-title":"Protein Sci"},{"key":"866_CR15","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1186\/1471-2105-10-153","volume":"10","author":"A Stivala","year":"2009","unstructured":"Stivala A, Wirth A, Stuckey PJ. Tableau-based protein substructure search using quadratic programming. BMC bioinformatics. 2009;10:153.","journal-title":"BMC bioinformatics"},{"key":"866_CR16","doi-asserted-by":"publisher","DOI":"10.1142\/9789812778789","volume-title":"Computational structural biology: Methods and applications","author":"T Schwede","year":"2008","unstructured":"Schwede T, Peitsch MC. Computational structural biology: Methods and applications. 1st ed. Singapore: World Scientific; 2008.","edition":"1"},{"issue":"7","key":"866_CR17","doi-asserted-by":"publisher","first-page":"1063","DOI":"10.1016\/j.str.2014.05.005","volume":"22","author":"M Wiederstein","year":"2014","unstructured":"Wiederstein M, Gruber M, Frank K, Melo F, Sippl MJ. Structure-based characterization of multiprotein complexes. Structure. 2014;22(7):1063\u201370.","journal-title":"Structure"},{"issue":"5906","key":"866_CR18","doi-asserted-by":"publisher","first-page":"1369","DOI":"10.1126\/science.1165886","volume":"322","author":"SG Brohawn","year":"2008","unstructured":"Brohawn SG, Leksa NC, Spear ED, Rajashankar KR, Schwartz TU. Structural evidence for common ancestry of the nuclear pore complex and vesicle coats. Science. 2008;322(5906):1369\u201373.","journal-title":"Science"},{"issue":"3","key":"866_CR19","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/0263-7855(95)00037-7","volume":"13","author":"AM Lesk","year":"1995","unstructured":"Lesk AM. Systematic representation of protein folding patterns. J Mol Graph. 1995;13(3):159\u201364.","journal-title":"J Mol Graph"},{"issue":"5","key":"866_CR20","doi-asserted-by":"publisher","first-page":"645","DOI":"10.1093\/bioinformatics\/btm641","volume":"24","author":"AS Konagurthu","year":"2008","unstructured":"Konagurthu AS, Stuckey PJ, Lesk AM. Structural search and retrieval using a tableau representation of protein folding patterns. Bioinformatics (Oxford, England). 2008;24(5):645\u201351.","journal-title":"Bioinformatics (Oxford, England)"},{"key":"866_CR21","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/978-1-62703-065-6_4","volume":"932","author":"AS Konagurthu","year":"2013","unstructured":"Konagurthu AS, Lesk AM. Structure description and identification using the tableau representation of protein folding patterns. Methods in molecular biology (Clifton, NJ). 2013;932:51\u20139.","journal-title":"Methods in molecular biology (Clifton, NJ)"},{"issue":"4","key":"866_CR22","doi-asserted-by":"publisher","first-page":"869","DOI":"10.1002\/prot.21241","volume":"66","author":"AP Kamat","year":"2007","unstructured":"Kamat AP, Lesk AM. Contact patterns between helices and strands of sheet define protein folding patterns. Proteins. 2007;66(4):869\u201376.","journal-title":"Proteins"},{"issue":"4","key":"866_CR23","first-page":"536","volume":"247","author":"AG Murzin","year":"1995","unstructured":"Murzin AG, Brenner SE, Hubbard T, Chothia C. SCOP: a structural classification of proteins database for the investigation of sequences and structures. J Mol Biol. 1995;247(4):536\u201340.","journal-title":"J Mol Biol"},{"issue":"1","key":"866_CR24","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/s10930-006-0011-7","volume":"25","author":"K Chen","year":"2006","unstructured":"Chen K, Ruan J, Kurgan L. Prediction of three dimensional structure of calmodulin. Protein J. 2006;25(1):57\u201370.","journal-title":"Protein J"},{"issue":"2","key":"866_CR25","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1002\/prot.10100","volume":"48","author":"M Shatsky","year":"2002","unstructured":"Shatsky M, Nussinov R, Wolfson HJ. Flexible protein alignment and hinge detection. Proteins: Struct, Funct, Bioinf. 2002;48(2):242\u201356.","journal-title":"Proteins: Struct, Funct, Bioinf"},{"issue":"12","key":"866_CR26","doi-asserted-by":"publisher","first-page":"e380","DOI":"10.1371\/journal.pbio.0020380","volume":"2","author":"D Devos","year":"2004","unstructured":"Devos D, Dokudovskaya S, Alber F, Williams R, Chait BT, Sali A, et al. Components of coated vesicles and nuclear pore complexes share a common molecular architecture. PLoS Biol. 2004;2(12):e380.","journal-title":"PLoS Biol"},{"issue":"6","key":"866_CR27","doi-asserted-by":"publisher","first-page":"963","DOI":"10.1083\/jcb.201102042","volume":"193","author":"MC Field","year":"2011","unstructured":"Field MC, Sali A, Rout MP. Evolution: On a bender--BARs, ESCRTs, COPs, and finally getting your coat. J Cell Biol. 2011;193(6):963\u201372.","journal-title":"J Cell Biol"},{"issue":"4","key":"866_CR28","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1002\/prot.340230412","volume":"23","author":"D Frishman","year":"1995","unstructured":"Frishman D, Argos P. Knowledge\u2010based protein secondary structure assignment. Proteins: Struct, Funct, Bioinf. 1995;23(4):566\u201379.","journal-title":"Proteins: Struct, Funct, Bioinf"},{"issue":"11","key":"866_CR29","doi-asserted-by":"publisher","first-page":"2469","DOI":"10.1002\/pro.5560071126","volume":"7","author":"K Mizuguchi","year":"1998","unstructured":"Mizuguchi K, Deane CM, Blundell TL, Overington JP. HOMSTRAD: a database of protein structure alignments for homologous families. Protein Sci. 1998;7(11):2469\u201371.","journal-title":"Protein Sci"},{"issue":"1","key":"866_CR30","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1093\/bioinformatics\/bts600","volume":"29","author":"AW Slater","year":"2013","unstructured":"Slater AW, Castellanos JI, Sippl MJ, Melo F. Towards the development of standardized methods for comparison, ranking and evaluation of structure alignments. Bioinformatics (Oxford, England). 2013;29(1):47\u201353.","journal-title":"Bioinformatics (Oxford, England)"},{"issue":"Database issue","key":"866_CR31","doi-asserted-by":"publisher","first-page":"D304","DOI":"10.1093\/nar\/gkt1240","volume":"42","author":"NK Fox","year":"2014","unstructured":"Fox NK, Brenner SE, Chandonia JM. SCOPe: Structural Classification of Proteins--extended, integrating SCOP and ASTRAL data and classification of new structures. Nucleic Acids Res. 2014;42(Database issue):D304\u2013309.","journal-title":"Nucleic Acids Res"},{"issue":"12","key":"866_CR32","doi-asserted-by":"publisher","first-page":"2577","DOI":"10.1002\/bip.360221211","volume":"22","author":"W Kabsch","year":"1983","unstructured":"Kabsch W, Sander C. Dictionary of protein secondary structure: pattern recognition of hydrogen-bonded and geometrical features. Biopolymers. 1983;22(12):2577\u2013637.","journal-title":"Biopolymers"},{"issue":"8","key":"866_CR33","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1093\/protein\/13.8.535","volume":"13","author":"J Jung","year":"2000","unstructured":"Jung J, Lee B. Protein structure alignment using environmental profiles. Protein Eng. 2000;13(8):535\u201343.","journal-title":"Protein Eng"},{"issue":"1","key":"866_CR34","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1002\/prot.20517","volume":"61","author":"M Carpentier","year":"2005","unstructured":"Carpentier M, Brouillet S, Pothier J. YAKUSA: a fast structural database scanning method. Proteins. 2005;61(1):137\u201351.","journal-title":"Proteins"},{"issue":"4","key":"866_CR35","doi-asserted-by":"publisher","first-page":"1173","DOI":"10.1016\/j.jmb.2004.12.032","volume":"346","author":"R Kolodny","year":"2005","unstructured":"Kolodny R, Koehl P, Levitt M. Comprehensive evaluation of protein structure alignment methods: scoring by geometric measures. J Mol Biol. 2005;346(4):1173\u201388.","journal-title":"J Mol Biol"},{"key":"866_CR36","doi-asserted-by":"crossref","unstructured":"Wall ME, Rechtsteiner A, Rocha LM. Singular value decomposition and principal component analysis. In: A practical approach to microarray data analysis. Springer. 2003: 91\u2013109.","DOI":"10.1007\/0-306-47815-3_5"},{"key":"866_CR37","unstructured":"Sung W-K. Algorithms in bioinformatics: A practical introduction: CRC Press; 2009. Broken Sound Parkway, NW Suite 300, Boca Raton, FL, 33487. USA."},{"issue":"1","key":"866_CR38","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","volume":"147","author":"TF Smith","year":"1981","unstructured":"Smith TF, Waterman MS. Identification of common molecular subsequences. J Mol Biol. 1981;147(1):195\u20137.","journal-title":"J Mol Biol"},{"issue":"6","key":"866_CR39","doi-asserted-by":"publisher","first-page":"872","DOI":"10.1093\/bioinformatics\/btn040","volume":"24","author":"MJ Sippl","year":"2008","unstructured":"Sippl MJ. On distance and similarity in fold space. Bioinformatics (Oxford, England). 2008;24(6):872\u20133.","journal-title":"Bioinformatics (Oxford, England)"},{"issue":"5","key":"866_CR40","doi-asserted-by":"publisher","first-page":"827","DOI":"10.1107\/S0567739478001680","volume":"34","author":"W Kabsch","year":"1978","unstructured":"Kabsch W. A discussion of the solution for the best rotation to relate two sets of vectors. Acta Crystallogr A. 1978;34(5):827\u20138.","journal-title":"Acta Crystallogr A"},{"issue":"2","key":"866_CR41","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1107\/S0108767388010128","volume":"45","author":"SK Kearsley","year":"1989","unstructured":"Kearsley SK. On the orthogonal transformation used for structural comparisons. Acta Crystallogr A. 1989;45(2):208\u201310.","journal-title":"Acta Crystallogr A"},{"issue":"3","key":"866_CR42","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1007\/BF00344966","volume":"50","author":"H Wolda","year":"1981","unstructured":"Wolda H. Similarity indices, sample size and diversity. Oecologia. 1981;50(3):296\u2013302.","journal-title":"Oecologia"},{"key":"866_CR43","first-page":"1","volume":"31","author":"T Fawcett","year":"2004","unstructured":"Fawcett T. ROC graphs: Notes and practical considerations for researchers. Mach Learn. 2004;31:1\u201338.","journal-title":"Mach Learn"},{"key":"866_CR44","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1186\/1471-2105-9-265","volume":"9","author":"IA Vergara","year":"2008","unstructured":"Vergara IA, Norambuena T, Ferrada E, Slater AW, Melo F. StAR: a simple tool for the statistical comparison of ROC curves. BMC bioinformatics. 2008;9:265.","journal-title":"BMC bioinformatics"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-015-0866-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s12859-015-0866-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-015-0866-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-015-0866-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,1]],"date-time":"2024-02-01T18:12:22Z","timestamp":1706811142000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/s12859-015-0866-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1,5]]},"references-count":44,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2016,12]]}},"alternative-id":["866"],"URL":"https:\/\/doi.org\/10.1186\/s12859-015-0866-8","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1,5]]},"assertion":[{"value":"19 August 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 December 2015","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 January 2016","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"20"}}