Nucleic acid structure prediction

{{short description|Computational prediction of nucleic acid structure}}

{{About|the computational prediction of nucleic acid structure|experimental methods|Nucleic acid structure determination}}

Nucleic acid structure prediction is a computational method to determine secondary and tertiary nucleic acid structure from its sequence. Secondary structure can be predicted from one or several nucleic acid sequences. Tertiary structure can be predicted from the sequence, or by comparative modeling (when the structure of a homologous sequence is known).

The problem of predicting nucleic acid secondary structure is dependent mainly on base pairing and base stacking interactions; many molecules have several possible three-dimensional structures, so predicting these structures remains out of reach unless obvious sequence and functional similarity to a known class of nucleic acid molecules, such as transfer RNA (tRNA) or microRNA (miRNA), is observed. Many secondary structure prediction methods rely on variations of dynamic programming and therefore are unable to efficiently identify pseudoknots.

While the methods are similar, there are slight differences in the approaches to RNA and DNA structure prediction. In vivo, DNA structures are more likely to be duplexes with full complementarity between two strands, while RNA structures are more likely to fold into complex secondary and tertiary structures such as in the ribosome, spliceosome, or transfer RNA. This is partly because the extra oxygen in RNA increases the propensity for hydrogen bonding in the nucleic acid backbone. The energy parameters are also different for the two nucleic acids. The structure prediction methods can follow a completely theoretical approach, or a hybrid one incorporating experimental data.{{Cite journal|last1=Ponce-Salvatierra|first1=Almudena|last2=Astha|last3=Merdas|first3=Katarzyna|last4=Chandran|first4=Nithin|last5=Ghosh|first5=Pritha|last6=Mukherjee|first6=Sunandan|last7=Bujnicki|first7=Janusz M|date=2019-01-22|title=Computational modeling of RNA 3D structure based on experimental data|journal=Bioscience Reports|volume=39|issue=2|pages=BSR20180430|doi=10.1042/bsr20180430|pmid=30670629|issn=0144-8463|pmc=6367127}}{{Cite journal|last1=Magnus|first1=Marcin|last2=Matelska|first2=Dorota|last3=Łach|first3=Grzegorz|last4=Chojnowski|first4=Grzegorz|last5=Boniecki|first5=Michal J|last6=Purta|first6=Elzbieta|last7=Dawson|first7=Wayne|last8=Dunin-Horkawicz|first8=Stanislaw|last9=Bujnicki|first9=Janusz M|date=2014-04-23|title=Computational modeling of RNA 3D structures, with the aid of experimental restraints|journal=RNA Biology|volume=11|issue=5|pages=522–536|doi=10.4161/rna.28826|pmid=24785264|pmc=4152360|issn=1547-6286}}

Single sequence structure prediction

A common problem for researchers working with RNA is to determine the three-dimensional structure of the molecule given only a nucleic acid sequence. However, in the case of RNA much of the final structure is determined by the secondary structure or intra-molecular base pairing interactions of the molecule. This is shown by the high conservation of base pairings across diverse species.

=The most stable structure=

Secondary structure of small RNA molecules is largely determined by strong, local interactions such as hydrogen bonds and base stacking. Summing the free energy for such interactions should provide an approximation for the stability of a given structure. To predict the folding free energy of a given secondary structure, an empirical nearest-neighbor model is used. In the nearest neighbor model the free energy change for each motif depends on the sequence of the motif and of its closest base-pairs. The model and parameters of minimal energy for Watson–Crick pairs, GU pairs and loop regions were derived from empirical calorimetric experiments, the most up-to-date parameters were published in 2004, although most software packages use the prior set assembled in 1999.

The simplest way to find the lowest free energy structure would be to generate all possible structures and calculate the free energy for it, but the number of possible structures for a sequence increases exponentially with the length of RNA: number of secondary structures = (1,8)^N, N- number of nucleotides. For longer molecules, the number of possible secondary structures is huge: a sequence of 100 nucleotides has more than 10²⁵ possible secondary structures.

=Dynamic programming algorithms=

