Combinatorics of locally optimal RNA secondary structures

It is a classical result of Stein and Waterman that the asymptotic number of RNA secondary structures is $1.104366 \cdot n^{-3/2} \cdot 2.618034^n$ . Motivated by the kinetics of RNA secondary structure formation, we are interested in determining the asymptotic number of secondary structures that are locally optimal, with respect to a particular energy model. In the Nussinov energy model, where each base pair contributes $-1$ towards the energy of the structure, locally optimal structures are exactly the saturated structures, for which we have previously shown that asymptotically, there are $1.07427\cdot n^{-3/2} \cdot 2.35467^n$ many saturated structures for a sequence of length $n$ . In this paper, we consider the base stacking energy model, a mild variant of the Nussinov model, where each stacked base pair contributes $-1$ toward the energy of the structure. Locally optimal structures with respect to the base stacking energy model are exactly those secondary structures, whose stems cannot be extended. Such structures were first considered by Evers and Giegerich, who described a dynamic programming algorithm to enumerate all locally optimal structures. In this paper, we apply methods from enumerative combinatorics to compute the asymptotic number of such structures. Additionally, we consider analogous combinatorial problems for secondary structures with annotated single-stranded, stacking nucleotides (dangles).     

Combinatorics of saturated secondary structures of RNA.

Following Zuker (1986), a saturated secondary structure for a given RNA sequence is a secondary structure such that no base pair can be added without violating the definition of secondary structure, e.g., without introducing a pseudoknot. In the Nussinov-Jacobson energy model (Nussinov and Jacobson, 1980), where the energy of a secondary structure is -1 times the number of base pairs, saturated secondary structures are local minima in the energy landscape, hence form kinetic traps during the folding process. Here we present recurrence relations and closed form asymptotic limits for combinatorial problems related to the number of saturated secondary structures. In addition, Python source code to compute the number of saturated secondary structures having k base pairs can be found at the web servers link of bioinformatics.bc.edu/clotelab/.     

Network Properties of the Ensemble of RNA Structures

We describe the first dynamic programming algorithm that computes the expected degree for the network, or graph G = (V, E) of all secondary structures of a given RNA sequence a = a ₁, …, a _n. Here, the nodes V correspond to all secondary structures of a, while an edge exists between nodes s, t if the secondary structure t can be obtained from s by adding, removing or shifting a base pair. Since secondary structure kinetics programs implement the Gillespie algorithm, which simulates a random walk on the network of secondary structures, the expected network degree may provide a better understanding of kinetics of RNA folding when allowing defect diffusion, helix zippering, and related conformation transformations. We determine the correlation between expected network degree, contact order, conformational entropy, and expected number of native contacts for a benchmarking dataset of RNAs. Source code is available at http://bioinformatics.bc.edu/clotelab/RNAexpNumNbors.     

Investigation of the Bernoulli model for RNA secondary structures

Within this paper we investigate the Bernoulli model for random secondary structures of ribonucleic acid (RNA) molecules. Assuming that two random bases can form a hydrogen bond with probability p we prove asymptotic equivalents for the averaged number of hairpins and bulges, the averaged loop length, the expected order, the expected number of secondary structures of size n and order k and further parameters all depending on p. In this way we get an insight into the change of shape of a random structure during the process . Afterwards we compare the computed parameters for random structures in the Bernoulli model to the corresponding quantities for real existing secondary structures of large subunit rRNA molecules found in the database of Wuyts et al. That is how it becomes possible to identify those parameters which behave (almost) randomly and those which do not and thus should be considered as interesting, e.g., with respect to the biological functions or the algorithmic prediction of RNA secondary structures.     

Loop dependence of the stability and dynamics of nucleic acid hairpins

