Frequency of cytosine methylation in the adjacent regions of soybean retrotransposon SORE-1 depends on chromosomal location.

Mobilization of transposable elements (TEs) is suppressed by epigenetic mechanisms involving cytosine methylation. However, few studies have focused on clarifying relationships between epigenetic influences of TEs on the adjacent DNA regions and time after insertion of TEs into the genome and/or their chromosomal location. Here we addressed these issues using soybean retrotransposon SORE-1. We analyzed SORE-1, inserted in exon 1 of the GmphyA2 gene, one of the newest insertions in this family so far identified. Cytosine methylation was detected in this element but was barely present in the adjacent regions. These results were correlated, respectively, with the presence and absence of the production of short interfering RNAs. Cytosine methylation profiles of 74 SORE-1 elements in the Williams 82 reference genome indicated that methylation frequency in the adjacent regions of SORE-1 was profoundly higher in pericentromeric regions than in euchromatic chromosome arms and was only weakly correlated with the length of time after insertion into the genome. Notably, the higher level of methylation in the 5' adjacent regions of SORE-1 coincided with the presence of repetitive elements in pericentromeric regions. Together, these results suggest that epigenetic influence of SORE-1 on the adjacent regions is influenced by its location on the chromosome.

A Web Server for Designing Molecular Switches Composed of Two Interacting RNAs.

The programmability of RNA-RNA interactions through intermolecular base-pairing has been successfully exploited to design a variety of RNA devices that artificially regulate gene expression. An in silico design for interacting structured RNA sequences that satisfies multiple design criteria becomes a complex multi-objective problem. Although multi-objective optimization is a powerful technique that explores a vast solution space without empirical weights between design objectives, to date, no web service for multi-objective design of RNA switches that utilizes RNA-RNA interaction has been proposed. We developed a web server, which is based on a multi-objective design algorithm called MODENA, to design two interacting RNAs that form a complex in silico. By predicting the secondary structures with RactIP during the design process, we can design RNAs that form a joint secondary structure with an external pseudoknot. The energy barrier upon the complex formation is modeled by an interaction seed that is optimized in the design algorithm. We benchmarked the RNA switch design approaches (MODENA+RactIP and MODENA+RNAcofold) for the target structures based on natural RNA-RNA interactions. As a result, MODENA+RactIP showed high design performance for the benchmark datasets.

Effects of Host-Adaptive Mutations on Hop Stunt Viroid Pathogenicity and Small RNA Biogenesis.

Accidental transmission of hop stunt viroid (HSVd) from grapevine to hop has led to several epidemics of hop stunt disease with convergent evolution of HSVd-g(rape) into HSVd-h(op) containing five mutations. However, the biological function of these five mutations remains unknown. In this study, we compare the biological property of HSVd-g and HSVd-h by bioassay and analyze HSVd-specific small RNA (HSVd-sRNA) using high-throughput sequencing. The bioassay indicated an association of these five mutations with differences in infectivity, replication capacity, and pathogenicity between HSVd-g and HSVd-h, e.g., HSVd-g induced more severe symptoms than HSVd-h in cucumber. Site-directed mutagenesis of HSVd-g showed that the mutation at position 54 increased pathogenicity. HSVd-sRNA analysis of cucumber and hop plants infected with different HSVd variants showed that several sRNA species containing adaptive nucleotides were specifically down-regulated in plants infected with HSVd-h. Several HSVd-sRNAs containing adaptive mutations were predicted to target cucumber genes, but changes in the levels of these genes were not directly correlated with changes in symptom expression. Furthermore, expression levels of two other cucumber genes targeted by HSVd-RNAs, encoding ethylene-responsive transcription factor ERF011, and trihelix transcription factor GTL2, were altered by HSVd infection. The possible relationship between these two genes to HSVd pathogenicity is discussed.

COSMO: A dynamic programming algorithm for multicriteria codon optimization.

