An Improved Heterogeneous Parallel Ant Colony System for RNA Secondary Structure Prediction

  • Nachuan Yang, Huibin Shi, Jingwen Hu

Abstract

Ribonucleic acid (RNA) molecules play an important part in biological and medical research. At present, experimental techniques for RNAs structure determination, such as X-ray crystallography is very expensive and inefficient. Computational technologies have been used to predict RNA secondary structure. A pure Ant colony algorithm is not efficient enough. This paper introduces an improved heterogeneous parallel ant colony system algorithm to predict RNA secondary structure (PACSRNA). A new heuristic information computation approach is applied to improve ant colony algorithm by combining stem length with the free energy together with a new pheromone release approach. The stem selection rules are developed to combine with the roulette wheel gamble method to speed up the convergence of the whole algorithm. Through dynamically controlling the number of stems generated in the search, this paper enlarges the search width and depth and makes the prediction closer to the real situation. The paper accelerates the space search with heterogenous parallel computing by separating computing tasks into the Open Computing Language platform (OpenCL) and CPU, which greatly increases the potential space search speed in each computation iteration based on Turner energy model. Test results show that this paper can achieve relatively high performance than ViennaRNA and RNAstructure.

Published
2019-07-28