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: : [email protected] or [email protected]. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

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 .

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.

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/.

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.

MOTIVATION: Repetitive DNA sequences are abundant in genomes and efficient mining of significant repeats is important as the first step of repetitive sequence research. Although many computational tools for the purpose, either automatic or visualization ones, have been developed, detection and analysis of approximate repeats are still non-trivial task. RESULTS: Auto Dot PLOT (Adplot), a dotplot-like repetitive pattern visualization program with a window filtering based on iid Bernoulli trials, is developed and applied to yeast chromosomes and human T cell receptor locus sequence. Typical examples found in yeast chromosomes 1 and 10 and a tandem repeat of periods longer than 10,000 bp in human T cell receptor locus are presented. A complex structure composed of both direct and palindromic repeats found in yeast chromosome 10 is also visualized as specific dot pattern. Computational time measured by a Pentium 3 PC for each yeast auto chromosome with a standard parameter setting is linearly scaled and below 10 s per one chromosome, indicating efficiency of the program. From the examples, it is shown that Adplot can visualize approximate local repeat structures and give us a diagnosis power for inferring a duplicational history of repeats. AVAILABILITY: Adplot can be obtained by an e-mail request.