{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,24]],"date-time":"2026-09-24T14:48:39Z","timestamp":1790261319931,"version":"4.1.0"},"reference-count":27,"publisher":"Oxford University Press (OUP)","issue":"21","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010,11,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Motivation: Comparing 3D structures of homologous RNA molecules yields information about sequence and structural variability. To compare large RNA 3D structures, accurate automatic comparison tools are needed. In this article, we introduce a new algorithm and web server to align large homologous RNA structures nucleotide by nucleotide using local superpositions that accommodate the flexibility of RNA molecules. Local alignments are merged to form a global alignment by employing a maximum clique algorithm on a specially defined graph that we call the \u2018local alignment\u2019 graph.<\/jats:p><jats:p>Results: The algorithm is implemented in a program suite and web server called \u2018R3D Align\u2019. The R3D Align alignment of homologous 3D structures of 5S, 16S and 23S rRNA was compared to a high-quality hand alignment. A full comparison of the 16S alignment with the other state-of-the-art methods is also provided. The R3D Align program suite includes new diagnostic tools for the structural evaluation of RNA alignments. The R3D Align alignments were compared to those produced by other programs and were found to be the most accurate, in comparison with a high quality hand-crafted alignment and in conjunction with a series of other diagnostics presented. The number of aligned base pairs as well as measures of geometric similarity are used to evaluate the accuracy of the alignments.<\/jats:p><jats:p>Availability: R3D Align is freely available through a web server http:\/\/rna.bgsu.edu\/R3DAlign. The MATLAB source code of the program suite is also freely available for download at that location.<\/jats:p><jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p><jats:p>Contact: \u00a0r-rahrig@onu.edu<\/jats:p>","DOI":"10.1093\/bioinformatics\/btq506","type":"journal-article","created":{"date-parts":[[2010,10,19]],"date-time":"2010-10-19T04:15:50Z","timestamp":1287461750000},"page":"2689-2697","source":"Crossref","is-referenced-by-count":51,"title":["R3D Align: global pairwise alignment of RNA 3D structures using local superpositions"],"prefix":"10.1093","volume":"26","author":[{"given":"Ryan R.","family":"Rahrig","sequence":"first","affiliation":[{"name":"1 Department of Mathematics and Statistics at Ohio Northern University, Ada, OH 45810 and 2Department of Chemistry, Bowling Green State University, Bowling Green, OH 43403, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Neocles B.","family":"Leontis","sequence":"additional","affiliation":[{"name":"1 Department of Mathematics and Statistics at Ohio Northern University, Ada, OH 45810 and 2Department of Chemistry, Bowling Green State University, Bowling Green, OH 43403, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Craig L.","family":"Zirbel","sequence":"additional","affiliation":[{"name":"1 Department of Mathematics and Statistics at Ohio Northern University, Ada, OH 45810 and 2Department of Chemistry, Bowling Green State University, Bowling Green, OH 43403, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2010,10,19]]},"reference":[{"key":"2023012507543818200_B1","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/BF01415983","article-title":"A branch and bound algorithm for the maximum clique problem","volume":"34","author":"Babel","year":"1990","journal-title":"Math. Methods Oper. Res."},{"key":"2023012507543818200_B2","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."},{"key":"2023012507543818200_B3","first-page":"87","article-title":"Some heuristics for graph coloring","volume-title":"Graph Colourings","author":"Biggs","year":"1990"},{"key":"2023012507543818200_B4","doi-asserted-by":"crossref","first-page":"1623","DOI":"10.1261\/rna.1601409","article-title":"The RNA structure alignment ontology","volume":"15","author":"Brown","year":"2009","journal-title":"RNA"},{"key":"2023012507543818200_B5","doi-asserted-by":"crossref","first-page":"i112","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":"2023012507543818200_B6","doi-asserted-by":"crossref","first-page":"W19","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":"Nucleic Acids Res."},{"key":"2023012507543818200_B7","doi-asserted-by":"crossref","first-page":"W394","DOI":"10.1093\/nar\/gkl244","article-title":"NAST: a multiple sequence alignment server for comparative analysis of 16S rRNA genes","volume":"34","author":"DeSantis","year":"2006","journal-title":"Nucleic Acids Res."},{"issue":"Suppl. 2","key":"2023012507543818200_B8","doi-asserted-by":"crossref","first-page":"ii47","DOI":"10.1093\/bioinformatics\/bti1108","article-title":"ARTS: alignment of RNA tertiary structures","volume":"21","author":"Dror","year":"2005","journal-title":"Bioinformatics"},{"key":"2023012507543818200_B9","doi-asserted-by":"crossref","first-page":"4755","DOI":"10.1093\/nar\/gkg682","article-title":"RNA structure comparison, motif search and discovery using a reduced representation of RNA conformational space","volume":"31","author":"Duarte","year":"2003","journal-title":"Nucleic Acids Res."},{"key":"2023012507543818200_B10","doi-asserted-by":"crossref","first-page":"W659","DOI":"10.1093\/nar\/gkm334","article-title":"DIAL: a web server for the pairwise alignment of two RNA three-dimensional structures using nucleotide, dihedral angle and base-pairing similarities","volume":"35","author":"Ferre","year":"2007","journal-title":"Nucleic Acids Res."},{"key":"2023012507543818200_B11","volume-title":"Computers and Intractability : a Guide to the Theory of NP- Completeness.","author":"Garey","year":"1979"},{"key":"2023012507543818200_B12","doi-asserted-by":"crossref","first-page":"6249","DOI":"10.1093\/nar\/gkg835","article-title":"Automated identification of RNA conformational motifs: theory and application to the HM LSU 23S rRNA","volume":"31","author":"Hershkovitz","year":"2003","journal-title":"Nucleic Acids Res."},{"key":"2023012507543818200_B13","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/j.jmb.2004.03.076","article-title":"The roles of ribosomal proteins in the structure assembly, and evolution of the large ribosomal subunit","volume":"340","author":"Klein","year":"2004","journal-title":"J. Mol. Biol."},{"key":"2023012507543818200_B14","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1126\/science.1101489","article-title":"Basis for structural diversity in homologous RNAs","volume":"306","author":"Krasilnikov","year":"2004","journal-title":"Science"},{"key":"2023012507543818200_B15","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1038\/nature01386","article-title":"Crystal structure of the specificity domain of ribonuclease P","volume":"421","author":"Krasilnikov","year":"2003","journal-title":"Nature"},{"key":"2023012507543818200_B16","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":"2023012507543818200_B17","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1021\/ma60045a006","article-title":"Configurational statistics of polynucleotide chains. A single virtual bond treatment","volume":"8","author":"Olson","year":"1975","journal-title":"Macromolecules"},{"key":"2023012507543818200_B18","doi-asserted-by":"crossref","first-page":"2606","DOI":"10.1110\/ps.0215902","article-title":"MAMMOTH (matching molecular models obtained from theory): an automated method for model comparison","volume":"11","author":"Ortiz","year":"2002","journal-title":"Protein Sci."},{"key":"2023012507543818200_B19","doi-asserted-by":"crossref","first-page":"1875","DOI":"10.1261\/rna.1700409","article-title":"New metrics for comparing and assessing discrepancies between RNA 3D structures and models","volume":"15","author":"Parisien","year":"2009","journal-title":"RNA"},{"key":"2023012507543818200_B20","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/s00285-007-0110-x","article-title":"FR3D: finding local and composite recurrent structural motifs in RNA 3D structures","volume":"56","author":"Sarver","year":"2008","journal-title":"J. Math. Biol."},{"key":"2023012507543818200_B21","doi-asserted-by":"crossref","first-page":"827","DOI":"10.1126\/science.1117230","article-title":"Structures of the bacterial ribosome at 3.5 A resolution","volume":"310","author":"Schuwirth","year":"2005","journal-title":"Science"},{"key":"2023012507543818200_B22","doi-asserted-by":"crossref","first-page":"1935","DOI":"10.1126\/science.1131127","article-title":"Structure of the 70S ribosome complexed with mRNA and tRNA","volume":"313","author":"Selmer","year":"2006","journal-title":"Science"},{"key":"2023012507543818200_B23","doi-asserted-by":"crossref","first-page":"2294","DOI":"10.1093\/nar\/gkp011","article-title":"Frequency and isostericity of RNA base pairs","volume":"37","author":"Stombaugh","year":"2009","journal-title":"Nucleic Acids Res."},{"key":"2023012507543818200_B24","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1287\/opre.1040.0189","article-title":"Optimal protein structure alignment using maximum cliques","volume":"53","author":"Strickland","year":"2005","journal-title":"Oper. Res."},{"key":"2023012507543818200_B25","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1038\/35030006","article-title":"Structure of the 30S ribosomal subunit","volume":"407","author":"Wimberly","year":"2000","journal-title":"Nature"},{"key":"2023012507543818200_B26","doi-asserted-by":"crossref","first-page":"3450","DOI":"10.1093\/nar\/gkg529","article-title":"Tools for the automatic identification and classification of RNA base pairs","volume":"31","author":"Yang","year":"2003","journal-title":"Nucleic Acids Res."},{"key":"2023012507543818200_B27","doi-asserted-by":"crossref","first-page":"4898","DOI":"10.1093\/nar\/gkp468","article-title":"Classification and energetic of the base-phosphate interactions in RNA","volume":"37","author":"Zirbel","year":"2009","journal-title":"Nucleic Acids Res."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/21\/2689\/48853173\/bioinformatics_26_21_2689.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/21\/2689\/48853173\/bioinformatics_26_21_2689.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,31]],"date-time":"2024-03-31T13:46:18Z","timestamp":1711892778000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/26\/21\/2689\/213314"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,10,19]]},"references-count":27,"journal-issue":{"issue":"21","published-print":{"date-parts":[[2010,11,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btq506","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2010,11,1]]},"published":{"date-parts":[[2010,10,19]]}}}