Codon optimization in protein-coding sequences (CDSs) is a widely used technique to promote the heterologous expression of target genes. In codon optimization, a combinatorial space of nucleotide sequences that code a given amino acid sequence and take into account user-prescribed forbidden sequence motifs is explored to optimize multiple criteria. Although evolutionary algorithms have been used to tackle such complex codon optimization problems, evolutionary codon optimization tools do not provide guarantees to find the optimal solutions for these multicriteria codon optimization problems. We have developed a novel multicriteria dynamic programming algorithm, COSMO. By using this algorithm, we can obtain all Pareto-optimal solutions for the multiple features of CDS, which include codon usage, codon context, and the number of hidden stop codons. User-prescribed forbidden sequence motifs are rigorously excluded from the Pareto-optimal solutions. To accelerate CDS design by COSMO, we introduced constraints that reduce the number of Pareto-optimal solutions to be processed in a branch-and-bound manner. We benchmarked COSMO for run-time and the number of generated solutions by adapting selected human genes to yeast codon usage frequencies, and found that the constraints effectively reduce the run-time. In addition to the benchmarking of COSMO, a multi-objective genetic algorithm (MOGA) for CDS design was also benchmarked for the same two aspects and their performances were compared. In this comparison, (i) MOGA identified significantly fewer Pareto-optimal solutions than COSMO, and (ii) the MOGA solutions did not achieve the same mean hypervolume values as those provided by COSMO. These results suggest that generating the whole set of the Pareto-optimal solutions of the codon optimization problems is a difficult task for MOGA.

Ant colony optimization for predicting RNA folding pathways.

RNA folding dynamics plays important roles in various functions of RNAs. To date, coarse-grained modeling has been successfully employed to simulate RNA folding dynamics on the energy landscape composed of secondary structures. In such a modeling, the energy barrier height between metastable structures is a key parameter that crucially affects the simulation results. Although a number of approaches ranging from the exact method to heuristic ones are available to predict the barrier heights, developing an efficient heuristic for this purpose is still an algorithmic challenge. We developed a novel RNA folding pathway prediction method, ACOfoldpath, based on Ant Colony Optimization (ACO). ACO is a widely used powerful combinatorial optimization algorithm inspired from the food-seeking behavior of ants. In ACOfoldpath, to accelerate the folding pathway prediction, we reduce the search space by utilizing originally devised structure generation rules. To evaluate the performance of the proposed method, we benchmarked ACOfoldpath on the known nineteen conformational RNA switches. As a result, ACOfoldpath successfully predicted folding pathways better than or comparable to the previous heuristics. The results of RNA folding dynamics simulations and pseudoknotted pathway predictions are also presented.

RNAi-Mediated Down-Regulation of Dicer-Like 2 and 4 Changes the Response of 'Moneymaker' Tomato to Potato Spindle Tuber Viroid Infection from Tolerance to Lethal Systemic Necrosis, Accompanied by Up-Regulation of miR398, 398a-3p and Production of Excessive Amount of Reactive Oxygen Species.

To examine the role of RNA silencing in plant defenses against viroids, a Dicer-like 2 and 4 (DCL2&4)-double knockdown transgenic tomato plant line, 72E, was created. The expression of endogenous SlDCL2s and SlDCL4 in line 72E decreased to about a half that of the empty cassette line, EC. When challenged with potato spindle tuber viroid (PSTVd), line 72E showed significantly higher levels of PSTVd accumulation early in the course of the infection and lethal systemic necrosis late in the infection. The size distribution of PSTVd-derived small RNAs was significantly different with the number of RNAs of 21 and 22 nucleotides (nt) in line 72E, at approximately 66.7% and 5% of those in line EC, respectively. Conversely, the numbers of 24 nt species increased by 1100%. Furthermore, expression of the stress-responsive microRNA species miR398 and miR398a-3p increased 770% and 868% in the PSTVd-infected line 72E compared with the PSTVd-infected EC. At the same time, the expression of cytosolic and chloroplast-localized Cu/Zn-superoxide dismutase 1 and 2 (SOD1 and SOD2) and the copper chaperon for SOD (CCS1) mRNAs, potential targets of miR398 or 398a-3p, decreased significantly in the PSTVd-infected line 72E leaves, showing necrosis. In concert with miR398 and 398a-3p, SODs control the detoxification of reactive oxygen species (ROS) generated in cells. Since high levels of ROS production were observed in PSTVd-infected line 72E plants, it is likely that the lack of full dicer-likes (DCL) activity in these plants made them unable to control excessive ROS production after PSTVd infection, as disruption in the ability of miR398 and miR398a-3p to regulate SODs resulted in the development of lethal systemic necrosis.

RNA inverse folding using Monte Carlo tree search.

