We present a highly accurate method for identifying genes with conserved RNA secondary structure by searching multiple sequence alignments of a large set of candidate orthologs for correlated arrangements of reverse-complementary regions. This approach is growing increasingly feasible as the genomes of ever more organisms are sequenced. A program called MSARI implements this method and is significantly more accurate than existing methods in the context of automatically generated alignments, making it particularly applicable to high-throughput scans. In our tests, it discerned CLUSTALW-generated multiple sequence alignments of signal recognition particle or RNaseP orthologs from controls with 89.1% sensitivity at 97.5% specificity and with 74.4% sensitivity with no false positives in 494 controls. We used MSARI to conduct a comprehensive scan for secondary structure in mRNAs of coding genes, and we found many genes with known mRNA secondary structure and compelling evidence for secondary structure in other genes. MSARI uses a method for coping with sequence redundancy that is likely to have applications in a large set of other comparisonbased search methods. The program is available for download from http:͞͞theory.csail.mit.edu͞MSARi. he structure of RNA is to a large extent determined by cis base pairing (AU, GC, and GU). This base-pairing is referred to as secondary structure. A noncoding RNA (ncRNA) (1) gene expresses RNA that is never translated into protein but is nonetheless biologically significant. Examples of such genes are tRNAs and XIST, which in mammalian males suppresses expression of genes on the X chromosome (2-4). RNA secondary structure in mRNAs can also be biologically significant, controlling timing and localization of protein expression (5). Identifying such secondary structure will be crucial to a complete understanding of cellular biology (6). Most work on identifying RNA secondary structure has been in the context of searching for ncRNA genes. Some approaches to automated identification of ncRNA genes have focused on searching for a recognizable secondary structure associated with RNA transcripts serving a specific biological function. One example of this type of program is Eddy and coworkers' 8) , which searches for tRNAs. Others are Regalia et al.'s search for signal recognition particles (9) and Rhoades et al.'s search for microRNAs (10). Automatically identifying novel biologically significant RNA secondary structure has proven to be difficult. By itself, RNA secondary structure in stand-alone genes is not particularly amenable to computer-based recognition methods, as many RNA sequences seem to have thermodynamically plausible secondary structures of no biological relevance (11). Moreover, ncRNA genes cannot be discerned by using standard computational gene detection algorithms, which are targeted at genes that express proteins and rely heavily on locating stop codons and other protein-specific guides (12-17). Comparative methods provide a way to cut through the abundance of plausible, but irrelevant, structures: only secondary structure that is conserved across species is likely to be biologically significant. We are aware of two programs that search for secondary structure by comparing potentially orthologous sequences. The first is QRNA (1, 18) , which scans pairwise alignments of homologous DNA sequences from related genomes. It uses a statistical model that flags alignments exhibiting mutation patterns preserving base-pairing in a thermodynamically plausible RNA secondary structure. Since first submitting this article for publication, we have also learned of a program called DDBRNA (19), which tests for complementary mutations in three-sequence multiple sequence alignments (MSAs). A serious problem with both QRNA and DDBRNA is that they can only detect complementary mutations of orthologous base pairs that have been accurately aligned to each other (1, 19) . This makes them imperfect for large-scale genome scans, as standard alignment algorithms do not reliably align such base pairs. For a sufficiently large hand-curated MSA of known ncRNA orthologs at the right evolutionary distance from each other, in which many orthologous base pairs are aligned, covariation between the corresponding columns of the MSA can be used to discern it from controls such as those described in Results with nearly perfect accuracy. However, hand curation of MSAs cannot be part of any high-throughput genomic scan. A related problem to RNA secondary structure detection is fine-grained secondary-structure prediction. This is the problem of determining all of the base pairs in sequences known to have (21) use MSAs of known ncRNA orthologs for secondary-structure prediction, but not detection. In the context of pairs of sequences, Mathews and Turner's DYNALIGN (22) and Sankhoff's sequence͞structure alignment algorithm (23) can be used for structure prediction. Secondary-structure prediction requires sufficient sensitivity to predict almost all base pairs and can have relatively low specificity without degrading its usefulness. Detection of secondary structure in a full-genome scan requires much greater specificity, but can be useful with much-lower-per-base pair sensitivity. Large MSAs have long been used for manual prediction of ncRNA secondary structure and have also recently been used in automated structure prediction (20, (24) (25) (26) ), but we are not aware of any earlier attempt to use them in searches for novel RNA secondary structure. Here, we propose an ab initio RNA secondary-structure detection scheme using large MSAs that does not rely on knowledge from or training on particular RNA secondary structures. The statistical evidence for conservation of RNA secondary structure across many sequences is often so strong that simple, robust statistical models can be used to detect it. In particular, as well as being a far more accurate detection scheme than its predecessors, to our knowledge ours is currently the only one that copes with the inaccuracies typical to automatically generated alignments. Our approach is based on computing the statistical significance of short, contiguous potential secondarystructure base-paired regions that are conserved between candidate orthologs and allows for small variations between alignFreely available online through the PNAS open access option. Abbreviations: ncRNA, noncoding RNA; MSA, multiple sequence alignment.
REF identify conserved RNA regions based on sequence alignment by searching for correlated reverse-complementary regions.
msari: Multiple sequence alignments for statistical detection of RNA secondary structure
Proceedings of the National Academy of Sciences of the United States of America
Proceedings of the National Academy of Sciences of the United States of America
Biology Medicine