RNA Search Acceleration with Genetic Algorithm Generated Decision Trees

The computing time requirements for using covariance models to search for non-coding RNA genes in genomic data make direct use of these models for RNA search impractical for RNA families with long consensus sequences. A possible solution is to break family models into portions and apply these portions sequentially on a segment of database until either an acceptance or rejection can be obtained on the given database segment. As will be shown, the application order and accept/reject decisions can be rather complex. A decision tree framework with genetic algorithms used to find the family-specific decision trees is proposed in this work to handle these complex cases. Computational speed-ups for database search of more than a factor of 15 have been observed using these methods as presented in the experimental section of this work.