BACKGROUND: Artificially synthesized RNA molecules provide important ways for creating a variety of novel functional molecules. State-of-the-art RNA inverse folding algorithms can design simple and short RNA sequences of specific GC content, that fold into the target RNA structure. However, their performance is not satisfactory in complicated cases. RESULT: We present a new inverse folding algorithm called MCTS-RNA, which uses Monte Carlo tree search (MCTS), a technique that has shown exceptional performance in Computer Go recently, to represent and discover the essential part of the sequence space. To obtain high accuracy, initial sequences generated by MCTS are further improved by a series of local updates. Our algorithm has an ability to control the GC content precisely and can deal with pseudoknot structures. Using common benchmark datasets for evaluation, MCTS-RNA showed a lot of promise as a standard method of RNA inverse folding. CONCLUSION: MCTS-RNA is available at https://github.com/tsudalab/MCTS-RNA .

Evolutionary design of multiple genes encoding the same protein.

MOTIVATION: Enhancing expression levels of a target protein is an important goal in synthetic biology. A widely used strategy is to integrate multiple copies of genes encoding a target protein into a host organism genome. Integrating highly similar sequences, however, can induce homologous recombination between them, resulting in the ultimate reduction of the number of integrated genes. RESULTS: We propose a method for designing multiple protein-coding sequences (i.e. CDSs) that are unlikely to induce homologous recombination, while encoding the same protein. The method, which is based on multi-objective genetic algorithm, is intended to design a set of CDSs whose nucleotide sequences are as different as possible and whose codon usage frequencies are as highly adapted as possible to the host organism. We show that our method not only successfully designs a set of intended CDSs, but also provides insight into the trade-off between nucleotide differences among gene copies and codon usage frequencies. AVAILABILITY AND IMPLEMENTATION: Our method, named Tandem Designer, is available as a web-based application at http://tandem.trahed.jp/tandem/ . CONTACT: : terai_goro@intec.co.jp or asai@k.u-tokyo.ac.jp. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Characterization of host-dependent mutations of apple fruit crinkle viroid replicating in newly identified experimental hosts suggests maintenance of stem-loop structures in the left-hand half of the molecule is important for replication.

Apple fruit crinkle viroid (AFCVd) is a tentative member of the genus Apscaviroid, family Pospiviroidae. AFCVd has a narrow host range and is known to infect apple, hop and persimmon as natural hosts. In this study, tomato, cucumber and wild hop have been identified as new experimental herbaceous hosts. Foliar symptoms were very mild or virtually undetectable, but fruits of infected tomato were small, cracked and distorted. These symptoms resemble those observed on some AFCVd-sensitive apple cultivars. After transfer to tomato, cucumber and wild hop, sequence changes were detected in a natural AFCVd isolate from hop, and major variants in tomato, cucumber and wild hop differed in 10, 8 or 2 nucleotides, respectively, from the predominant one in the inoculum. The major variants in tomato and cucumber were almost identical, and the one in wild hop was very similar to the one in cultivated hop. Detailed analyses of the host-dependent sequence changes that appear in a naturally occurring AFCVd isolate from hop after transfer to tomato using small RNA deep sequence data and infectivity studies with dimeric RNA transcripts followed by progeny analysis indicate that the major AFCVd variant in tomato emerged by selection of a minor variant present in the inoculum (i.e. hop) followed by one to two host-dependent de novo mutations. Comparison of the secondary structures of major variants in hop, tomato and persimmon after transfer to tomato suggested that maintenance of stem-loop structures in the left-hand half of the molecule is critical for infection.

Multi-objective optimization for RNA design with multiple target secondary structures.

BACKGROUND: RNAs are attractive molecules as the biological parts for synthetic biology. In particular, the ability of conformational changes, which can be encoded in designer RNAs, enables us to create multistable molecular switches that function in biological circuits. Although various algorithms for designing such RNA switches have been proposed, the previous algorithms optimize the RNA sequences against the weighted sum of objective functions, where empirical weights among objective functions are used. In addition, an RNA design algorithm for multiple pseudoknot targets is currently not available. RESULTS: We developed a novel computational tool for automatically designing RNA sequences which fold into multiple target secondary structures. Our algorithm designs RNA sequences based on multi-objective genetic algorithm, by which we can explore the RNA sequences having good objective function values without empirical weight parameters among the objective functions. Our algorithm has great flexibility by virtue of this weight-free nature. We benchmarked our multi-target RNA design algorithm with the datasets of two, three, and four target structures and found that our algorithm shows better or comparable design performances compared with the previous algorithms, RNAdesign and Frnakenstein. In addition to the benchmarks with pseudoknot-free datasets, we benchmarked MODENA with two-target pseudoknot datasets and found that MODENA can design the RNAs which have the target pseudoknotted secondary structures whose free energies are close to the lowest free energy. Moreover, we applied our algorithm to a ribozyme-based ON-switch which takes a ribozyme-inactive secondary structure when the theophylline aptamer structure is assumed. CONCLUSIONS: Currently, MODENA is the only RNA design software which can be applied to multiple pseudoknot targets. Successful design results for the multiple targets and an RNA device indicate usefulness of our multi-objective RNA design algorithm.

