First check if your RNA sequences are described by existing covariance models (CMs) available in Rfam. You can do this using the Infernal package to search the Rfam database of CMs. For those RNA sequences which match an Rfam CM, you can then use that CM to search the sequence databases for additional matches.
For those that do not match an Rfam CM, you will want to build your own models. In order to do this you need to identify homologues for each sequence which you can use to produce an alignment from which a model can be built. In order to do this you will want to use a method which is RNA aware and uses a rigorous search method. For example from the FASTA suite, which has an RNA mode which adjusts the scoring accordingly:
- Smith and Waterman for local/local alignment (e.g. SSEARCH)
- Needleman–Wunsch for global/global alignment (e.g. GGSEARCH)
- Hybrid alignment for global/local alignment (e.g. GLSEARCH)
Your coverage requirements and the nature of the database being searched will determine the most suitable method to use for the sequence similarity search. Combining the best search method with appropriate selection of the database to search, for example the European Nucleotide Archive (ENA) provide a set of non-protein coding sequences (ftp://ftp.ebi.ac.uk/pub/databases/ena/non-coding/) derived from the annotations in EMBL-Bank that could be a good starting point your search. Will improve the sensitivity of your search.
Given the set of homologous sequences you need to produce a multiple sequence alignment (MSA) to generate a model from. To do this you will want to use an RNA aware MSA tool, for example R-COFFEE or Clustal Omega in order to produce an alignment which attempts to take into account the folding of the RNA molecules.
Given the alignment you can create a CM using Infernal or an HMM using HMMER, and use this to search the sequence database (cmsearch or hmmsearch) to find additional homologues in the database.