Hairpin loops are critical to the formation of nucleic acid secondary structure, and to their function. Previous studies revealed a steep dependence of single-stranded DNA (ssDNA) hairpin stability with length of the loop (L) as ~L^{8.5 ± 0.5}, in 100 mM NaCl, which was attributed to intraloop stacking interactions. In this article, the loop-size dependence of RNA hairpin stabilities and their folding/unfolding kinetics were monitored with laser temperature-jump spectroscopy. Our results suggest that similar mechanisms stabilize small ssDNA and RNA loops, and show that salt contributes significantly to the dependence of hairpin stability on loop size. In 2.5 mM MgCl₂, the stabilities of both ssDNA and RNA hairpins scale as ~L^{4 ± 0.5}, indicating that the intraloop interactions are weaker in the presence of Mg²⁺. Interestingly, the folding times for ssDNA hairpins (in 100 mM NaCl) and RNA hairpins (in 2.5 mM MgCl₂) are similar despite differences in the salt conditions and the stem sequence, and increase similarly with loop size, ~L^{2.2 ± 0.5} and ~L^{2.6 ± 0.5}, respectively. These results suggest that hairpins with small loops may be specifically stabilized by interactions of the Na⁺ ions with the loops. The results also reinforce the idea that folding times are dominated by an entropic search for the correct nucleating conformation.     

Mismatch Recognition Protein MutS�� Does Not Hijack (CAG)n Hairpin Repair in Vitro

CAG repeats form stable hairpin structures, which are believed to be responsible for CAG repeat expansions associated with certain human neurological diseases. Human cells possess an accurate DNA hairpin repair system that prevents expansion of disease-associated CAG repeats. Based on transgenic animal studies, it is suggested that (CAG)_n expansion is caused by abnormal binding of the MutSβ mismatch recognition protein to (CAG)_n hairpins, leading to hijacking mismatch repair function during (CAG)_n hairpin repair. We demonstrate here that MutSβ displays identical biochemical and biophysical activities (including ATP-provoked conformational change, ATPase, ATP binding, and ADP binding) when interacting with a (CAG)_n hairpin and a mismatch. More importantly, our in vitro functional hairpin repair assays reveal that excess MutSβ does not inhibit (CAG)_n hairpin repair in HeLa nuclear extracts. Evidence presented here provides a novel view as to whether or not MutSβ is involved in CAG repeat instability in humans.Expansion of trinucleotide repeats (TNRs)³ causes hereditary neurological disorders such as Huntington disease and myotonic dystrophy, whose clinical symptoms are directly linked to expansion of CAG and CTG repeats, respectively (1–3). The precise mechanisms by which TNR expansion occurs and the factors that promote it are not fully understood. It has been proposed that CAG and CTG repeats form thermostable hairpins that include A-A and T-T mispairs in the hairpin stem (4, 5). Therefore, cellular mechanisms that process DNA hairpin/loop structures and/or A-A or T-T mispairs may influence TNR stability.Recent studies have identified and characterized a DNA hairpin repair (HPR) system in human cells that promotes CAG/CTG repeat stability (6, 7). The mechanism of human HPR involves incision and removal of CAG/CTG repeat hairpins in a nick-directed and proliferating cell nuclear antigen-dependent manner, followed by DNA resynthesis using the continuous strand as a template (6). In addition to human HPR, the human mismatch repair (MMR) system is well known for its role in stabilizing simple repetitive sequences called microsatellites, which are prone to forming small loops or insertion/deletion (ID) mispairs. In human cells, MutSα (MSH2–MSH6) and MutSβ (MSH2–MSH3) both bind to 1–2-nt ID mispairs, but MutSβ has higher affinity for these small loops (8). Defects in MMR genes cause microsatellite instability and predisposition to cancer (9), demonstrating that MMR is essential for genetic stability in human cells. Surprisingly, genetic studies in mice suggest that MutSβ promotes (CAG)_n expansion and TNR instability. These studies show that expansion of a heterologous (CAG)_n tract occurs in wild type and MSH6^−/− mice but that expansion of the (CAG)_n tract is suppressed in MSH2^−/− and MSH3^−/− mice (10, 11). Recently, Owens et al. (11) reported that binding to a (CAG)_n hairpin influences the protein conformation, nucleotide binding, and hydrolysis activities of MutSβ so that they are different from what has been reported for MutSα during mismatch recognition. It is therefore hypothesized that (CAG)_n hairpins, through their ability to alter the biochemical properties of MutSβ, hijack the MMR process, leading to CAG repeat expansion instead of CAG hairpin removal (11). However, it is not clear why MMR, a major genome maintenance system, would promote TNR instability instead of TNR stability. We, therefore, have developed a novel functional assay and examined the validity of this hypothesis. Our results reveal that MutSβ displays normal biochemical activities when binding to CAG hairpins and does not inhibit (CAG)_n hairpin repair. The observations presented here provide novel thoughts on whether or not or how MutSβ is involved in CAG repeat instability in human cells.     