Deep sequencing uncovers commonality in small RNA profiles between transgene-induced and naturally occurring RNA silencing of chalcone synthase-A gene in petunia.

BACKGROUND: Introduction of a transgene that transcribes RNA homologous to an endogenous gene in the plant genome can induce silencing of both genes, a phenomenon termed cosuppression. Cosuppression was first discovered in transgenic petunia plants transformed with the CHS-A gene encoding chalcone synthase, in which nonpigmented sectors in flowers or completely white flowers are produced. Some of the flower-color patterns observed in transgenic petunias having CHS-A cosuppression resemble those in existing nontransgenic varieties. Although the mechanism by which white sectors are generated in nontransgenic petunia is known to be due to RNA silencing of the CHS-A gene as in cosuppression, whether the same trigger(s) and/or pattern of RNA degradation are involved in these phenomena has not been known. Here, we addressed this question using deep-sequencing and bioinformatic analyses of small RNAs. RESULTS: We analyzed short interfering RNAs (siRNAs) produced in nonpigmented sectors of petal tissues in transgenic petunia plants that have CHS-A cosuppression and a nontransgenic petunia variety Red Star, that has naturally occurring CHS-A RNA silencing. In both silencing systems, 21-nt and 22-nt siRNAs were the most and the second-most abundant size classes, respectively. CHS-A siRNA production was confined to exon 2, indicating that RNA degradation through the RNA silencing pathway occurred in this exon. Common siRNAs were detected in cosuppression and naturally occurring RNA silencing, and their ranks based on the number of siRNAs in these plants were correlated with each other. Noticeably, highly abundant siRNAs were common in these systems. Phased siRNAs were detected in multiple phases at multiple sites, and some of the ends of the regions that produced phased siRNAs were conserved. CONCLUSIONS: The features of siRNA production found to be common to cosuppression and naturally occurring silencing of the CHS-A gene indicate mechanistic similarities between these silencing systems especially in the biosynthetic processes of siRNAs including cleavage of CHS-A transcripts and subsequent production of secondary siRNAs in exon 2. The data also suggest that these events occurred at multiple sites, which can be a feature of these silencing phenomena.

Multi-objective genetic algorithm for pseudoknotted RNA sequence design.

RNA inverse folding is a computational technology for designing RNA sequences which fold into a user-specified secondary structure. Although pseudoknots are functionally important motifs in RNA structures, less reports concerning the inverse folding of pseudoknotted RNAs have been done compared to those for pseudoknot-free RNA design. In this paper, we present a new version of our multi-objective genetic algorithm (MOGA), MODENA, which we have previously proposed for pseudoknot-free RNA inverse folding. In the new version of MODENA, (i) a new crossover operator is implemented and (ii) pseudoknot prediction methods, IPknot and HotKnots, are used to evaluate the designed RNA sequences, allowing us to perform the inverse folding of pseudoknotted RNAs. The new version of MODENA with the new crossover operator was benchmarked with a dataset composed of natural pseudoknotted RNA secondary structures, and we found that MODENA can successfully design more pseudoknotted RNAs compared to the other pseudoknot design algorithm. In addition, a sequence constraint function newly implemented in the new version of MODENA was tested by designing RNA sequences which fold into the pseudoknotted structure of a hepatitis delta virus ribozyme; as a result, we successfully designed eight RNA sequences. The new version of MODENA is downloadable from http://rna.eit.hirosaki-u.ac.jp/modena/.

Coincident sequence-specific RNA degradation of linked transgenes in the plant genome.

The expression of transgenes in plant genomes can be inhibited by either transcriptional gene silencing or posttranscriptional gene silencing (PTGS). Overexpression of the chalcone synthase-A (CHS-A) transgene triggers PTGS of CHS-A and thus results in loss of flower pigmentation in petunia. We previously demonstrated that epigenetic inactivation of CHS-A transgene transcription leads to a reversion of the PTGS phenotype. Although neomycin phosphotransferase II (nptII), a marker gene co-introduced into the genome with the CHS-A transgene, is not normally silenced in petunia, even when CHS-A is silenced, here we found that nptII was silenced in a petunia line in which CHS-A PTGS was induced, but not in the revertant plants that had no PTGS of CHS-A. Transcriptional activity, accumulation of short interfering RNAs, and restoration of mRNA level after infection with viruses that had suppressor proteins of gene silencing indicated that the mechanism for nptII silencing was posttranscriptional. Read-through transcripts of the CHS-A gene toward the nptII gene were detected. Deep-sequencing analysis revealed a striking difference between the predominant size class of small RNAs produced from the read-through transcripts (22 nt) and that from the CHS-A RNAs (21 nt). These results implicate the involvement of read-through transcription and distinct phases of RNA degradation in the coincident PTGS of linked transgenes and provide new insights into the destabilization of transgene expression.

