A memory-efficient dynamic programming algorithm for optimal alignment of a sequence to an RNA secondary structure

Background  

Covariance models (CMs) are probabilistic models of RNA secondary structure, analogous to profile hidden Markov models of linear sequence. The dynamic programming algorithm for aligning a CM to an RNA sequence of length N is O(N ³) in memory. This is only practical for small RNAs.     

Design,implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics

Background  

The general problem of RNA secondary structure prediction under the widely used thermodynamic model is known to be NP-complete when the structures considered include arbitrary pseudoknots. For restricted classes of pseudoknots, several polynomial time algorithms have been designed, where the O(n ⁶)time and O(n ⁴) space algorithm by Rivas and Eddy is currently the best available program.     

An Alternative to Ewald Sums. Part 3: Implementation and Results

Abstract

This paper describes the implementation of a method for computing the Coulombic interaction in a periodic system. If the basic cell contains n charges the CPU time required to compute all forces and the total energy is O(n·log n) in contrast to Ewald's method with O(n ³/²).     

Listing all sorting reversals in quadratic time

We describe an average-case O(n ²) algorithm to list all reversals on a signed permutation π that, when applied to π, produce a permutation that is closer to the identity. This algorithm is optimal in the sense that, the time it takes to write the list is Ω(n ²) in the worst case.     

Computational experience with a parallel algorithm for tetrangle inequality bound smoothing

Determining molecular structure from interatomic distances is an important and challenging problem. Given a molecule with n atoms, lower and upper bounds on interatomic distances can usually be obtained only for a small subset of the atom pairs, using NMR. Given the bounds so obtained on the distances between some of the atom pairs, it is often useful to compute tighter bounds on all the pairwise distances. This process is referred to as bound smoothing. The initial lower and upper bounds for the pairwise distances not measured are usually assumed to be 0 and ∞. One method for bound smoothing is to use the limits imposed by the triangle inequality. The distance bounds so obtained can often be tightened further by applying the tetrangle inequality—the limits imposed on the six pairwise distances among a set of four atoms (instead of three for the triangle inequalities). The tetrangle inequality is expressed by the Cayley—Menger determinants. For every quadruple of atoms, each pass of the tetrangle inequality bound smoothing procedure finds upper and lower limits on each of the six distances in the quadruple. Applying the tetrangle inequalities to each of the ( ₄ ⁿ ) quadruples requires O(n ⁴) time. Here, we propose a parallel algorithm for bound smoothing employing the tetrangle inequality. Each pass of our algorithm requires O(n ³ log n) time on a CREW PRAM (Concurrent Read Exclusive Write Parallel Random Access Machine) with processors. An implementation of this parallel algorithm on the Intel Paragon XP/S and its performance are also discussed.     

An efficient method for the prediction of deleterious multiple-point mutations in the secondary structure of RNAs using suboptimal folding solutions

Background  

RNAmute is an interactive Java application which, given an RNA sequence, calculates the secondary structure of all single point mutations and organizes them into categories according to their similarity to the predicted structure of the wild type. The secondary structure predictions are performed using the Vienna RNA package. A more efficient implementation of RNAmute is needed, however, to extend from the case of single point mutations to the general case of multiple point mutations, which may often be desired for computational predictions alongside mutagenesis experiments. But analyzing multiple point mutations, a process that requires traversing all possible mutations, becomes highly expensive since the running time is O(n ^m ) for a sequence of length n with m-point mutations. Using Vienna's RNAsubopt, we present a method that selects only those mutations, based on stability considerations, which are likely to be conformational rearranging. The approach is best examined using the dot plot representation for RNA secondary structure.     

Synthetic and mechanistic studies on ruthenium dicarbonyl complexes containing PhP(CH2CH2CH2PCy2)2 (Cyttp) ligand