The Role of XPG in Processing (CAG)n/(CTG)n DNA Hairpins

Background

During DNA replication or repair, disease-associated (CAG)_n/(CTG)_n expansion can result from formation of hairpin structures in the repeat tract of the newly synthesized or nicked DNA strand. Recent studies identified a nick-directed (CAG)_n/(CTG)_n hairpin repair (HPR) system that removes (CAG)_n/(CTG)_n hairpins from human cells via endonucleolytic incisions. Because the process is highly similar to the mechanism by which XPG and XPF endonucleases remove bulky DNA lesions during nucleotide excision repair, we assessed the potential role of XPG in conducting (CAG)_n/(CTG)_n HPR.

Results

To determine if the XPG endonuclease is involved in (CAG)_n/(CTG)_n hairpin removal, two XPG-deficient cell lines (GM16024 and AG08802) were examined for their ability to process (CAG)_n/(CTG)_n hairpins in vitro. We demonstrated that the GM16024 cell line processes all hairpin substrates as efficiently as HeLa cells, and that the AG08802 cell line is partially defective in HPR. Analysis of repair intermediates revealed that nuclear extracts from both XPG-deficient lines remove CAG/CTG hairpins via incisions, but the incision products are distinct from those generated in HeLa extracts. We also show that purified recombinant XPG protein greatly stimulates HPR in XPG-deficient extracts by promoting an incision 5' to the hairpin.

Conclusions

Our results strongly suggest that 1) human cells possess multiple pathways to remove (CAG)_n/(CTG)_n hairpins located in newly synthesized (or nicked) DNA strand; and 2) XPG, although not essential for (CAG)_n/(CTG)_n hairpin removal, stimulates HPR by facilitating a 5' incision to the hairpin. This study reveals a novel role for XPG in genome-maintenance and implicates XPG in diseases caused by trinucleotide repeat expansion.     

79 Thermodynamic and kinetic studies of trinucleotide repeat (TNR) DNA

The expansion of trinucleotide repeat (TNR) DNA has been linked to several neurodegenerative diseases (McMurray, 2010). The number of repeats is usually a characteristic indication of the severity of TNR-related diseases, with longer repeats giving higher propensity to expand and earlier onset of symptoms (López, Cleary, & Pearson, 2010). It is generally accepted that formation of noncanonical secondary structures, such as stem-loop hairpins or slipouts, contributes to the expansion mechanisms during aberrant DNA replication or repair processes (Mirkin, 2007). The stability of these hairpins is considered an important factor (Paiva & Sheardy, 2005). In this work, we used differential scanning calorimetry (DSC) and UV–Vis spectroscopy to study the thermodynamic and kinetic stability of a series of (CTG)_n and (CAG)_n TNR stem-loop hairpins and their corresponding (CTG)_n/(CAG)_n duplexes (n?=?6–14). We found that hairpins with n?=?even and n?=?even?+?1 (odd) repeats possess very similar thermodynamic stability. But, when converting to the canonical duplex form, odd-repeat hairpins are more stabilized compared to those of their even-repeat counterparts. Within both even- and odd-repeat series, hairpins with longer repeats are thermodynamically more stabilized compared to the shorter ones. Kinetic experiments of the stem-loop hairpin to duplex conversion revealed a longer lifetime for the even-repeat hairpins, while the odd-repeat hairpins convert to duplexes 10-fold faster. Also, hairpins with increased number of repeats are more resistant to the conversion when considered within the even- or odd-repeat series individually. Taken together, although it is thermodynamically more favored that hairpins containing longer repeats convert to canonical duplex form; On the contrary, these longer hairpins are kinetically trapped during the conversion and therefore can persist the noncanonical structures, which allows TNR expansion.     