Most popular methods for predicting RNA and DNA's secondary structure involve dynamic programming. One of the early attempts at predicting RNA secondary structure was made by Ruth Nussinov and co-workers who developed a dynamic programming-based algorithm that maximized the length and number of a series of "blocks" (polynucleotide chains). Each "block" required at least two nucleotides, which reduced the algorithm's storage requirements over single base-matching approaches. Nussinov et al. later published an adapted approach with improved performance that increased the RNA size limit to ~1,000 bases by folding increasingly sized subsections while storing the results of prior folds, now known as the Nussinov algorithm. In 1981, Michael Zuker and Patrick Stiegler proposed a refined approach with performance comparable to Nussinov et al.'s solution but with the additional ability to find also find "suboptimal" secondary structures.

Dynamic programming algorithms provide a means to implicitly check all variants of possible RNA secondary structures without explicitly generating the structures. First, the lowest conformational free energy is determined for each possible sequence fragment starting with the shortest fragments and then for longer fragments. For longer fragments, recursion on the optimal free energy changes determined for shorter sequences speeds the determination of the lowest folding free energy. Once the lowest free energy of the complete sequence is calculated, the exact structure of RNA molecule is determined.

Dynamic programming algorithms are commonly used to detect base pairing patterns that are "well-nested", that is, form hydrogen bonds only to bases that do not overlap one another in sequence position. Secondary structures that fall into this category include double helices, stem-loops, and variants of the "cloverleaf" pattern found in transfer RNA molecules. These methods rely on pre-calculated parameters which estimate the free energy associated with certain types of base-pairing interactions, including Watson-Crick and Hoogsteen base pairs. Depending on the complexity of the method, single base pairs may be considered, and short two- or three-base segments, to incorporate the effects of base stacking. This method cannot identify pseudoknots, which are not well nested, without substantial algorithmic modifications that are computationally very costly.

=Suboptimal structures=

The accuracy of RNA secondary structure prediction from one sequence by free energy minimization is limited by several factors:

The free energy value's list in nearest neighbor model is incomplete
Not all known RNA folds in such a way as to conform with the thermodynamic minimum.
Some RNA sequences have more than one biologically active conformation (i.e., riboswitches)

For this reason, the ability to predict structures which have similar low free energy can provide significant information. Such structures are termed suboptimal structures. MFOLD is one program that generates suboptimal structures.

=Predicting pseudoknots=

One of the issues when predicting RNA secondary structure is that the standard free energy minimization and statistical sampling methods can not find pseudoknots. The major problem is that the usual dynamic programing algorithms, when predicting secondary structure, consider only the interactions between the closest nucleotides, while pseudoknotted structures are formed due to interactions between distant nucleotides. Rivas and Eddy published a dynamic programming algorithm for predicting pseudoknots. However, this dynamic programming algorithm is very slow. The standard dynamic programming algorithm for free energy minimization scales O(N³) in time (N is the number of nucleotides in the sequence), while the Rivas and Eddy algorithm scales O(N⁶) in time. This has prompted several researchers to implement versions of the algorithm that restrict classes of pseudoknots, resulting in performance gains. For example, pknotsRG tool includes only the class of simple recursive pseudoknots and scales O(N4) in time.

=Other approaches for RNA secondary structure prediction=

Another approach for RNA secondary structure determination is to sample structures from the Boltzmann ensemble, as exemplified by the program SFOLD. The program generates a statistical sample of all possible RNA secondary structures. The algorithm samples secondary structures according to the Boltzmann distribution. The sampling method offers an appealing solution to the problem of uncertainties in folding.

Comparative secondary structure prediction

File:TRNA structure space.png

Sequence covariation methods rely on the existence of a data set composed of multiple homologous RNA sequences with related but dissimilar sequences. These methods analyze the covariation of individual base sites in evolution; maintenance at two widely separated sites of a pair of base-pairing nucleotides indicates the presence of a structurally required hydrogen bond between those positions. The general problem of pseudoknot prediction has been shown to be NP-complete.

In general, the problem of alignment and consensus structure prediction are closely related. Three different approaches to the prediction of consensus structures can be distinguished:

Folding of alignment
Simultaneous sequence alignment and folding
Alignment of predicted structures

=Align then fold=

