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

An efficient genetic algorithm for structural RNA pairwise alignment and its application to non-coding RNA discovery in yeast - Download this document for free, or read online. Document in PDF available to download.

BMC Bioinformatics

, 9:521

First Online: 05 December 2008Received: 02 September 2008Accepted: 05 December 2008


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

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

ConclusionThe present method gives an efficient tool complementary to sequence-alignment-based ncRNA finders.

Electronic supplementary materialThe online version of this article doi:10.1186-1471-2105-9-521 contains supplementary material, which is available to authorized users.

Download fulltext PDF

Author: Akito Taneda



Related documents