Structural characterization of the highly conserved 98-base sequence at the 3' end of HCV RNA genome and the complementary sequence located at the 5' end of the replicative viral strand

Oligoribonucleotides that corresponded to the X regions of the (+) and (−) polarity strands of HCV RNA, as well as several shorter oligomers comprising defined stem-loop motifs of their predicted secondary structure models, were analyzed by Pb²⁺-induced cleavage, partial digestion with specific nucleases and chemical modification. Patterns characteristic of the motifs were compared with those obtained for the full-length molecules and on the basis of such ‘structural fingerprinting’ conclusions concerning folding of regions X were formulated. It turned out that the secondary structure model of X(+) RNA proposed earlier, the three-stem-loop model composed of hairpins SL1, SL2 and SL3, was only partially consistent with our experimental data. We confirmed the presence of SL1 and SL3 motifs and showed that the single-stranded stretch adjacent to the earlier proposed hairpin SL2 contributed to the folding of that region. It seemed to be arranged into two hairpins, which might form a hypothetical pseudoknot by changing their base-pairing systems. These data were discussed in terms of their possible biological significance. On the other hand, analysis of the X(−) RNA and its sub-fragments supported a three-stem-loop secondary structure model for this RNA.     

Molecular dynamics simulations of the folding of poly(alanine) peptides

The secondary structures and the shapes of long-chain polyalanine (PA) molecules were investigated by all-atom molecular dynamics simulations using a modified Amber force field. Homopolymers of polyaminoacids such as PA are convenient models to study the mechanism of protein folding. It was found that the conformational structures of PA peptides are highly sensitive to the chain length. In the absence of solvent, straight α-helices dominate in short (n ∼ 20) peptides at room temperature. A shape transition occurs at a chain length n of 40–45; the compact helix-turn-helix structure (the double-leg hairpin) becomes favored over a straight α-helix. For n = 60, double-leg and the triple-leg hairpins are the only structures present in PA molecules. An exploration of a chain organization in a cubic cavity revealed a clear predisposition of PA molecules for additional breaks in α-helices and the formation of multifolded hairpins. Furthermore, under confinement the hairpin structure becomes much looser, the antiparallel positions of helical stems are disturbed, and a sizeable proportion of the helical stems are transformed from α-helices into 3₁₀-helices.     

Determination of the secondary structure of group II bulge loops using the fluorescent probe 2-aminopurine

Eleven RNA hairpins containing 2-aminopurine (2-AP) in either base-paired or single nucleotide bulge loop positions were optically melted in 1 M NaCl; and, the thermodynamic parameters ΔH°, ΔS°, ΔG°₃₇, and T_M for each hairpin were determined. Substitution of 2-AP for an A (adenosine) at a bulge position (where either the 2-AP or A is the bulge) in the stem of a hairpin, does not affect the stability of the hairpin. For group II bulge loops such as AA/U, where there is ambiguity as to which of the A residues is paired with the U, hairpins with 2-AP substituted for either the 5′ or 3′ position in the hairpin stem have similar stability. Fluorescent melts were performed to monitor the environment of the 2-AP. When the 2-AP was located distal to the hairpin loop on either the 5′ or 3′ side of the hairpin stem, the change in fluorescent intensity upon heating was indicative of an unpaired nucleotide. A database of phylogenetically determined RNA secondary structures was examined to explore the presence of naturally occurring bulge loops embedded within a hairpin stem. The distribution of bulge loops is discussed and related to the stability of hairpin structures.     

