Title: Efficient non-coding RNA gene searches through classical and evolutionary methods

Authors: Scott F. Smith

Addresses: Electrical and Computer Engineering Department, Boise State University, Boise, ID 83725-2075, USA

Abstract: Successful non-coding RNA gene searching requires examination of long-range intramolecular base pairing possibilities. This results in search algorithms with extremely long run times such that large-scale use of the algorithms often becomes computationally infeasible. Methods for the efficient search of the solution space are examined. A review of the standard dynamic-programming covariance model search algorithm is given. An analysis of the statistically probable regions of the search space is undertaken and a method of limiting the traditional dynamic-programming algorithm to this region is shown. An alternative search method using a Genetic Algorithm (GA) which favours the probable region of the search space is also given.

Keywords: bioinformatics; covariance models; genetic algorithms; GAs; RNA database search; non-coding RNA gene searching; intramolecular base pairing; search space.

DOI: 10.1504/IJCIBSB.2009.024043

International Journal of Computational Intelligence in Bioinformatics and Systems Biology, 2009 Vol.1 No.1, pp.42 - 58

Published online: 24 Mar 2009 *