A synthetic and mechanistic study is reported on ligand substitution and other reactions of six-coordinate ruthenium(II) carbonyl complexes containing tridentate PhP(CH₂CH₂CH₂PCy₂)₂ (Cyttp). Carbonylation of cis-mer-Ru(OSO₂CF₃)₂(CO)(Cyttp) (1) affords [cis-mer-Ru(OSO₂CF₃)(CO)₂(Cyttp)]O₃SCF₃ (2(O₃SCF₃)) and, on longer reaction times, [cis-mer-Ru(solvent)(CO)₂(Cyttp)](O₃SCF₃)₂ (solvent = acetone, THF, methanol). 2(O₃SCF₃) reacts with each of NaF, LiCl, LiBr, NaI, and LiHBEt₃ to yield [cis-mer-RuX(CO)₂(Cyttp)]⁺ (X = F (3), Cl (4), Br (5), I (6), H (7)), isolated as 3-7(BPh₄). These conversions proceed with high stereospecificity to afford only a single isomer of the product that is assigned a structure in which the Ph group of Cyttp points toward the CO trans to X (anti when X = F, Cl, Br, or I; syn when X = H). Treatment of 2(O₃SCF₃) with NaOMe and CO generates the methoxycarbonyl complex [cis-mer-Ru(CO₂Me)(CO)₂(Cyttp)]⁺ (8), whereas addition of excess n-BuLi to 2(O₃SCF₃) in THF under CO affords mer-Ru(CO)₂(Cyttp) (9). The two ¹³C isotopomers [cis-mer-Ru(OSO₂CF₃)(CO)(¹³CO)(Cyttp)]O₃SCF₃ (2′(O₃SCF₃): ¹³CO trans to P_C; 2″(O₃SCF₃): ¹³CO cis to all P donors) were synthesized by appropriate adaptations of known transformations and used in mechanistic studies of reactions with each of LiHBEt₃, NaOMe/CO, and n-BuLi. Whereas LiHBEt₃ reacts with 2′(O₃SCF₃) and 2″(O₃SCF₃) to replace triflate by hydride without any scrambling of the carbonyl ligands, the corresponding reactions of NaOMe-CO are more complex. The methoxide combines with the CO cis to triflate in 2, and the resultant methoxycarbonyl ligand ends up positioned trans to the incoming CO in 8. A mechanism is proposed for this transformation. Finally, treatment of either 2′(O₃SCF₃) or 2″(O₃SCF₃) with an excess of n-BuLi leads to the formation of the same two ruthenium(0) isomers of mer-Ru(CO)(¹³CO)(Cyttp). These products represent, to our knowledge, the first example of a syn-anti pair of isomers of a five-coordinate metal complex.     

Structures and excitation energies of ozone-water clusters O3(H2O)n (n = 1-4)

Hybrid density functional theory (DFT) and time-dependent DFT (TD-DFT) calculations have been carried out for ozone-water clusters O₃(H₂O)_n (n = 1-4) in order to obtain hydration effects on the absorption spectrum of ozone. The first water molecule in n = 1 is bound to the ozone molecule by an oxygen orientation form in which the oxygen atom of H₂O orients the central oxygen atom of O₃. In n = 2, the water dimer is bound to O₃ and then the cyclic structure is formed as the most stable structure. For n = 3 (or n = 4), the cyclic water trimer (or tetramer) is bound by a hydrogen bond to the ozone molecule. The TD-DFT calculations of O₃(H₂O)_n (n = 0-4) show that the first and second excitation energies of O₃ are blue-shifted by the interaction with the water clusters. The magnitude of the spectral shift is largest in n = 2, and the shifts of the excitation energies are +0.07 eV for S₁ and +0.13 eV for S₂ states. In addition to the spectral shifts (S₁ and S₂ states), it is suggested that a charge-transfer band is appeared as a low-lying excited state above the S₁ and S₂ states. The origin of the spectrum shifts was discussed on the basis of theoretical results.     

Regulation of purine biosynthetic genes expression in Salmonella typhimurium Ⅳ Oc mutation site of purG and its function analysis