Asymptotic Enumeration of RNA Structures with Pseudoknots

In this paper, we present the asymptotic enumeration of RNA structures with pseudoknots. We develop a general framework for the computation of exponential growth rate and the asymptotic expansion for the numbers of k-noncrossing RNA structures. Our results are based on the generating function for the number of k-noncrossing RNA pseudoknot structures, , derived in Bull. Math. Biol. (2008), where k−1 denotes the maximal size of sets of mutually intersecting bonds. We prove a functional equation for the generating function and obtain for k=2 and k=3, the analytic continuation and singular expansions, respectively. It is implicit in our results that for arbitrary k singular expansions exist and via transfer theorems of analytic combinatorics, we obtain asymptotic expression for the coefficients. We explicitly derive the asymptotic expressions for 2- and 3-noncrossing RNA structures. Our main result is the derivation of the formula .     

84 PPC measurements of unfolding volumes of DNA stem-loop motifs

One focus of our research is to further our understanding of the physico-chemical properties of non-canonical nucleic acid structures. In this work, DNA hairpins are used to mimic a common motif present in RNA, i.e. a stem-loop motif with a bulge or internal loop in their stem. Specifically, we used a combination of temperature-dependent UV spectroscopy, differential scanning (DSC), and pressure perturbation (PPC) calorimetric techniques to determine complete thermodynamic profiles for the helix–coil transitions of two sets of hairpins with 5′–3′ sequences: d(GCGCT _n GTAACT₅GTTACGCGC) and d(GCGCT _n GTAACT₅GTTACT _n GCGC). “T _n ” is a variable loop of thymines, n?=?1, 3 or 5; and “T₅” is an end-loop of five thymines. Unfolding curves show monophasic transitions with TMs independent of strand concentration, confirming their intramolecular formation. DSC thermodynamic profiles indicate that the favorable folding of each hairpin results from the typical compensation of favorable enthalpy and unfavorable entropy contributions, while the DSC curves as a function of salt concentration yielded an uptake of cations and negative heat capacity effects. PPC melting curves yielded positive folding volumes ranging 12–31?cm³/mol, corresponding to releases of water molecules; in contrast, an uptake of water (ranging from 32 to 63?mol of H₂O/mol) is observed from osmotic stress experiments using ethylene glycol as the osmolyte. Overall, the increase in the size of the variable bulge or internal-loop yielded lower TMs and slightly more favorable enthalpies, corresponding to less favorable free energy contributions of ～0.7?kcal/mol per thymine residue. The volume measurements will be correlated with the unfolding entropies and discussed in terms of the type of water that is hydrating these stem-loop motifs structures.     

The guanine-rich fragile X chromosome repeats are reluctant to form tetraplexes

Using circular dichroism spectroscopy, UV absorption spectroscopy and polyacrylamide gel electrophoresis, we studied conformational properties of guanine-rich DNA strands of the fragile X chromosome repeats d(GGC)_n, d(GCG)_n and d(CGG)_n, with n = 2, 4, 8 and 16. These strands are generally considered in the literature to form guanine tetraplexes responsible for the repeat expansion. However, we show in this paper that the repeats are reluctant to form tetraplexes. At physiological concentrations of either Na⁺ or K⁺ ions, the hexamers and dodecamers associate to form homoduplexes and the longer repeats generate homoduplexes and hairpins. The tetraplexes are rarely observed being relatively most stable with d(GGC)_n and least stable with d(GCG)_n. The tetraplexes are exclusively formed in the presence of K⁺ ions, at salt concentrations higher than physiological, more easily at higher than physiological temperatures, and they arise with extremely long kinetics (even days). Moreover, the capability to form tetraplexes sharply diminishes with the oligonucleotide length. These facts make the concept of the tetraplex appearance in this motif in vivo very improbable. Rather, a hairpin of the fragile X repeats, whose stability increases with the repeat length, is the probable structure responsible for the repeat expansion in genomes.     