MODENA: a multi-objective RNA inverse folding.

Artificially synthesized RNA molecules have recently come under study since such molecules have a potential for creating a variety of novel functional molecules. When designing artificial RNA sequences, secondary structure should be taken into account since functions of noncoding RNAs strongly depend on their structure. RNA inverse folding is a methodology for computationally exploring the RNA sequences folding into a user-given target structure. In the present study, we developed a multi-objective genetic algorithm, MODENA (Multi-Objective DEsign of Nucleic Acids), for RNA inverse folding. MODENA explores the approximate set of weak Pareto optimal solutions in the objective function space of 2 objective functions, a structure stability score and structure similarity score. MODENA can simultaneously design multiple different RNA sequences at 1 run, whose lowest free energies range from a very stable value to a higher value near those of natural counterparts. MODENA and previous RNA inverse folding programs were benchmarked with 29 target structures taken from the Rfam database, and we found that MODENA can successfully design 23 RNA sequences folding into the target structures; this result is better than those of the other benchmarked RNA inverse folding programs. The multi-objective genetic algorithm gives a useful framework for a functional biomolecular design. Executable files of MODENA can be obtained at http://rna.eit.hirosaki-u.ac.jp/modena/.

Accumulation of Potato spindle tuber viroid-specific small RNAs is accompanied by specific changes in gene expression in two tomato cultivars.

To better understand the biogenesis of viroid-specific small RNAs and their possible role in disease induction, we have examined the accumulation of these small RNAs in potato spindle tuber viroid (PSTVd)-infected tomato plants. Large-scale sequence analysis of viroid-specific small RNAs revealed active production from the upper portion of the pathogenicity and central domains, two regions previously thought to be underrepresented. Profiles of small RNA populations derived from PSTVd antigenomic RNA were more variable, with differences between infected Rutgers (severe symptoms) and Moneymaker (mild symptoms) plants pointing to possible cultivar-specific differences in small RNA synthesis and/or stability. Using microarray analysis, we monitored the effects of PSTVd infection on the expression levels of >100 tomato genes containing potential binding sites for PSTVd small RNAs. Of 18 such genes down-regulated early in infection, two genes involved in gibberellin or jasmonic acid biosynthesis contain binding sites for PSTVd small RNAs in their respective ORFs.

Multi-objective pairwise RNA sequence alignment.

MOTIVATION: With an increase in the number of known biological functions of non-coding RNAs, the importance of RNA sequence alignment has risen. RNA sequence alignment problem has been investigated by many researchers as a mono-objective optimization problem where contributions from sequence similarity and secondary structure are taken into account through a single objective function. Since there is a trade-off between these two objective functions, usually we cannot obtain a single solution that has both the best sequence similarity score and the best structure score simultaneously. Multi-objective optimization is a widely used framework for the optimization problems with conflicting objective functions. So far, no one has examined how good alignments we can obtain by applying multi-objective optimization to structural RNA sequence alignment problem. RESULTS: We developed a pairwise RNA sequence alignment program, Cofolga2mo, based on multi-objective genetic algorithm (MOGA). We tested Cofolga2mo with a benchmark dataset which includes sequence pairs with a wide range of sequence identity, and we obtained at most 100 alignments for each inputted RNA sequence pair as an approximate set of weak Pareto optimal solutions. We found that the alignments in the approximate set give benchmark results comparable to those obtained by the state-of-the-art mono-objective RNA alignment algorithms. Moreover, we found that our algorithm is efficient in both time and memory usage compared to the other methods. AVAILABILITY: Our MOGA programs for structural RNA sequence alignment can be downloaded at http://rna.eit.hirosaki-u.ac.jp/cofolga2mo/.

A small nucleolar RNA functions in rRNA processing in Caenorhabditis elegans.

