An improved algorithm for nucleic acid secondary structure display

An improved algorithm for the display of nucleic acid secondarystructures is presented. It is particularly suitable for largesequence segments and it automatically generates an aestheticallypleasing display of the structure with very limited overlapof strands. Structural similarities in different structuresare conserved in the display thus greatly aiding structuralhomology comparisons. Using the algorithm, we illustrate theeffect of ribosome translocation on the secondary structureof a rat neuropeptide messenger RNA. Received on September 21, 1987; accepted on October 22, 1987     

An algorithm for the display of nucleic acid secondary structure.

A simple algorithm is presented for the graphic display of nucleic acid secondary structure. Examples of secondary structure displays are given for tRNA, 5S RNA and part of the 16S RNA. Due to its speed, this algorithm could easily be used in conjunction with secondary structure programs which calculate various alternate structures.     

Parsing nucleic acid pseudoknotted secondary structure: algorithm and applications.

Accurate prediction of pseudoknotted nucleic acid secondary structure is an important computational challenge. Prediction algorithms based on dynamic programming aim to find a structure with minimum free energy according to some thermodynamic ("sum of loop energies") model that is implicit in the recurrences of the algorithm. However, a clear definition of what exactly are the loops in pseudoknotted structures, and their associated energies, has been lacking. In this work, we present a complete classification of loops in pseudoknotted nucleic secondary structures, and describe the Rivas and Eddy and other energy models as sum-of-loops energy models. We give a linear time algorithm for parsing a pseudoknotted secondary structure into its component loops. We give two applications of our parsing algorithm. The first is a linear time algorithm to calculate the free energy of a pseudoknotted secondary structure. This is useful for heuristic prediction algorithms, which are widely used since (pseudoknotted) RNA secondary structure prediction is NP-hard. The second application is a linear time algorithm to test the generality of the dynamic programming algorithm of Akutsu for secondary structure prediction.Together with previous work, we use this algorithm to compare the generality of state-of-the-art algorithms on real biological structures.     

Ring-closing metathesis reactions in nucleic acid chemistry-cyclic dinucleotides for targeting secondary nucleic acid structures

Cyclic dinucleotides are synthesized using a ring-closing metathesis protocol and incorporated into oligonucleotides. A stabilization of a three-way junction is observed by an oligodeoxynucleotide containing a central 2'-C to 3'-phosphate connection.     

An algorithm for protein secondary structure prediction based on class prediction

An algorithm has been developed to improve the success rate in the prediction of the secondary structure of proteins by taking into account the predicted class of the proteins. This method has been called the 'double prediction method' and consists of a first prediction of the secondary structure from a new algorithm which uses parameters of the type described by Chou and Fasman, and the prediction of the class of the proteins from their amino acid composition. These two independent predictions allow one to optimize the parameters calculated over the secondary structure database to provide the final prediction of secondary structure. This method has been tested on 59 proteins in the database (i.e. 10,322 residues) and yields 72% success in class prediction, 61.3% of residues correctly predicted for three states (helix, sheet and coil) and a good agreement between observed and predicted contents in secondary structure.     

A secondary and tertiary structure editor for nucleic acids

A major difficulty in the evaluation of secondary and tertiarystructures of nucleic acids is the lack of convenient methodsfor their construction and representation. As a first step ina study of the symbolic representation of biopolymers, we reportthe development of a structure editor written in Pascal, permittingmodel construction on the screen of a personal computer. Theprogram calculates energies for helical regions, allows user-definedhelices and displays the secondary structure of a nucleic acidbased on a user-selected set of helices. Screen and printeroutputs can be in the form of a backbone or the letters of theprimary sequence. The molecule can then be displayed in a formatwhich simulates its three-dimensional structure. Using appropriateglasses, the molecule can be viewed on the screen in three dimensions.Other options include the manipulation of helices and single-strandedregions which results in changes in the spatial relationshipbetween different regions of the molecule. The editor requiresan IBM or compatible PC, 640 kbyte memory and a medium or highresolution graphics card. Received on September 19, 1987; accepted on November 15, 1987     

The biological significance of G-T/G-U mispairing in nucleic acid secondary structure

We have computed the expected distribution of the potential for hairpin-like secondary structures with small loops (3-20 bases) and uninterrupted stems and compared that to the distribution observed in the complete genomes of seven DNA viruses from animals, plants and bacteria, as well as a bacterial plasmid. The formation of G-T mismatches in the stems of these structures was allowed. Furthermore we have analyzed the distribution of the potential for such structures along the genetic maps of these genomes, specifically around the start sites of known genes. Our data reveal that the potential for mismatch containing structures with stem length exceeding eight base pairs is over-represented and non-randomly distributed, but to a much lesser degree than that for perfect structures of equal size. Moreover, the potential for both types of structures is preferentially located near functional start codons. From this we deduce that in general G-T/G-U containing nucleic acid secondary structures are biologically relevant, though possibly less significant than perfect ones.     

Isoelectric characteristics and the secondary structure of some nucleic acids

The isoelectric characteristics of some nucleic acid preparations from rat liver have been examined. 10S and 4S RNA species and SV-DNA were found to have isoelectric points of 5.2, 6.0-6.7, and 4.35 respectively. The molecular charge ratios (net negative charge/nucleotide) were calculated. Using SV-DNA as a standard, these isoelectric characteristics and charge ratios have been interpreted as indicating that the 10S and 4S RNAs have 35 and 56% of the molecules involved in secondary structure.     

