Prediction of RNA Secondary Structure Based on Optimization in the Space of Its Descriptors by the Simulated Annealing Algorithm

The proportion of genome coding proteins is only a small part of a whole genome (for example, about 5% in human's genome). Among other things the remaining part contains regulatory RNAs whose function depends on their three-dimensional structure. Secondary structure is the first level of RNA structure description (three-dimensional structure is approximated by secondary structure). Therefore the problem of determining the common secondary structure of isofunctional RNA sequences (i.e., a set having similar functionality) is an important and longstanding problem of bioinformatics. In this paper we present the program which builds the secondary structure model for a such set of non-homologous RNA sequences. Secondary structure is described by directed acyclic graph i.e. multitree. The problem of determining the model of secondary structure is reduced to the discrete optimization task in the space of structure multitrees. The optimizable function depends on the energy of the referenced sequences being folded into this structure. The optimization task is solved by simulated annealing algorithm. We developed the program for building a common secondary structure model of RNA and compared it with the existing solutions on the set of mobile group II introns.