{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,26]],"date-time":"2026-06-26T22:29:53Z","timestamp":1782512993638,"version":"3.54.5"},"reference-count":47,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2009,4,21]],"date-time":"2009-04-21T00:00:00Z","timestamp":1240272000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>This work presents a generalized approach for the fast structural alignment of thousands of macromolecular structures. The method uses string representations of a macromolecular structure and a hash table that stores n-grams of a certain size for searching. To this end, macromolecular structure-to-string translators were implemented for protein and RNA structures. A query against the index is performed in two hierarchical steps to unite speed and precision. In the first step the query structure is translated into n-grams, and all target structures containing these n-grams are retrieved from the hash table. In the second step all corresponding n-grams of the query and each target structure are subsequently aligned, and after each alignment a score is calculated based on the matching n-grams of query and target. The extendable framework enables the user to query and structurally align thousands of protein and RNA structures on a commodity machine and is available as open source from http:\/\/lajolla.sf.net.<\/jats:p>","DOI":"10.3390\/a2020692","type":"journal-article","created":{"date-parts":[[2009,4,21]],"date-time":"2009-04-21T09:24:37Z","timestamp":1240305877000},"page":"692-709","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":26,"title":["Fast Structural Alignment of Biomolecules Using a Hash Table, N-Grams and String Descriptors"],"prefix":"10.3390","volume":"2","author":[{"given":"Raphael Andr\u00e9","family":"Bauer","sequence":"first","affiliation":[{"name":"Charit\u00e9 Medical University, Structural Bioinformatics Group, Arnimallee 22, 14195 Berlin, Germany"},{"name":"Graduate School: Genomics and Systems Biology of Molecular Networks, Invalidenstrasse 43, 10115 Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kristian","family":"Rother","sequence":"additional","affiliation":[{"name":"International Institute of Molecular and Cell Biology in Warsaw, ul. Ks. Trojdena 4, 02-109 Warsaw, Poland"},{"name":"Laboratory of Bioinformatics, Institute of Molecular Biology and Biotechnology, Faculty of Biology, Adam Mickiewicz University, ul. Umultowska 89, 61-614 Poznan, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter","family":"Moor","sequence":"additional","affiliation":[{"name":"Charit\u00e9 Medical University, Structural Bioinformatics Group, Arnimallee 22, 14195 Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Knut","family":"Reinert","sequence":"additional","affiliation":[{"name":"Freie Universit\u00e4t Berlin, Algorithmische Bioinformatik, Institut f\u00fcr Informatik, Takustr. 9, 14195 Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Steinke","sequence":"additional","affiliation":[{"name":"Zuse Institute Berlin, Dept. Computer Science, Takustrasse 7, 14195 Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Janusz M.","family":"Bujnicki","sequence":"additional","affiliation":[{"name":"International Institute of Molecular and Cell Biology in Warsaw, ul. Ks. Trojdena 4, 02-109 Warsaw, Poland"},{"name":"Laboratory of Bioinformatics, Institute of Molecular Biology and Biotechnology, Faculty of Biology, Adam Mickiewicz University, ul. Umultowska 89, 61-614 Poznan, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert","family":"Preissner","sequence":"additional","affiliation":[{"name":"Charit\u00e9 Medical University, Structural Bioinformatics Group, Arnimallee 22, 14195 Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2009,4,21]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"662","DOI":"10.1038\/181662a0","article-title":"A three- dimensional model of the myoglobin molecule obtained by x-ray analysis","volume":"181","author":"Kendrew","year":"1958","journal-title":"Nature"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1038\/nature07330","article-title":"Crystal structure of opsin in its G-protein-interacting conformation","volume":"455","author":"Scheerer","year":"2008","journal-title":"Nature"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"D301","DOI":"10.1093\/nar\/gkl971","article-title":"The worldwide Protein Data Bank (ww-PDB): Ensuring a single, uniform archive of PDB data","volume":"35","author":"Berman","year":"2007","journal-title":"Nucl. Acid. Res."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1610","DOI":"10.1126\/science.319.5870.1610","article-title":"Structural biology. protein structure initiative: phase 3 or phase out","volume":"319","author":"Service","year":"2008","journal-title":"Science"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"3183","DOI":"10.1073\/pnas.0611678104","article-title":"Growth of novel protein structural data","volume":"104","author":"Levitt","year":"2007","journal-title":"Proc. Nat. Acad. Sci."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1002\/prot.20520","article-title":"How well are protein structures annotated in secondary databases?","volume":"60","author":"Rother","year":"2005","journal-title":"Proteins"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1093\/nar\/gkm993","article-title":"Data growth and its impact on the SCOP database: new developments","volume":"36","author":"Andreeva","year":"2008","journal-title":"Nucl.Acid.Res."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"14412","DOI":"10.1073\/pnas.0805857105","article-title":"NMR structures of two designed proteins with high sequence identity but different fold and function","volume":"105","author":"He","year":"2008","journal-title":"Proc.Nat.Acad.Sci."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1186\/1471-2105-5-197","article-title":"SCOPmap: automated assignment of protein structures to evolutionary superfamilies","volume":"5","author":"Cheek","year":"2004","journal-title":"BMC Bioinformatics"},{"key":"ref_10","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 Engeering"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1093\/bioinformatics\/btm622","article-title":"A note on difficult structure alignment problems","volume":"24","author":"Sippl","year":"2008","journal-title":"Bioinformatics"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/0022-2836(73)90388-4","article-title":"Comparison of super-secondary structures in proteins","volume":"76","author":"Rao","year":"1973","journal-title":"J. Mol. Biol."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"2302","DOI":"10.1093\/nar\/gki524","article-title":"TM-align: a protein structure alignment algorithm based on the TM-score","volume":"33","author":"Zhang","year":"2005","journal-title":"Nucl.Acid.Res."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1374","DOI":"10.1110\/ps.035469.108","article-title":"Novel protein folds and their nonsequential structural analogs","volume":"17","author":"Guerler","year":"2008","journal-title":"Protein Sci."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1865","DOI":"10.1110\/ps.04672604","article-title":"Structural alignment of proteins by a novel topofit method, as a superimposition of common volumes at a topomax point","volume":"13","author":"Ilyin","year":"2004","journal-title":"Protein Sci."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"2256","DOI":"10.1107\/S0907444904026460","article-title":"Secondary-structure matching (ssm), a new tool for fast protein structure alignment in three dimensions","volume":"60","author":"Krissinel","year":"2004","journal-title":"Acta Crystallogr-D-Biol Cryst."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1173","DOI":"10.1016\/j.jmb.2004.12.032","article-title":"Comprehensive evaluation of protein structure alignment methods: scoring by geometric measures","volume":"346","author":"Kolodny","year":"2005","journal-title":"J. Mol. Biol."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1002\/prot.10553","article-title":"Evaluation of protein fold comparison servers","volume":"54","author":"Novotny","year":"2004","journal-title":"Proteins"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/S0022-2836(63)80023-6","article-title":"Stereochemistry of polypeptide chain configurations","volume":"7","author":"Ramachandran","year":"1963","journal-title":"J. Mol. Biol."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"W545","DOI":"10.1093\/nar\/gkh467","article-title":"SA-Search: a web tool for protein structure mining based on a Structural Alphabet","volume":"32","author":"Guyon","year":"2004","journal-title":"Nucl.Acid.Sci."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"W20","DOI":"10.1093\/nar\/gkl273","article-title":"PAST: Fast structure-based searching in the PDB","volume":"34","author":"Buchner","year":"2006","journal-title":"Nucl. Acid. Sci."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"e219","DOI":"10.1093\/bioinformatics\/btl310","article-title":"Using an alignment of fragment strings for comparing protein structures","volume":"23","author":"Friedberg","year":"2007","journal-title":"Bioinformatics"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1186\/1471-2105-8-307","article-title":"Protein structural similarity search by Ramachandran codes","volume":"8","author":"Lo","year":"2007","journal-title":"BMC Bioinformatics"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1016\/j.jpdc.2007.07.008","article-title":"PSIST: A scalable approach to indexing protein structures using suffix trees","volume":"68","author":"Gao","year":"2008","journal-title":"J. Parallel Distributed Computation"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"839","DOI":"10.1002\/prot.21746","article-title":"Docking without docking: ISEARCH-prediction of interactions using known interfaces","volume":"69","author":"May","year":"2007","journal-title":"Proteins"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1093\/bib\/bbm026","article-title":"Informatics challenges in structured RNA","volume":"8","author":"Laederach","year":"2007","journal-title":"Brief Bioinformatics"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"D182","DOI":"10.1093\/nar\/gkh080","article-title":"SCOR: Structural Classification of RNA, version 2.0","volume":"32","author":"Tamura","year":"2004","journal-title":"Nucl. Acid. Res."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"2274","DOI":"10.1261\/rna.853208","article-title":"Analysis and classification of RNA tertiary structures","volume":"14","author":"Abraham","year":"2008","journal-title":"RNA"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1093\/nar\/gkn327","article-title":"SARSA: a web tool for structural alignment of RNA using a structural alphabet","volume":"36","author":"Chang","year":"2008","journal-title":"Nucl. Acid. Res."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1093\/bioinformatics\/btn288","article-title":"RNA structure alignment by a unit-vector approach","volume":"24","author":"Capriotti","year":"2008","journal-title":"Bioinformatics"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"942","DOI":"10.1016\/j.jmb.2007.06.058","article-title":"Evaluating and Learning from RNA Pseudotorsional Space: Quantitative Validation of a Reduced Representation for RNA Structure","volume":"372","author":"Wadley","year":"2007","journal-title":"J. Mol. Biol."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1261\/rna.657708","article-title":"RNA backbone: consensus all-angle conformers and modular string nomenclature (an RNA Ontology Consortium contribution)","volume":"14","author":"Richardson","year":"2008","journal-title":"RNA"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1038\/nature06684","article-title":"The MC-Fold and MC-Sym pipeline infers RNA structure from sequence data","volume":"452","author":"Parisien","year":"2008","journal-title":"Nature"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1261\/rna.2343206","article-title":"The RNA Ontology Consortium: an open invitation to the RNA community","volume":"12","author":"Leontis","year":"2006","journal-title":"RNA"},{"key":"ref_35","unstructured":"Gusfield, D. (1997). Cambridge University Press."},{"key":"ref_36","first-page":"183","article-title":"Suffix techniques as a rapid method for RNA substructure search","volume":"20","author":"Bauer","year":"2008","journal-title":"Genome Informatics"},{"key":"ref_37","unstructured":"Dietzfelbinger, M., Karlin, A.R., Mehlhorn, K., Meyer auf der Heide, F., Rohnert, H., and Tarjan, R.E. (1988). IEEE Symposium on Foundations of Computer Science."},{"key":"ref_38","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. (2003). McGraw-Hill Science \/ Engineering \/ Math, [2nd Edition]."},{"key":"ref_39","unstructured":"Burkhardt, S., Crauser, A., Ferragina, P., Lenhof, H.P., Rivals, E., and Vingron, M. q-gram based database searching using a suffix array (QUASAR). RECOMB \u201999: Proceedings of the third annual international conference on Computational molecular biology."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"922","DOI":"10.1107\/S0567739476001873","article-title":"A solution for the best rotation to relate two sets of vectors","volume":"32","author":"Kabsch","year":"1976","journal-title":"Acta Crystallogr. A"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"702","DOI":"10.1002\/prot.20264","article-title":"Scoring function for automated assessment of protein structure template quality","volume":"57","author":"Zhang","year":"2007","journal-title":"Proteins"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"920","DOI":"10.1002\/prot.21776","article-title":"Protein structure mining using a structural alphabet","volume":"71","author":"Tyagi","year":"2008","journal-title":"Proteins"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"D310","DOI":"10.1093\/nar\/gkn877","article-title":"The CATH classification revisited\u2013architectures reviewed and new ways to characterize structural divergence in superfamilies","volume":"37","author":"Cuff","year":"2009","journal-title":"Nucl. Acid. Res."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"1007","DOI":"10.1038\/nsmb.1498","article-title":"Toward a more complete view of tRNA biology","volume":"15","year":"2008","journal-title":"Nat. Struct. Mol. Biol."},{"key":"ref_45","doi-asserted-by":"crossref","unstructured":"Stombaugh, J., Zirbel, C.L., Westhof, E., and Leontis, N.B. (2009). Frequency and isostericity of RNA base pairs. Nucl. Acid. Res., in press.","DOI":"10.1093\/nar\/gkp011"},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1186\/1471-2105-9-531","article-title":"Fr-TM-align: A new protein structural alignment method based on fragment alignments and the TM-score","volume":"9","author":"Pandit","year":"2008","journal-title":"BMC Bioinformatics"},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"2096","DOI":"10.1093\/bioinformatics\/btn397","article-title":"BioJava: an open-source framework for bioinformatics","volume":"24","author":"Holland","year":"2008","journal-title":"Bioinformatics"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/2\/2\/692\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T22:10:16Z","timestamp":1760220616000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/2\/2\/692"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,4,21]]},"references-count":47,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2009,6]]}},"alternative-id":["a2020692"],"URL":"https:\/\/doi.org\/10.3390\/a2020692","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,4,21]]}}}