Salmonella typhimurium 5 phosphoribosylformylglycinamide (FGAR) amidotransferase encoded bypurG gene catalyzes the conversion of FGAR to formylglycinamide ribonucleotide (FGAM) in the presence of glu- tamine and ATP for thede novo purine nucleotide biosynthesis.purG gene is negatively regulated by a repressor-operator system. The O⁺ purG and O^c purG were cloned respectivelyin vivo. Restriction enzymes analysis of preliminary clones pLBG-1 (O⁺) and pLBG-2 (O^c) were carried out. The hybrid plasmids pLB1933 (O⁺) and pLB1927 (O^c) containing 5′ control region ofpurG were constructed and the DNA sequences were determined respectively, DNA sequences data showed that O^c mutation ofpurG occurred at the 3rd position of 16 bp PUR box in the 5′ control region (G→A). Gel retardation experiment indicated that the repressor bound well with O⁺ PUR box, but not with O^c PUR box. The result strongly supported the idea that PUR box is the binding region of repressor protein and the 3rd position base G of PUR box is essential for the binding function with repressor protein. Project supported by the National Natural Science Foundation of China.     

The structural definition of adducts of stoichiometry AgX:dppf (1:1)(n), X = simple anion, dppf = bis(diphenylphosphino)ferrocene

