{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T11:43:39Z","timestamp":1753875819268,"version":"3.41.2"},"reference-count":34,"publisher":"Oxford University Press (OUP)","issue":"5","license":[{"start":{"date-parts":[[2023,5,11]],"date-time":"2023-05-11T00:00:00Z","timestamp":1683763200000},"content-version":"vor","delay-in-days":10,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100004239","name":"Poznan University of Technology","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004239","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,5,4]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>Tertiary structure alignment is one of the main challenges in the computer-aided comparative study of molecular structures. Its aim is to optimally overlay the 3D shapes of two or more molecules in space to find the correspondence between their nucleotides. Alignment is the starting point for most algorithms that assess structural similarity or find common substructures. Thus, it has applications in solving a variety of bioinformatics problems, e.g. in the search for structural patterns, structure clustering, identifying structural redundancy, and evaluating the prediction accuracy of 3D models. To date, several tools have been developed to align 3D structures of RNA. However, most of them are not applicable to arbitrarily large structures and do not allow users to parameterize the optimization algorithm.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>We present two customizable heuristics for flexible alignment of 3D RNA structures, geometric search (GEOS), and genetic algorithm (GENS). They work in sequence-dependent\/independent mode and find the suboptimal alignment of expected quality (below a predefined RMSD threshold). We compare their performance with those of state-of-the-art methods for aligning RNA structures. We show the results of quantitative and qualitative tests run for all of these algorithms on benchmark sets of RNA structures.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>Source codes for both heuristics are hosted at https:\/\/github.com\/RNApolis\/rnahugs.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btad315","type":"journal-article","created":{"date-parts":[[2023,5,11]],"date-time":"2023-05-11T14:52:03Z","timestamp":1683816723000},"source":"Crossref","is-referenced-by-count":5,"title":["High-quality, customizable heuristics for RNA 3D structure alignment"],"prefix":"10.1093","volume":"39","author":[{"given":"Michal","family":"Zurkowski","sequence":"first","affiliation":[{"name":"Institute of Computing Science, Poznan University of Technology , 60-965 Poznan, Poland"}]},{"given":"Maciej","family":"Antczak","sequence":"additional","affiliation":[{"name":"Institute of Computing Science, Poznan University of Technology , 60-965 Poznan, Poland"},{"name":"Department of Structural Bioinformatics, Institute of Bioorganic Chemistry, Polish Academy of Sciences , 61-704 Poznan, Poland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8724-7908","authenticated-orcid":false,"given":"Marta","family":"Szachniuk","sequence":"additional","affiliation":[{"name":"Institute of Computing Science, Poznan University of Technology , 60-965 Poznan, Poland"},{"name":"Department of Structural Bioinformatics, Institute of Bioorganic Chemistry, Polish Academy of Sciences , 61-704 Poznan, Poland"}]}],"member":"286","published-online":{"date-parts":[[2023,5,11]]},"reference":[{"key":"2023052007035854000_btad315-B1","doi-asserted-by":"crossref","first-page":"3668","DOI":"10.1093\/bioinformatics\/btac386","article-title":"RNAsolo: a repository of cleaned PDB-derived RNA 3D structures","volume":"38","author":"Adamczyk","year":"2022","journal-title":"Bioinformatics"},{"key":"2023052007035854000_btad315-B2","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1186\/s12859-016-1237-9","article-title":"Structural alignment of protein descriptors\u2014a combinatorial model","volume":"17","author":"Antczak","year":"2016","journal-title":"BMC Bioinformatics"},{"key":"2023052007035854000_btad315-B3","doi-asserted-by":"crossref","first-page":"692","DOI":"10.3390\/a2020692","article-title":"Fast structural alignment of biomolecules using a hash table, n-Grams and string descriptors","volume":"2","author":"Bauer","year":"2009","journal-title":"Algorithms"},{"key":"2023052007035854000_btad315-B4","doi-asserted-by":"crossref","first-page":"2356","DOI":"10.1093\/bioinformatics\/bti351","article-title":"RNA tertiary structure determination: NOE pathway construction by tabu search","volume":"21","author":"Blazewicz","year":"2005","journal-title":"Bioinformatics"},{"key":"2023052007035854000_btad315-B5","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0004-3702(89)90050-7","article-title":"Classifier systems and genetic algorithms","volume":"40","author":"Booker","year":"1989","journal-title":"Artif Intell"},{"key":"2023052007035854000_btad315-B6","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":"2023052007035854000_btad315-B7","doi-asserted-by":"crossref","first-page":"610","DOI":"10.1261\/rna.031054.111","article-title":"RNA-Puzzles: a CASP-like evaluation of RNA three-dimensional structure prediction","volume":"18","author":"Cruz","year":"2012","journal-title":"RNA"},{"key":"2023052007035854000_btad315-B8","doi-asserted-by":"crossref","first-page":"953","DOI":"10.1038\/nsb1101-953","article-title":"Identification of homology in protein structure classification","volume":"8","author":"Dietmann","year":"2001","journal-title":"Nat Struct Biol"},{"key":"2023052007035854000_btad315-B9","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":"2023052007035854000_btad315-B10","first-page":"e137","article-title":"STAR3D: a stack-based RNA 3D structural alignment tool","volume":"43","author":"Ge","year":"2015","journal-title":"Nucleic Acids Res"},{"key":"2023052007035854000_btad315-B11","doi-asserted-by":"crossref","first-page":"4459","DOI":"10.1093\/bioinformatics\/btz282","article-title":"RNA-align: quick and accurate alignment of RNA 3D structures based on size-independent TM-scoreRNA","volume":"35","author":"Gong","year":"2019","journal-title":"Bioinformatics"},{"key":"2023052007035854000_btad315-B12","doi-asserted-by":"crossref","first-page":"1858","DOI":"10.1093\/bioinformatics\/bts301","article-title":"Efficient RNA pairwise structure comparison by SETTER method","volume":"28","author":"Hoksza","year":"2012","journal-title":"Bioinformatics"},{"key":"2023052007035854000_btad315-B13","doi-asserted-by":"crossref","first-page":"774","DOI":"10.1016\/j.molcel.2010.11.026","article-title":"Structural insights into ligand recognition by a sensing domain of the cooperative glycine riboswitch","volume":"40","author":"Huang","year":"2010","journal-title":"Mol Cell"},{"key":"2023052007035854000_btad315-B14","doi-asserted-by":"crossref","first-page":"827","DOI":"10.1107\/S0567739478001680","article-title":"A discussion of the solution for the best rotation to relate two sets of vectors","volume":"34","author":"Kabsch","year":"1978","journal-title":"Acta Cryst A"},{"key":"2023052007035854000_btad315-B15","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/978-3-642-25740-7_13","volume-title":"RNA 3D Structure Analysis and Prediction","author":"Leontis","year":"2012"},{"key":"2023052007035854000_btad315-B16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/1748-7188-8-1","article-title":"The difficulty of protein structure alignment under the RMSD","volume":"8","author":"Li","year":"2013","journal-title":"Algorithms Mol Biol"},{"key":"2023052007035854000_btad315-B17","doi-asserted-by":"crossref","first-page":"8566","DOI":"10.1002\/anie.201302995","article-title":"Structural basis of DNA quadruplex-duplex junction formation","volume":"52","author":"Lim","year":"2013","journal-title":"Angew Chem Int Ed Engl"},{"key":"2023052007035854000_btad315-B18","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":"2023052007035854000_btad315-B19","doi-asserted-by":"crossref","first-page":"5108","DOI":"10.1093\/nar\/gkg680","article-title":"3DNA: a software package for the analysis, rebuilding and visualization of three-dimensional nucleic acid structures","volume":"31","author":"Lu","year":"2003","journal-title":"Nucleic Acids Res"},{"key":"2023052007035854000_btad315-B20","doi-asserted-by":"crossref","first-page":"5978","DOI":"10.1093\/nar\/gkt318","article-title":"RNAlyzer\u2014novel approach for quality analysis of RNA structural models","volume":"41","author":"Lukasiak","year":"2013","journal-title":"Nucleic Acids Res"},{"key":"2023052007035854000_btad315-B21","doi-asserted-by":"crossref","first-page":"W502","DOI":"10.1093\/nar\/gkv557","article-title":"RNAssess\u2014a webserver for quality assessment of RNA 3D structures","volume":"43","author":"Lukasiak","year":"2015","journal-title":"Nucleic Acids Res"},{"key":"2023052007035854000_btad315-B22","first-page":"576","article-title":"RNA-Puzzles toolkit: a computational resource of RNA 3D structure benchmark datasets, structure manipulation, and evaluation tools","volume":"48","author":"Magnus","year":"2020","journal-title":"Nucleic Acids Res"},{"key":"2023052007035854000_btad315-B23","doi-asserted-by":"crossref","first-page":"625","DOI":"10.1006\/jmbi.1994.1017","article-title":"Significance of root-mean-square deviation in comparing three-dimensional structures of globular proteins","volume":"235","author":"Maiorov","year":"1994","journal-title":"J Mol Biol"},{"key":"2023052007035854000_btad315-B24","doi-asserted-by":"crossref","first-page":"6783010","DOI":"10.1155\/2017\/6783010","article-title":"Bioinformatics study of structural patterns in plant microRNA precursors","volume":"2017","author":"Miskiewicz","year":"2017","journal-title":"Biomed Res Int"},{"key":"2023052007035854000_btad315-B25","doi-asserted-by":"crossref","first-page":"e5","DOI":"10.1093\/nar\/gkw819","article-title":"Topology independent comparison of RNA 3D structures using the CLICK algorithm","volume":"45","author":"Nguyen","year":"2017","journal-title":"Nucleic Acids Res"},{"key":"2023052007035854000_btad315-B26","doi-asserted-by":"crossref","first-page":"e150","DOI":"10.1093\/nar\/gkx631","article-title":"SupeRNAlign: a new tool for flexible superposition of homologous RNA structures and inference of accurate structure-based sequence alignments","volume":"45","author":"Piatkowski","year":"2017","journal-title":"Nucleic Acids Res"},{"key":"2023052007035854000_btad315-B27","doi-asserted-by":"crossref","first-page":"1129","DOI":"10.1093\/bioinformatics\/btz738","article-title":"Topology-based classification of tetrads and quadruplex structures","volume":"36","author":"Popenda","year":"2020","journal-title":"Bioinformatics"},{"key":"2023052007035854000_btad315-B28","doi-asserted-by":"crossref","first-page":"2689","DOI":"10.1093\/bioinformatics\/btq506","article-title":"R3D align: global pairwise alignment of RNA 3D structures using local superpositions","volume":"26","author":"Rahrig","year":"2010","journal-title":"Bioinformatics"},{"key":"2023052007035854000_btad315-B29","first-page":"241","article-title":"RNApolis: computational platform for RNA structure analysis","volume":"44","author":"Szachniuk","year":"2019","journal-title":"FCDS"},{"key":"2023052007035854000_btad315-B30","doi-asserted-by":"crossref","first-page":"12177","DOI":"10.1093\/nar\/gky990","article-title":"Several structural motifs cooperate in determining the highly effective anti-thrombin activity of NU172 aptamer","volume":"46","author":"Troisi","year":"2018","journal-title":"Nucleic Acids Res"},{"key":"2023052007035854000_btad315-B31","doi-asserted-by":"crossref","first-page":"3174","DOI":"10.3390\/ijms20133174","article-title":"3D-PP: a tool for discovering conserved Three-Dimensional protein patterns","volume":"20","author":"Valdes-Jimenez","year":"2019","journal-title":"IJMS"},{"key":"2023052007035854000_btad315-B32","doi-asserted-by":"crossref","first-page":"W340","DOI":"10.1093\/nar\/gkq483","article-title":"iPARTS: an improved tool of pairwise alignment of RNA tertiary structures","volume":"38","author":"Wang","year":"2010","journal-title":"Nucleic Acids Res"},{"key":"2023052007035854000_btad315-B33","doi-asserted-by":"crossref","first-page":"276","DOI":"10.1186\/s12864-019-5631-3","article-title":"RMalign: an RNA structural alignment tool based on a novel scoring function RMscore","volume":"20","author":"Zheng","year":"2019","journal-title":"BMC Genomics"},{"key":"2023052007035854000_btad315-B34","doi-asserted-by":"crossref","first-page":"D253","DOI":"10.1093\/nar\/gkab1118","article-title":"ONQUADRO: a database of experimentally determined quadruplex structures","volume":"50","author":"Zok","year":"2022","journal-title":"Nucleic Acids Res"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btad315\/50278567\/btad315.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/39\/5\/btad315\/50408714\/btad315.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/39\/5\/btad315\/50408714\/btad315.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,20]],"date-time":"2023-05-20T07:04:37Z","timestamp":1684566277000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/doi\/10.1093\/bioinformatics\/btad315\/7160141"}},"subtitle":[],"editor":[{"given":"Yann","family":"Ponty","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2023,5,1]]},"references-count":34,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,5,4]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btad315","relation":{},"ISSN":["1367-4811"],"issn-type":[{"type":"electronic","value":"1367-4811"}],"subject":[],"published-other":{"date-parts":[[2023,5,1]]},"published":{"date-parts":[[2023,5,1]]},"article-number":"btad315"}}