A practical heuristic approach is to use multiple sequence alignment tools to produce an alignment of several RNA sequences, to find consensus sequence and then fold it. The quality of the alignment determines the accuracy of the consensus structure model. Consensus sequences are folded using various approaches similarly as in individual structure prediction problem. The thermodynamic folding approach is exemplified by RNAalifold program. The different approaches are exemplified by Pfold and ILM programs. Pfold program implements a SCFGs. ILM (iterated loop matching) unlike the other algorithms for folding of alignments, can return pseudoknoted structures. It uses combination of thermodynamics and mutual information content scores.

=Align and fold=

Evolution frequently preserves functional RNA structure better than RNA sequence. Hence, a common biological problem is to infer a common structure for two or more highly diverged but homologous RNA sequences. In practice, sequence alignments become unsuitable and do not help to improve the accuracy of structure prediction, when sequence similarity of two sequences is less than 50%.{{cite journal |doi=10.1093/bfgp/elp043 |vauthors=Bernhart SH, Hofacker IL |title=From consensus structure prediction to RNA gene finding|journal=Brief Funct Genomic Proteomic |volume=8 |issue=6 |pages=461–71 |year=2009 |pmid=19833701|doi-access=free }}

Structure-based alignment programs improves the performance of these alignments and most of them are variants of the Sankoff algorithm. Basically, Sankoff algorithm is a merger of sequence alignment and Nussinov (maximal-pairing) folding dynamic programming method. Sankoff algorithm itself is a theoretical exercise because it requires extreme computational resources (O^(n3m) in time, and O^(n2m) in space, where n is the sequence length and m is the number of sequences). Some notable attempts at implementing restricted versions of Sankoff's algorithm are Foldalign, Dynalign, PMmulti/PMcomp, Stemloc, and Murlet. In these implementations the maximal length of alignment or variants of possible consensus structures are restricted. For example, Foldalign focuses on local alignments and restricts the possible length of the sequences alignment.

=Fold then align=

A less widely used approach is to fold the sequences using single sequence structure prediction methods and align the resulting structures using tree-based metrics. The fundamental weakness with this approach is that single sequence predictions are often inaccurate, thus all further analyses are affected.

Tertiary structure prediction

Once secondary structure of RNA is known, the next challenge is to predict tertiary structure. The biggest problem is to determine the structure of regions between double stranded helical regions. Also RNA molecules often contain posttranscriptionally modified nucleosides, which because of new possible non-canonical interactions, cause a lot of troubles for tertiary structure prediction.{{cite journal |doi=10.1371/journal.pcbi.1000406 |vauthors=Frellsen J, Moltke I, Thiim M, Mardia KV, Ferkinghoff-Borg J, Hamelryck T |title=A probabilistic model of RNA conformational space|journal=PLOS Comput Biol |volume=5 |issue=6 |pages=e1000406 |year=2009 |pmid=19543381 |pmc=2691987|bibcode=2009PLSCB...5E0406F |doi-access=free }}

