Alignment of possible secondary structures in multiple RNA sequences using simulated annealing

Abstract

Multiple sequence alignment has been a useful technique for identifying RNA secondary structures. In this paper, an algorithm for aligning multiple RNA sequences to identify possible secondary structure is presented. In this algorithm, dot matrices generated from intra-sequence comparisons are used to obtain possible common secondary structures. A hit probability for dot matrices is calculated and a score function based on this hit probability is defined. Simulated annealing is applied to optimize the score function. The solution set of multiple sequence alignment is introduced, and the effects on the solution set of increasing the number of alignment gaps and the alignment length are analyzed. Several additional strategies to reduce simulated annealing time are applied. A method is applied to reduce the computation time based on the solution set. Also, an optimized transition rule, double shuffle, which moves two positions in a sequence with each iteration, is applied to increase the rate of convergence. This algorithm was used to find possible common secondary structures in RNA sequences.