Non-coding RNAs (ncRNAs) are functional RNA molecules that do not code for proteins. Classic examples include ribosomal and transfer RNAs, but dramatic discoveries in the last few years have greatly expanded both the number of known ncRNAs and the breadth of their biological roles [1]. In short, ncRNAs are much more biologically significant than previously realized. The computational problems associated with discovery and characterization of ncRNAs are quite different from, and arguably more difficult than, comparable tasks for protein-coding genes [2]. A key element of this difference is the importance of secondary structure in most ncRNAs. RNA secondary structure prediction is a well-studied problem, and useful tools exist, but they are certainly not perfect. It is generally accepted that the best evidence for stable secondary structure in biologically relevant RNAs is to identify diverged examples exhibiting compensatory base-pair changes that would preserve putative structural elements. Unfortunately, such compensatory mutations interfere with the ability of standard sequence search and alignment tools (e.g., BLAST, ClustalW) to find and align homologs.