Comparative analysis of RNA/protein dynamics for the arginine-rich-binding motif and zinc-finger-binding motif proteins encoded by HIV-1

We report a comparative study in which a single-molecule fluorescence resonance energy transfer approach was used to examine how the binding of two families of HIV-1 viral proteins to viral RNA hairpins locally changes the RNA secondary structures. The single-molecule fluorescence resonance energy transfer results indicate that the zinc finger protein (nucleocapsid) locally melts the TAR RNA and RRE-IIB RNA hairpins, whereas arginine-rich motif proteins (Tat and Rev) may strengthen the hairpin structures through specific binding interactions. Competition experiments show that Tat and Rev can effectively inhibit the nucleocapsid-chaperoned annealing of complementary DNA oligonucleotides to the TAR and RRE-IIB RNA hairpins, respectively. The competition binding data presented here suggest that the specific nucleic acid binding interactions of Tat and Rev can effectively compete with the general nucleic acid binding/chaperone functions of the nucleocapsid protein, and thus may in principle help regulate critical events during the HIV life cycle.     

Conserved secondary structures in Aspergillus

Background

Recent evidence suggests that the number and variety of functional RNAs (ncRNAs as well as cis-acting RNA elements within mRNAs ) is much higher than previously thought; thus, the ability to computationally predict and analyze RNAs has taken on new importance. We have computationally studied the secondary structures in an alignment of six Aspergillus genomes. Little is known about the RNAs present in this set of fungi, and this diverse set of genomes has an optimal level of sequence conservation for observing the correlated evolution of base-pairs seen in RNAs.

Methodology/Principal Findings

We report the results of a whole-genome search for evolutionarily conserved secondary structures, as well as the results of clustering these predicted secondary structures by structural similarity. We find a total of 7450 predicted secondary structures, including a new predicted ∼60 bp long hairpin motif found primarily inside introns. We find no evidence for microRNAs. Different types of genomic regions are over-represented in different classes of predicted secondary structures. Exons contain the longest motifs (primarily long, branched hairpins), 5′ UTRs primarily contain groupings of short hairpins located near the start codon, and 3′ UTRs contain very little secondary structure compared to other regions. There is a large concentration of short hairpins just inside the boundaries of exons. The density of predicted intronic RNAs increases with the length of introns, and the density of predicted secondary structures within mRNA coding regions increases with the number of introns in a gene.

Conclusions/Sigificance

There are many conserved, high-confidence RNAs of unknown function in these Aspergillus genomes, as well as interesting spatial distributions of predicted secondary structures. This study increases our knowledge of secondary structure in these aspergillus organisms.     

Loopstructures in synthetic oligonucleotides. Hairpin stability and structure studied as a function of loop elongation

The formation of hairpin structures in the homologous, (partly) self-complementary DNA fragments d(ATCCTAT_nTAGGAT), n = 0–7, was studied by means of nuclear magnetic resonance, T-jump and ultra-violet techniques. It is shown that all compounds in the series may adopt hairpin-like conformations, albeit for n < 3 this only occurs to a significant amount at relatively low concentrations (∼ 10μM). For the present series of oligonucleotides, hairpin formation is accompanied by an apparent loop enthalpy significantly different from zero. The stability of the DNA hairpins turns out to be at its maximum for loop lengths of four or five residues, whereas earlier experiments (Tinocoet al., 1973) indicated that loop lengths of six to seven residues are most favourable for RNA hairpins. This is explained by considering the difference in geometry of A-RNA and B-DNA helices.