Searching genomes for noncoding RNA using FastR

The discovery of novel noncoding RNAs has been among the most exciting recent developments in biology. It has been hypothesized that there is, in fact, an abundance of functional noncoding RNAs (ncRNAs) with various catalytic and regulatory functions. However, the inherent signal for ncRNA is weaker than the signal for protein coding genes, making these harder to identify. We consider the following problem: Given an RNA sequence with a known secondary structure, efficiently detect all structural homologs in a genomic database by computing the sequence and structure similarity to the query. Our approach, based on structural filters that eliminate a large portion of the database while retaining the true homologs, allows us to search a typical bacterial genome in minutes on a standard PC. The results are two orders of magnitude better than the currently available software for the problem. We applied FastR to the discovery of novel riboswitches, which are a class of RNA domains found in the untranslated regions. They are of interest because they regulate metabolite synthesis by directly binding metabolites. We searched all available eubacterial and archaeal genomes for riboswitches from purine, lysine, thiamin, and riboflavin subfamilies. Our results point to a number of novel candidates for each of these subfamilies and include genomes that were not known to contain riboswitches.

1 Introduction

Not all genes encode proteins. Noncoding RNAs (ncRNAs) form transcripts that are functional molecules by themselves. The involvement of ncRNA in translation (tRNA), splicing, and other cellular functions is well-known. As early as 1961, Jacob and Monod hypothesized complementary roles for the two classes of genes, proposing that "Structural genes encode proteins, and regulatory genes produce ncRNA" [16]. Until recently, however, most novel gene discovery was in the form of protein coding genes and discovery of ncRNA was limited to finding novel homologs of commonly occurring ncRNAs (such as tRNA and rRNA). In part, these discoveries were fuelled by advances in genomic and computational technologies as well as large scale genome sequencing projects leading up to publications of large Eukaryotic genomes [21], [38], [41]. The complete genomic sequence allowed us to refine the estimates of the number of human (coding) genes. Surprisingly, these current estimates (30, 000-40, 000 genes) comprise less than 2 percent of the genome, far lower than earlier estimates and only twice as many as in Drosophila. It is an intriguing question if these genes and their (alternatively spliced) protein products are sufficient to carry out complex cellular functions. Could it be that many cellular functions are carried out by as yet undiscovered ncRNA?