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

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 (≤ 50%). By comparing with the previous predictions, we found that > 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.The present method gives an efficient tool complementary to sequence-alignment-based ncRNA finders.The RNA worlds in both experimental and computational fields have recently grown rapidly, and non-coding RNAs (ncRNAs) have increased their importance in life sciences. One of the most important breakthrough from the experimental side is the high-throughput experiments which have unveiled the existence of many non-protein coding transcripts in various species [1,2]. While function-known ncRNAs, which often harbor family-specific conserved secondary structure, such as tRNAs and miRNAs have been intensively studied in detail, no functional annotation has been assig