Single crystal X-ray structural characterizations are recorded for an array of adducts of the form AgX:dppf (1:1)_(n), X = simple (pseudo-)halide or oxy-anion, ‘dppf’ = bis(diphenyl phosphino)ferrocene, for adducts X = Cl (new phase), Br, I, SCN, OCN, CN, NO₃ (new phase), O₂CCH₃, n = 2, the form being dimeric [(dppf-P,P′)Ag(μ-X)₂Ag(P,P′-dppf)], for X = I, SCN, [Ag(μ-X)₂(P-dppf-P′)₂Ag′]; for X = O₂CCF₃, n = ∞, the form is an extended polymer: ?Ag(O · CO · CF₃)(P-dppf-P′)Ag′(O?. A dichloromethane solvate phase of CuI:dppf (1:1)₂ (also centrosymmetric) is also recorded. Synthetic procedures for all adducts have been reported. All compounds have been characterized both in solution (¹H, ¹³C, ³¹P NMR, ESI MS) and in the solid state (IR). The topology of the structures in the solid state was found to depend on the nature of the counterion.     

Fast Kalman filtering on quasilinear dendritic trees

Optimal filtering of noisy voltage signals on dendritic trees is a key problem in computational cellular neuroscience. However, the state variable in this problem—the vector of voltages at every compartment—is very high-dimensional: realistic multicompartmental models often have on the order of N = 10⁴ compartments. Standard implementations of the Kalman filter require O(N ³) time and O(N ²) space, and are therefore impractical. Here we take advantage of three special features of the dendritic filtering problem to construct an efficient filter: (1) dendritic dynamics are governed by a cable equation on a tree, which may be solved using sparse matrix methods in O(N) time; and current methods for observing dendritic voltage (2) provide low SNR observations and (3) only image a relatively small number of compartments at a time. The idea is to approximate the Kalman equations in terms of a low-rank perturbation of the steady-state (zero-SNR) solution, which may be obtained in O(N) time using methods that exploit the sparse tree structure of dendritic dynamics. The resulting methods give a very good approximation to the exact Kalman solution, but only require O(N) time and space. We illustrate the method with applications to real and simulated dendritic branching structures, and describe how to extend the techniques to incorporate spatially subsampled, temporally filtered, and nonlinearly transformed observations.     

Specificity of Phage Display Selected Peptides for Modified Anticodon Stem and Loop Domains of tRNA

Protein recognition of RNA has been studied using Peptide Phage Display Libraries, but in the absence of RNA modifications. Peptides from two libraries, selected for binding the modified anticodon stem and loop (ASL) of human tRNA^Lys3 having 2-thiouridine (s²U₃₄) and pseudouridine (Ψ₃₉), bound the modified human ASL^Lys3(s²U₃₄;Ψ₃₉) preferentially and had significant homology with RNA binding proteins. Selected peptides were narrowed to a manageable number using a less sensitive, but inexpensive assay before conducting intensive characterization. The affinity and specificity of the best binding peptide (with an N-terminal fluorescein) were characterized by fluorescence spectrophotometry. The peptide exhibited the highest binding affinity for ASL^Lys3(s²U₃₄;Ψ₃₉), followed by the hypermodified ASL^Lys3 (mcm⁵s²U₃₄;ms²t⁶A₃₇) and the unmodified ASL^Lys3, but bound poorly to singly modified ASL^Lys3 constructs (Ψ₃₉, ms²t⁶A_37, s²U₃₄), ASL^Lys1,2 (t⁶A₃₇) and Escherichia coli ASL^Glu (s²U₃₄). Thus, RNA modifications are potentially important recognition elements for proteins and can be targets for selective recognition by peptides.     

Optimized ancestral state reconstruction using Sankoff parsimony

Background  

Parsimony methods are widely used in molecular evolution to estimate the most plausible phylogeny for a set of characters. Sankoff parsimony determines the minimum number of changes required in a given phylogeny when a cost is associated to transitions between character states. Although optimizations exist to reduce the computations in the number of taxa, the original algorithm takes time O(n ²) in the number of states, making it impractical for large values of n.     

Interactions of tropospheric CO2 and O3 enrichments and moisture variations on microbial biomass and respiration in soil

Soil microbial biomass C (C_mic) is a sensitive indicator of trends in organic matter dynamics in terrestrial ecosystems. This study was conducted to determine the effects of tropospheric CO₂ or O₃ enrichments and moisture variations on total soil organic C (C_org), mineralizable C fraction (C_Min), C_mic, maintenance respiratory (qCO₂) or C_mic death (qD) quotients, and their relationship with basal respiration (BR) rates and field respiration (FR) fluxes in wheat‐soybean agroecosystems. Wheat (Triticum aestivum L.) and soybean (Glycine max. L. Merr) plants were grown to maturity in 3‐m dia open‐top field chambers and exposed to charcoal‐filtered (CF) air at 350 μL CO₂ L^?1; CF air + 150 μL CO₂ L^?1; nonfiltered (NF) air + 35 nL O₃ L^?1; and NF air + 35 nL O₃ L^?1 + 150 μL CO₂ L^?1 at optimum (? 0.05 MPa) and restricted soil moisture (? 1.0 ± 0.05 MPa) regimes. The + 150 μL CO₂ L^?1 additions were 18 h d^?1 and the + 35 nL O₃ L^?1 treatments were 7 h d^?1 from April until late October. While C_org did not vary consistently, C_Min, C_mic and C_mic fractions increased in soils under tropospheric CO₂ enrichment (500 μL CO₂ L^?1) and decreased under high O₃ exposures (55 ± 6 nL O₃ L^?1 for wheat; 60 ± 5 nL O₃ L^?1 for soybean) compared to the CF treatments (25 ± 5 nL O₃ L^?1). The qCO₂ or qD quotients of C_mic were also significantly decreased in soils under high CO₂ but increased under high O₃ exposures compared to the CF control. The BR rates did not vary consistently but they were higher in well‐watered soils. The FR fluxes were lower under high O₃ exposures compared to soils under the CF control. An increase in C_mic or C_mic fractions and decrease in qCO₂ or qD observed under high CO₂ treatment suggest that these soils were acting as C sinks whereas, reductions in C_mic or C_mic fractions and increase in qCO₂ or qD in soils under elevated tropospheric O₃ exposures suggest the soils were serving as a source of CO₂.     

A partial digest approach to restriction site mapping

We present a new, practical algorithm to resolve the experimental data in restriction site analysis, which is a common technique for mapping DNA. Specifically, we assert that multiple digestions with a single restriction enzyme can provide sufficient information to identify the positions of the restriction sites with high probability. The motivation for the new approach comes from combinatorial results on the number of mutually homeometric sets in one dimension, where two sets ofn points are homeometric if the multiset ofn(n−1)/2 distances they determine are the same. Since experimental data contain errors, we propose algorithms for reconstructing sets from noisy interpoint distances, including the possibility of missing fragments. We analyse the performance of these algorithms under a reasonable probability distribution, establishing a relative error limit ofr=Θ(1/n ²) beyond which our technique becomes infeasible. Through simulations, we establish that our technique is robust enough to reconstruct data with relative errors of up to 7.0% in the measured fragment lengths for typical problems, which appears sufficient for certain biological applications.     

Na4‐αM2+α/2(P2O7)2 (2/3 ≤ α ≤ 7/8, M = Fe,Fe0.5Mn0.5, Mn): A Promising Sodium Ion Cathode for Na‐ion Batteries

A new polyanion‐based compound, Na_3.12M_2.44(P₂O₇)₂ (M = Fe, Fe_0.5Mn_0.5, Mn) is synthesized and examined as a cathode for Na ion batteries. Off‐stoichiometric synthesis induces the formation of a Na‐rich phase, Na_3.32Fe_2.34(P₂O₇)₂ ‐ a member of the solid solution series Na_4‐αFe_2+α/2(P₂O₇)₂ (2/3 ≤ α ≤ 7/8) ‐ which delivers a reversible capacity of about 85 mA h g^?1 at ca. 3 V vs. Na/Na⁺ and exhibits very stable cycle performance. Above all, it shows fast kinetics for Na ions, delivering an almost constant 72% reversible capacity at rates between C/10 and 10C without the necessity for nanosizing or carbon coating. We attribute this to the spacious channel size along the a‐axis, along with a single phase transformation upon de/sodiation.     

Synthetic, structural and spectroscopic studies of complexes derived from the copper(II) perchlorate/succinamic acid/N,N′-donor tertiary reaction systems

The use of succinamic acid (H₂sucm) in Cu(ClO₄)₂·6H₂O/N,N′-donor [2,2′-bipyridine (bpy), 1,10-phenanthroline (phen), 4,4′-dimethyl-2,2′-bipyridine (dmbpy), 4,4′-bipyridine (4,4′-bpy)] reaction mixtures yielded compounds [Cu₂(Hsucm)₃(bpy)₂](ClO₄)·0.5MeOH (1·0.5MeOH), [Cu₂(Hsucm)(OH)(H₂O)(bpy)](ClO₄)₂ (2), [Cu₄(Hsucm)₅(dmbpy)₄]_n(ClO₄)_3n·nH₂O ·0.53nMeOH (3·nH₂O·0.53nMeOH), [Cu₂(Hsucm)₂(dmbpy)₂(H₂O)₂](ClO₄)₂·2H₂O (4·2H₂O), [Cu₂(Hsucm)₂(phen)₂(H₂O)₂](ClO₄)₂·1.8MeOH (5·1.8MeOH), [Cu₂(Hsucm)₂(phen)₂(MeOH)₂](ClO₄)₂·MeOH (6·MeOH) and [Cu(Hsucm)₂(H₂O)(4,4′-bpy)]_n (7). The succinamate(−1) ligand exists in five different coordination modes in the structures of 1-7, i.e. the common syn, syn μ₂-κO:κO′ in 1-6, the μ₂-κ²O in 1, the μ₂-κ²O:κO′ in 1, the μ₃-κ²O:κ²O′ in 3, and the monodentate κO in 7. The primary amide group of Hsucm⁻ remains uncoordinated and participates in intra- and intermolecular hydrogen bonding interactions leading to interesting crystal structures. Characteristic IR bands of the complexes are discussed in terms of the known structures and the coordination modes of the Hsucm⁻ ligands. The thermal decomposition of representative complexes was monitored by TG/DTG and DTA measurements.