{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T21:49:16Z","timestamp":1757454556485},"reference-count":37,"publisher":"Oxford University Press (OUP)","issue":"16","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015,8,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Given the importance of non-coding RNAs to cellular regulatory functions, it would be highly desirable to have accurate computational prediction of RNA 3D structure, a task which remains challenging. Even for a short RNA sequence, the space of tertiary conformations is immense; existing methods to identify native-like conformations mostly resort to random sampling of conformations to achieve computational feasibility. However, native conformations may not be examined and prediction accuracy may be compromised due to sampling. State-of-the-art methods have yet to deliver satisfactory predictions for RNAs of length beyond 50 nucleotides.<\/jats:p>\n               <jats:p>Results: This paper presents a method to tackle a key step in the RNA 3D structure prediction problem, the prediction of the nucleotide interactions that constitute the desired 3D structure. The research is based on a novel graph model, called a backbone k-tree, to tightly constrain the nucleotide interaction relationships considered for RNA 3D structures. It is shown that the new model makes it possible to efficiently predict the optimal set of nucleotide interactions (including the non-canonical interactions in all recently revealed families) from the query sequence along with known or predicted canonical basepairs. The preliminary results indicate that in most cases the new method can predict with a high accuracy the nucleotide interactions that constitute the 3D structure of the query sequence. It thus provides a useful tool for the accurate prediction of RNA 3D structure.<\/jats:p>\n               <jats:p>Availability and Implementation: The source package for BkTree is available at http:\/\/rna-informatics.uga.edu\/index.php?f=software&amp;p=BkTree.<\/jats:p>\n               <jats:p>Contact: \u00a0lding@uga.edu or cai@cs.uga.edu<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btv210","type":"journal-article","created":{"date-parts":[[2015,4,18]],"date-time":"2015-04-18T00:21:53Z","timestamp":1429316513000},"page":"2660-2667","source":"Crossref","is-referenced-by-count":1,"title":["Accurate prediction of RNA nucleotide interactions with backbone <i>k<\/i>-tree model"],"prefix":"10.1093","volume":"31","author":[{"given":"Liang","family":"Ding","sequence":"first","affiliation":[{"name":"1 Department of Computer Science,"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xingran","family":"Xue","sequence":"additional","affiliation":[{"name":"1 Department of Computer Science,"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sal","family":"LaMarca","sequence":"additional","affiliation":[{"name":"1 Department of Computer Science,"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohammad","family":"Mohebbi","sequence":"additional","affiliation":[{"name":"1 Department of Computer Science,"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Abdul","family":"Samad","sequence":"additional","affiliation":[{"name":"4 Department of Computer Science, BUITEMS, Pakistan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Russell L.","family":"Malmberg","sequence":"additional","affiliation":[{"name":"2 Institute of Bioinformatics and"},{"name":"3 Department of Plant Biology, University of Georgia, GA 30602, USA and"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Liming","family":"Cai","sequence":"additional","affiliation":[{"name":"1 Department of Computer Science,"},{"name":"2 Institute of Bioinformatics and"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2015,4,16]]},"reference":[{"key":"2023020202203422700_btv210-B1","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","article-title":"Linear time algorithms for NP-hard problems restricted to partial k-trees","volume":"23","author":"Arnborg","year":"1989","journal-title":"Discrete Appl. Math."},{"key":"2023020202203422700_btv210-B2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0012-365X(90)90292-P","article-title":"Forbidden minors characterization of partial 3-trees","volume":"80","author":"Arnborg","year":"1990","journal-title":"Discrete Math."},{"key":"2023020202203422700_btv210-B3","doi-asserted-by":"crossref","first-page":"1575","DOI":"10.1093\/bioinformatics\/btr168","article-title":"ProDy: protein dynamics inferred from theory and experiments","volume":"27","author":"Bakan","year":"2011","journal-title":"Bioinformatics"},{"key":"2023020202203422700_btv210-B4","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1093\/nar\/28.1.235","article-title":"The protein data bank","volume":"28","author":"Berman","year":"2000","journal-title":"Nucleic Acids Res."},{"key":"2023020202203422700_btv210-B5","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1261\/rna.027201.111","article-title":"Improved prediction of RNA 3D structure with insights into native state dynamics","volume":"18","author":"Bida","year":"2012","journal-title":"RNA"},{"key":"2023020202203422700_btv210-B6","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/j.ic.2009.03.008","article-title":"Treewidth computations I. Upper bounds","volume":"208","author":"Bodlaender","year":"2010","journal-title":"Inf. Comput."},{"key":"2023020202203422700_btv210-B7","doi-asserted-by":"crossref","first-page":"14664","DOI":"10.1073\/pnas.0703836104","article-title":"Automated de novo prediction of native-like RNA 3D structures","volume":"104","author":"Das","year":"2007","journal-title":"Proc. Natl Acad Sci"},{"key":"2023020202203422700_btv210-B8","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1038\/nmeth.1433","article-title":"Atomic accuracy in predicting and designing noncanonical RNA structure","volume":"7","author":"Das","year":"2010","journal-title":"Nat. Methods"},{"key":"2023020202203422700_btv210-B9","doi-asserted-by":"crossref","first-page":"1164","DOI":"10.1261\/rna.894608","article-title":"Ab initio RNA folding by discrete molecular dynamics: From structure prediction to folding mechanisms","volume":"14","author":"Ding","year":"2008","journal-title":"RNA"},{"key":"2023020202203422700_btv210-B10","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1007\/978-3-319-04921-2_25","article-title":"Stochastic k-tree grammar and its application in bio-molecular structure modeling","volume":"8370","author":"Ding","year":"2014","journal-title":"Lect. Notes Comput. Sci."},{"key":"2023020202203422700_btv210-B11","article-title":"Polynomial-time algorithms for maximum spanning k-tree constrained by Hamitonian path, in press","author":"Ding","year":"2014"},{"key":"2023020202203422700_btv210-B12","first-page":"25","article-title":"Ab initio prediction of RNA nucleotide interactions with backbone k-tree model","volume-title":"Proceedings of ECCB\u201914 Workshop on Computational Methods for Structural RNAs","author":"Ding","year":"2014"},{"key":"2023020202203422700_btv210-B13","doi-asserted-by":"crossref","first-page":"919","DOI":"10.1006\/jmbi.2001.4626","article-title":"Quantitative analysis of nucleic acid three-dimensional structures","volume":"308","author":"Gendron","year":"2001","journal-title":"J. Mol. Biol."},{"key":"2023020202203422700_btv210-B14","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1261\/rna.1270809","article-title":"Coarse-grained modeling of large RNA molecules with knowledge-based potentials and structure filters","volume":"15","author":"Jonikas","year":"2009","journal-title":"RNA"},{"key":"2023020202203422700_btv210-B15","doi-asserted-by":"crossref","first-page":"2057","DOI":"10.1093\/bioinformatics\/btq321","article-title":"Assemble: An interactive graphical tool to analyze and build RNA architectures at the 2D and tertiary levels","volume":"26","author":"Jossinet","year":"2010","journal-title":"Bioinformatics"},{"key":"2023020202203422700_btv210-B16","article-title":"Personal communication","author":"Laing","year":"2014"},{"key":"2023020202203422700_btv210-B17","doi-asserted-by":"crossref","first-page":"e71947","DOI":"10.1371\/journal.pone.0071947","article-title":"Predicting helical topologies in RNA junctions as tree graphs","volume":"8","author":"Laing","year":"2013","journal-title":"PLoS ONE"},{"key":"2023020202203422700_btv210-B18","doi-asserted-by":"crossref","first-page":"283101","DOI":"10.1088\/0953-8984\/22\/28\/283101","article-title":"Computational approaches to tertiary modeling of RNA","volume":"22","author":"Laing","year":"2010","journal-title":"J. Phys. Condens. Matter"},{"key":"2023020202203422700_btv210-B19","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1017\/S1355838201002515","article-title":"Geometric nomenclature and classification of RNA base pairs","volume":"7","author":"Leontis","year":"2001","journal-title":"RNA"},{"key":"2023020202203422700_btv210-B20","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-25740-7","volume-title":"RNA 3D structure analysis and prediction","author":"Leontis","year":"2012"},{"key":"2023020202203422700_btv210-B21","doi-asserted-by":"crossref","first-page":"3497","DOI":"10.1093\/nar\/gkf481","article-title":"The non-Watson\u2013Crick base pairs and their associated isostericity matrices","volume":"30","author":"Leontis","year":"2002","journal-title":"Nucleic Acids Res."},{"key":"2023020202203422700_btv210-B22","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1145\/1656274.1656278","article-title":"The WEKA data mining software: an update","volume":"11","author":"Hall","year":"2009","journal-title":"ACM SIGKDD Expl. Newsl."},{"key":"2023020202203422700_btv210-B23","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1080\/07391102.2008.10531240","article-title":"RNA2Dtertiary: a program for generating, viewing, and comparing 3-dimensional models of RNA","volume":"25","author":"Martinez","year":"2008","journal-title":"J. Biomol. Struct. Dyn."},{"key":"2023020202203422700_btv210-B24","volume-title":"Machine Learning","author":"Mitchell","year":"1997"},{"key":"2023020202203422700_btv210-B25","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":"2023020202203422700_btv210-B26","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":"2023020202203422700_btv210-B27","first-page":"57","article-title":"On the structure of k-tree","volume":"11","author":"Patil","year":"1986","journal-title":"J. Comb. Inf. Syst. Sci."},{"key":"2023020202203422700_btv210-B28","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1186\/1748-7188-8-27","article-title":"Efficient edit distance with duplications and contractions","volume":"8","author":"Pinhas","year":"2014","journal-title":"Algor. Mol. Biol."},{"key":"2023020202203422700_btv210-B29","doi-asserted-by":"crossref","first-page":"e112","DOI":"10.1093\/nar\/gks339","article-title":"Automated 3D structure composition for large RNAs","volume":"40","author":"Popenda","year":"2012","journal-title":"Nucleic Acids Res."},{"key":"2023020202203422700_btv210-B30","doi-asserted-by":"crossref","first-page":"i207","DOI":"10.1093\/bioinformatics\/bts226","article-title":"Towards 3D structure prediction of large RNA molecules: an integer programming framework to insert local tertiary motifs in RNA secondary structure","volume":"28","author":"Reinharz","year":"2013","journal-title":"Bioinformatics"},{"key":"2023020202203422700_btv210-B31","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1002\/wcms.1121","article-title":"An overview of the Amber biomolecular simulation package, WIREs Comput","volume":"3","author":"Salomon-Ferrer","year":"2012","journal-title":"Mol. Sci."},{"key":"2023020202203422700_btv210-B32","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":"2023020202203422700_btv210-B33","doi-asserted-by":"crossref","first-page":"1951","DOI":"10.1093\/bioinformatics\/btn328","article-title":"iFoldRNA: three-dimensional RNA structure prediction and folding","volume":"24","author":"Sharma","year":"2008","journal-title":"Bioinformatics"},{"key":"2023020202203422700_btv210-B34","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":"2023020202203422700_btv210-B35","article-title":"Graph algorithms","author":"Van Leeuwen","year":"1990","journal-title":"Handbook of Theoretical Computer Science, A: Algorithms and Complexity theory"},{"key":"2023020202203422700_btv210-B37","doi-asserted-by":"crossref","first-page":"4898","DOI":"10.1093\/nar\/gkp468","article-title":"Classification and energetics of the base-phosphate interactions in RNA","volume":"37","author":"Zirbel","year":"2009","journal-title":"Nucleic Acids Res."},{"key":"2023020202203422700_btv210-B38","article-title":"FR3D list of base-phosphate and base-ribose interactions in 1EHZ","author":"Zirbel","year":"2011"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/31\/16\/2660\/49034877\/bioinformatics_31_16_2660.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/31\/16\/2660\/49034877\/bioinformatics_31_16_2660.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T03:44:46Z","timestamp":1675309486000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/31\/16\/2660\/321332"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4,16]]},"references-count":37,"journal-issue":{"issue":"16","published-print":{"date-parts":[[2015,8,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btv210","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2015,8,15]]},"published":{"date-parts":[[2015,4,16]]}}}