CeR-2 RNA is one of the newly identified Caenorhabditis elegans noncoding RNAs (ncRNAs). The characterization of CeR-2 by RNomic studies has failed to classify it into any known ncRNA family. In this study, we examined the spatiotemporal expression patterns of CeR-2 to gain insight into its function. CeR-2 is expressed in most cells from the early embryo to adult stages. The subcellular localization of this RNA is analogous to that of fibrillarin, a major protein of the nucleolus. It was observed that knockdown of C/D small nucleolar ribonucleoproteins (snoRNPs), but not of H/ACA snoRNPs, resulted in the aberrant nucleolar localization of CeR-2 RNA. A mutant worm with a reduced amount of cellular CeR-2 RNA showed changes in its pre-rRNA processing pattern compared with that of the wild-type strain N2. These results suggest that CeR-2 RNA is a C/D snoRNA involved in the processing of rRNAs.

An efficient genetic algorithm for structural RNA pairwise alignment and its application to non-coding RNA discovery in yeast.

BACKGROUND: Aligning RNA sequences with low sequence identity has been a challenging problem since such a computation essentially needs an algorithm with high complexities for taking structural conservation into account. Although many sophisticated algorithms for the purpose have been proposed to date, further improvement in efficiency is necessary to accelerate its large-scale applications including non-coding RNA (ncRNA) discovery. RESULTS: We developed a new genetic algorithm, Cofolga2, for simultaneously computing pairwise RNA sequence alignment and consensus folding, and benchmarked it using BRAliBase 2.1. The benchmark results showed that our new algorithm is accurate and efficient in both time and memory usage. Then, combining with the originally trained SVM, we applied the new algorithm to novel ncRNA discovery where we compared S. cerevisiae genome with six related genomes in a pairwise manner. By focusing our search to the relatively short regions (50 bp to 2,000 bp) sandwiched by conserved sequences, we successfully predict 714 intergenic and 1,311 sense or antisense ncRNA candidates, which were found in the pairwise alignments with stable consensus secondary structure and low sequence identity ( 92% of the candidates is novel candidates. The estimated rate of false positives in the predicted candidates is 51%. Twenty-five percent of the intergenic candidates has supports for expression in cell, i.e. their genomic positions overlap those of the experimentally determined transcripts in literature. By manual inspection of the results, moreover, we obtained four multiple alignments with low sequence identity which reveal consensus structures shared by three species/sequences. CONCLUSION: The present method gives an efficient tool complementary to sequence-alignment-based ncRNA finders.

Twelve novel C. elegans RNA candidates isolated by two-dimensional polyacrylamide gel electrophoresis.

C. elegans small RNAs (<50 nt) were separated by two-dimensional gel electrophoresis (2D-PAGE). cDNAs were prepared from the RNAs extracted from randomly chosen 2D-PAGE spots. Although many cDNA sequences corresponded to parts of known RNAs, twelve novel small RNA candidates were identified: eleven from 2D-PAGE spots of the mixed-stage worm RNA preparation and one from those of the embryonic RNA preparation. These are encoded in the intergenic regions, in the introns of protein-coding genes, in the anti-sense strand of protein-coding sequences and repetitive sequence regions of the genome. None of them showed a characteristic structure of miRNAs, suggesting that they are candidates of other or new classes of RNAs.

Cofolga: a genetic algorithm for finding the common folding of two RNAs.

In order to predict non-coding RNA genes and functions on the basis of genome sequences, accurate secondary structure prediction is useful. Although single-sequence folding programs such as mfold have been successful, it is of great importance to develop a novel approach for further improvement of the prediction performance. In the present paper, a secondary structure prediction method based on genetic algorithm, Cofolga, is proposed. The program developed performs folding and alignment of two homologous RNAs simultaneously. Cofolga was tested with a dataset composed of 13 tRNAs, seven 5S rRNAs, five RNase P RNAs, and five SRP RNAs; as a result, it turned out that the average prediction accuracies for the tRNAs, 5S rRNAs, RNase P RNAs, and SRP RNAs obtained by Cofolga with an optimal weight factor and default parameters were 83.6, 81.8, 73.5, and 67.7%, respectively. These results were superior to those obtained by a single-sequence folding based on free-energy minimization in which corresponding average prediction accuracies were 52.4, 47.4, 57.7, and 52.3%, respectively. Cofolga has a post-processing in which a single-sequence folding is performed after fixation of a predicted common structure; this post-processing enables Cofolga to predict a structure that is present in one of two RNAs alone. The executable files of Cofolga (for Windows/Unix/Mac) can be obtained by an e-mail request.