Abstract:
Motivation:
Non-coding RNAs (ncRNAs) -- functional RNA molecules not coding for
protein -- are grouped into hundreds of families of homologs. To
find new members of an ncRNA gene family in a large genome database,
Covariance Models (CMs) are a useful statistical tool, as they use
both sequence and RNA secondary structure information. Unfortunately,
CM searches are slow. Previously, we introduced "rigorous filters,"
which provably sacrifice none of CMs' accuracy, while often scanning
much faster. A rigorous filter, using a profile hidden Markov model
(HMM), is built based on the CM, and filters the genome database,
eliminating sequences that provably could not be annotated as
homologs. The CM is run only on the remainder. Some biologically
important ncRNA families could not be scanned efficiently with this
technique, largely due to the significance of conserved secondary
structure relative to primary sequence in identifying these families.
Current heuristic filters are also expected to perform poorly on such
families.
Results:
By augmenting profile HMMs with limited secondary structure
information, we obtain rigorous filters that accelerate CM searches
for virtually all known ncRNA families from the Rfam Database and tRNA
models in tRNAscan-SE. These filters scan an 8-gigabase database in
weeks instead of years, and uncover homologs missed by heuristic
techniques to speed CM searches.
Availability:
software in development; contact the authors.
Supplementary information:
http://bio.cs.washington.edu/supplements/zasha-ISMB-2004
(Additional technical details on the method; predicted homologs.)
Keywords:
non-coding RNA, covariance model, gene family, profile hidden Markov
model, rigorous filter.
Contact:
{zasha,ruzzo}@cs.washington.edu
E-mail: ruzzo /at/ cs /dot/ washington /dot/ edu