A new algorithm for RNA secondary structure design

The function of many RNAs depends crucially on their structure. Therefore, the design of RNA molecules with specific structural properties has many potential applications, e.g. in the context of investigating the function of biological RNAs, of creating new ribozymes, or of designing artificial RNA nanostructures. Here, we present a new algorithm for solving the following RNA secondary structure design problem: given a secondary structure, find an RNA sequence (if any) that is predicted to fold to that structure. Unlike the (pseudoknot-free) secondary structure prediction problem, this problem appears to be hard computationally. Our new algorithm, "RNA Secondary Structure Designer (RNA-SSD)", is based on stochastic local search, a prominent general approach for solving hard combinatorial problems. A thorough empirical evaluation on computationally predicted structures of biological sequences and artificially generated RNA structures as well as on empirically modelled structures from the biological literature shows that RNA-SSD substantially out-performs the best known algorithm for this problem, RNAinverse from the Vienna RNA Package. In particular, the new algorithm is able to solve structures, consistently, for which RNAinverse is unable to find solutions. The RNA-SSD software is publically available under the name of RNA Designer at the RNASoft website (www.rnasoft.ca).     

RnaPredict--an evolutionary algorithm for RNA secondary structure prediction

This paper presents two in-depth studies on RnaPredict, an evolutionary algorithm for RNA secondary structure prediction. The first study is an analysis of the performance of two thermodynamic models, Individual Nearest Neighbor (INN) and Individual Nearest Neighbor Hydrogen Bond (INN-HB). The correlation between the free energy of predicted structures and the sensitivity is analyzed for 19 RNA sequences. Although some variance is shown, there is a clear trend between a lower free energy and an increase in true positive base pairs. With increasing sequence length, this correlation generally decreases. In the second experiment, the accuracy of the predicted structures for these 19 sequences are compared against the accuracy of the structures generated by the mfold dynamic programming algorithm (DPA) and also to known structures. RnaPredict is shown to outperform the minimum free energy structures produced by mfold and has comparable performance when compared to sub-optimal structures produced by mfold.     

An algorithm for the determination and quantification of components of nucleic acid mixtures based on single sequencing reactions

Background  

Determination and quantification of nucleic acid components in a mixture is usually accomplished by microarray approaches, where the mixtures are hybridized against specific probes. As an alternative, we propose here that a single sequencing reaction from a mixture of nucleic acids holds enough information to potentially distinguish the different components, provided it is known which components can occur in the mixture.     

Interactions of molecules with nucleic acids. I. An algorithm to generate nucleic acid structures with an application to the B-DNA structure and a counterclockwise helix.

An algorithm is developed that enables the routine determination of backbone conformations of nucleic acids. All atomic positions including hydrogen are specified in accord with experimental bond lengths and angles but with theoretically determined conformational angles. For two Watson-Crick base pairs at a separation of 3.38 Å, and perpendicular to a common helical axis, minimum energy configurations are found for all 10 combinations at helical angles of α ～ 36°–38°, corresponding to the B-DNA structure with C(2′)-endo sugar puckers. Backbone configurations exist only within the range 35.5° ? α ? 42°, which suggests the origin of the 10-fold helix. Calculated stacking energies for the B-DNA structure increases for each of the clustered groups of base pairs: G·C with G·C, G·C with A·T, and A·T with A·T, and they are in approximate agreement with experimental observations. The counter-clockwise helix is examined, and physically meaningful structures are found only when the helical axes of successive base pairs are disjointed.     

An algorithm for comparing multiple RNA secondary structures

A new distributed computational procedure is presented for rapidlydetermining the similarity of multiple conformations of RNAsecondary structures. A data abstraction scheme is utilizedto reduce the quantity of data that must be handled to determinethe degree of similarity among multiple structures. The methodhas been used to compare 200 structures with easy visualizationof both those structures and substructures that are similarand those that are vastly different. It has the capability ofprocessing many more conformations as a function of researchrequirements. The algorithm is described as well as some suggestionsfor future uses and extensions. Received on October 29, 1987; accepted on May 4, 1988     

Minimising the secondary structure of DNA targets by incorporation of a modified deoxynucleoside: implications for nucleic acid analysis by hybridisation

Some regions of nucleic acid targets are not accessible to heteroduplex formation with complementary oligonucleotide probes because they are involved in secondary structure through intramolecular Watson–Crick pairing. The secondary conformation of the target may be destabilised to assist its interaction with oligonucleotide probes. To achieve this, we modified a DNA target, which has self-complementary sequence able to form a hairpin loop, by replacing dC with N4-ethyldeoxycytidine (d^4EtC), which hybridises specifically with natural dG to give a G:^4EtC base pair with reduced stability compared to the natural G:C base pair. Substitution by d^4EtC greatly reduced formation of the target secondary structure. The lower level of secondary structure allowed hybridisation with complementary probes made with natural bases. We confirmed that hybridisation could be further enhanced by modifying the probes with intercalating groups which stabilise the duplex.     

A parallel algorithm for estimating the secondary structure in ribonucleic acids

A parallel algorithm for estimating the secondary structure of an RNA molecule is presented in this paper. The mathematical problem to compute an optimal folding based on free-energy minimization is mapped onto a graph planarization problem. In the planarization problem we want to maximize the number of edges in a plane with no two edges crossing each other. To solve a sequence of n bases, n(n — 1)/2 processing elements are used in our algorithm.