The three-dimensional structure prediction methods can use comparative modeling which starts from a related known structure known as the template.{{Cite journal|last1=Rother|first1=Magdalena|last2=Rother|first2=Kristian|last3=Puton|first3=Tomasz|last4=Bujnicki|first4=Janusz M.|date=2011-02-07|title=ModeRNA: a tool for comparative modeling of RNA 3D structure|journal=Nucleic Acids Research|volume=39|issue=10|pages=4007–4022|doi=10.1093/nar/gkq1320|issn=1362-4962|pmc=3105415|pmid=21300639}} The alternative strategy is de novo modeling of RNA secondary structure{{Cite book|title=RNA 3D structure analysis and prediction|editor=Neocles B Leontis|editor2=Eric Westhof|date=2012|publisher=Springer|isbn=9783642257407|oclc=795570014}} which uses physics-based principles such as molecular dynamics{{Cite journal|last1=Vangaveti|first1=Sweta|last2=Ranganathan|first2=Srivathsan V.|last3=Chen|first3=Alan A.|date=2016-10-04|title=Advances in RNA molecular dynamics: a simulator's guide to RNA force fields|journal=Wiley Interdisciplinary Reviews: RNA|volume=8|issue=2|pages=e1396|doi=10.1002/wrna.1396|pmid=27704698|s2cid=35501632|issn=1757-7004}} or random sampling of the conformational landscape{{Cite journal|last=Chen|first=Shi-Jie|date=June 2008|title=RNA Folding: Conformational Statistics, Folding Kinetics, and Ion Electrostatics|journal=Annual Review of Biophysics|volume=37|issue=1|pages=197–214|doi=10.1146/annurev.biophys.37.032807.125957|issn=1936-122X|pmc=2473866|pmid=18573079}} followed by screening with a statistical potential for scoring.{{Cite journal|last1=Laing|first1=Christian|last2=Schlick|first2=Tamar|date=June 2011|title=Computational approaches to RNA structure prediction, analysis, and design|journal=Current Opinion in Structural Biology|volume=21|issue=3|pages=306–318|doi=10.1016/j.sbi.2011.03.015|issn=0959-440X|pmc=3112238|pmid=21514143}} These methods either use an all-atom representation{{Citation|last1=Zhao|first1=Chenhan|volume=1654|date=2017|series=Methods in Molecular Biology|pages=3–15|publisher=Springer New York|isbn=9781493972302|last2=Xu|first2=Xiaojun|last3=Chen|first3=Shi-Jie|title=Functional Genomics |chapter=Predicting RNA Structure with Vfold |doi=10.1007/978-1-4939-7231-9_1|pmid=28986779|pmc=5762135}} of the nucleic acid structure or a coarse-grained representation.{{Cite journal|last1=Boniecki|first1=Michal J.|last2=Lach|first2=Grzegorz|last3=Dawson|first3=Wayne K.|last4=Tomala|first4=Konrad|last5=Lukasz|first5=Pawel|last6=Soltysinski|first6=Tomasz|last7=Rother|first7=Kristian M.|last8=Bujnicki|first8=Janusz M.|date=2015-12-19|title=SimRNA: a coarse-grained method for RNA folding simulations and 3D structure prediction|journal=Nucleic Acids Research|volume=44|issue=7|pages=e63|doi=10.1093/nar/gkv1479|issn=0305-1048|pmid=26687716|pmc=4838351}} The low-resolution structures generated by many of these modeling methods are then subjected to high-resolution refinement.{{Cite journal|last1=Stasiewicz|first1=Juliusz|last2=Mukherjee|first2=Sunandan|last3=Nithin|first3=Chandran|last4=Bujnicki|first4=Janusz M.|date=2019-03-21|title=QRNAS: software tool for refinement of nucleic acid structures|journal=BMC Structural Biology|volume=19|issue=1|pages=5|doi=10.1186/s12900-019-0103-1|pmid=30898165|pmc=6429776|issn=1472-6807 |doi-access=free }} Evaluations of standalone RNA 3D structure prediction methods indicate that machine learning-based methods effectively predict global RNA folds, while non-ML-based methods demonstrate higher precision in modeling intramolecular interactions and ligand binding sites.{{Cite journal |last1=Nithin |first1=Chandran |last2=Kmiecik |first2=Sebastian |last3=Błaszczyk |first3=Roman |last4=Nowicka |first4=Julita |last5=Tuszyńska |first5=Irina |date=2024-06-25 |title=Comparative analysis of RNA 3D structure prediction methods: towards enhanced modeling of RNA–ligand interactions |journal=Nucleic Acids Research |volume=52 |issue=13 |pages=7465–7486 |doi=10.1093/nar/gkae541 |issn=0305-1048|doi-access=free |pmid=38917327 |pmc=11260495 }}

References

{{Reflist|refs=

{{cite journal |doi= 10.1093/nar/gkg938 |vauthors=Ding Y, Lawrence CE |year= 2003 |title= A statistical sampling algorithm for RNA secondary structure prediction |journal= Nucleic Acids Res. |volume= 31 |issue= 24| pages= 7280–301 |pmid= 14654704 |pmc= 297010}}

{{cite journal |doi= 10.1186/1471-2105-5-140 |author= Gardner P.P. |year= 2004 |last2= Giegerich |first2= Robert |title= A comprehensive comparison of comparative RNA structure prediction approaches |journal= BMC Bioinformatics |volume= 5 |page= 140 |pmid=15458580 |pmc=526219 |doi-access= free }}

Harmanci AO, Sharma G, Mathews DH, (2007), [http://www.biomedcentral.com/1471-2105/8/130 Efficient Pairwise RNA Structure Prediction Using Probabilistic Alignment Constraints in Dynalign], BMC Bioinformatics, 8(130).

{{cite journal |doi= 10.1093/bioinformatics/bti279 |vauthors=Havgaard JH, Lyngso RB, Stormo GD, Gorodkin J |year= 2005 |title= Pairwise local structural alignment of RNA sequences with sequence similarity less than 40% |journal= Bioinformatics |volume= 21 |issue= 9| pages= 1815–24 |pmid= 15657094|doi-access= free }}

{{cite journal |doi= 10.1093/bioinformatics/bth229 |vauthors=Hofacker IL, Bernhart SH, Stadler PF |year= 2004 |title= Alignment of RNA base pairing probability matrices |journal= Bioinformatics |volume= 20 |issue= 14| pages= 2222–7 |pmid= 15073017|doi-access= free }}

{{cite journal |doi= 10.1016/S0022-2836(02)00308-X |vauthors=Hofacker IL, Fekete M, Stadler PF |year= 2002 |title= Secondary structure prediction for aligned RNA sequences |journal= J Mol Biol |volume= 319 |issue= 5| pages= 1059–66 |pmid= 12079347|citeseerx=10.1.1.73.479 }}

Holmes I. (2005) [http://www.biomedcentral.com/1471-2105/6/73 Accelerated probabilistic inference of RNA structure evolution]. BMC Bioinformatics. 2005 Mar 24;6:73.

{{cite journal |doi= 10.1093/bioinformatics/btm146 |vauthors=Kiryu H, Tabei Y, Kin T, Asai K |year= 2007 |title= Murlet: A practical multiple alignment tool for structural RNA sequences |journal= Bioinformatics |volume= 23 |issue= 13| pages= 1588–1598 |pmid= 17459961|doi-access= free }}

{{cite journal |doi= 10.1093/nar/gkg614 |vauthors=Knudsen B, Hein J |year= 2003 |title= Pfold: RNA secondary structure prediction using stochastic context-free grammars |url= |journal= Nucleic Acids Res. |volume= 31 |issue= 13| pages= 3423–8 |pmid= 12824339 |pmc= 169020}}

{{cite journal | vauthors = Lyngsø RB, Pedersen CN | year = 2000 | title = RNA pseudoknot prediction in energy-based models | journal = J Comput Biol | volume = 7 | issue = 3–4| pages = 409–427 | doi=10.1089/106652700750050862 | pmid=11108471| citeseerx = 10.1.1.34.4044 }}

{{cite journal | vauthors = Major F, Turcotte M, Gautheret D, Lapalme G, Fillion E, Cedergren R | date = Sep 1991 | title = The combination of symbolic and numerical computation for three-dimensional modeling of RNA | journal = Science | volume = 253 | issue = 5025| pages = 1255–60 | doi=10.1126/science.1716375| pmid = 1716375 | bibcode = 1991Sci...253.1255F }}

{{cite journal | vauthors = Major F, Gautheret D, Cedergren R | date = Oct 1993 | title = Reproducing the three-dimensional structure of a tRNA molecule from structural constraints | journal = Proc Natl Acad Sci U S A | volume = 90 | issue = 20| pages = 9408–12 | doi=10.1073/pnas.90.20.9408| pmid = 8415714 | pmc = 47577| bibcode = 1993PNAS...90.9408M| doi-access = free }}

{{cite journal |author= Mathews D.H. |year= 2006 |title= Revolutions in RNA secondary structure prediction |journal= J. Mol. Biol. |volume= 359 |issue= 3|pages= 526–532 |doi=10.1016/j.jmb.2006.01.067 |pmid=16500677}}

{{cite journal |doi= 10.1073/pnas.0401799101 |vauthors=Mathews DH, Disney MD, Childs JL, Schroeder SJ, Zuker M, Turner DH |year= 2004 |title= Incorporating chemical modification constraints into a dynamic programming algorithm for prediction of RNA secondary structure |journal= Proceedings of the National Academy of Sciences USA |volume= 101 |issue= 19|pages= 7287–7292 |pmid=15123812 |pmc=409911 |bibcode=2004PNAS..101.7287M|doi-access=free }}

{{cite journal |doi= 10.1006/jmbi.1999.2700 |vauthors=Mathews DH, Sabina J, Zuker M, Turner DH |year= 1999 |title= Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure |journal= J Mol Biol |volume= 288 |issue= 5| pages= 911–40 |pmid= 10329189|s2cid=19989405 |doi-access= free }}

{{cite journal |doi= 10.1006/jmbi.2001.5351 |vauthors=Mathews DH, Turner DH |year= 2002 |title= Dynalign: an algorithm for finding the secondary structure common to two RNA sequences |journal= J Mol Biol |volume= 317 |issue= 2| pages= 191–203 |pmid= 11902836}}

{{cite journal |doi= 10.1002/bip.360290621 |author= McCaskill JS |year= 1990 |title= The equilibrium partition function and base pair binding probabilities for RNA secondary structure |journal= Biopolymers |volume= 29 |issue= 6–7| pages= 1105–19 |pmid= 1695107|hdl= 11858/00-001M-0000-0013-0DE3-9 |s2cid= 12629688 |hdl-access= free }}

Nussinov R, Piecznik G, Grigg JR and Kleitman DJ (1978) Algorithms for loop matchings. SIAM Journal on Applied Mathematics.

{{cite journal |doi= 10.1073/pnas.77.11.6309 |vauthors=Nussinov R, Jacobson AB |year= 1980 |title= Fast algorithm for predicting the secondary structure of single-stranded RNA |journal= Proc Natl Acad Sci U S A |volume= 77 |issue= 11| pages= 6309–13 |pmid= 6161375 |pmc= 350273 |bibcode= 1980PNAS...77.6309N|doi-access=free }}

{{cite journal |author1=Reeder J. |author2=Giegerich R. |year= 2004 |title= Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics |journal= BMC Bioinformatics |volume= 5 |page= 104 |doi= 10.1186/1471-2105-5-104 |pmid=15294028 |pmc=514697 |doi-access=free }}

{{cite journal |doi= 10.1006/jmbi.1998.2436 |vauthors=Rivas E, Eddy SR |year= 1999 |title= A dynamic programming algorithm for RNA structure prediction including pseudoknots |journal= J Mol Biol |volume= 285 |issue= 5| pages= 2053–68 |pmid= 9925784|arxiv= physics/9807048|s2cid=2228845 }}

Ruan, J., Stormo, G.D. & Zhang, W. (2004) ILM: a web server for predicting RNA secondary structures with pseudoknots. Nucleic Acids Research, 32(Web Server issue), W146-149.

{{cite journal | vauthors = Sankoff D | year = 1985 | title = Simultaneous solution of the RNA folding, alignment and protosequence problems | journal = SIAM Journal on Applied Mathematics | volume = 45 | issue = 5| pages = 810–825 | doi=10.1137/0145048| citeseerx = 10.1.1.665.4890 }}

Shapiro BA, Yingling YG, Kasprzak W, Bindewald E. (2007) Bridging the gap in RNA structure prediction. Curr Opin Struct Biol.

Torarinsson E, Havgaard JH, Gorodkin J. (2007) Multiple structural alignment and clustering of RNA sequences. Bioinformatics.

{{cite journal | vauthors = Zuker M, Stiegler P | year = 1981 | title = Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information | journal = Nucleic Acids Res | volume = 9 | issue = 1| pages = 133–48 | doi=10.1093/nar/9.1.133 | pmid=6163133 | pmc=326673}}

{{cite journal |author1=Zuker M. |author2=Sankoff D. |year= 1984 |title= RNA secondary structures and their prediction |journal= Bull. Math. Biol. |volume= 46 |issue= 4|pages= 591–621 |doi=10.1016/s0092-8240(84)80062-2|doi-broken-date=1 November 2024 |s2cid=189885784 }}

{{cite journal |doi= 10.1093/nar/gkg595 |author= Zuker M |year= 2003 |title= Mfold web server for nucleic acid folding and hybridization prediction |journal= Nucleic Acids Research |volume= 31 |issue= 13| pages= 3406–3415 |pmid= 12824337 |pmc= 169194}}

Shapiro BA and Zhang K (1990) Comparing Multiple RNA Secondary Structures Using Tree Comparisons Computer Applications in the Biosciences, vol. 6, no. 4, pp. 309–318.

}}