Sha Shi, Xin-Li Zhang, Le Yang, Wei Du, Xian-Li Zhao and Yun-Jiang Wang*
Both dynamic programming algorithms (DPAs) and evolutionary algorithms (EAs) are popular strategies for RNA secondary structure prediction. However, compared to most state-of-the-art software based on DPAs, the performances of EAs are a bit far from satisfactory. Here, we introduce the idea of quantum computing to the prediction of RNA secondary structure yielding a new strategy for this task. The new strategy is achieved by applying a quantum-inspired genetic algorithm (QGA) to find all possible legal paired-bases with the constraint of minimum free energy. In our strategy, the sate of a stem pool with size N is encoded as a population of QGA, which is represented by N quantum bits but not classical bits. The updating of populations is accomplished by so called quantum crossover operations, quantum mutation operations and quantum rotation operations. The numerical results show that the performances of traditional EAs are significantly improved by using QGA in terms of not only prediction accuracy and sensitivity but also complexity. Moreover, for RNA sequences with middle-short length, QGA even improves that state-of-art software based on DPAs in terms of both prediction accuracy and sensitivity. Our work sheds an interesting light to the applications of quantum computing on RNA structure prediction.
RNA secondary structure, Prediction, quantum computing, genetic algorithm, quantum algorithms
Engineering Research Centre of Molecular and Neuro Imaging Ministry of Education, School of life Science and Technology, Xidian University, Xi’an , Xinxiang Medical University, Xinxiang, Henan , The First Affiliated Hospical of Xi’an Jiaotong University, Xi’an, The First Affiliated Hospical of Zhengzhou University, Zhengzhou, Northwestern Women and Children’s Hospital, Xi'an, State Key Laboratory of Integrated Services Networks, Xidian University, Xi’an