Subcubic Time Algorithms for RNA SecondaryStructure Prediction
Tatsuya Akutsu

takutsu@ims.u-tokyo.ac.jp
Human Genome Center, Institute of Medical Science, University of Tokyo
4-6-1 Shirokanedai, Minato-ku, Tokyo 108-8639, Japan

1 Introduction
A lot of studies have been done on RNA secondary structure prediction [6], which is a problem of,given an RNA sequence of length n, nding its correct secondary structure (an outerplanar graph likestructure). Usually, it is modeled as a free-energy minimization problem, for which simple DP (dynamic programming) algorithms have been proposed [6]. However, from a viewpoint of computationalcomplexity, there had been no improvement on global free-energy minimization for 20 years (although
there had been signi cant improvements on nding locally stabilizing substructures) [6].
In a basic and simplest version, global free-energy minimization of an RNA secondary structure isde ned as a problem of maximizing the number of complementary base pairs. This problem is denoted
by RNA0 in this article. Even for RNA0 , a simple O(n3 ) time DP algorithm had been the fastest
algorithm for 20 years. Recently, we have developed slightly improved algorithms for RNA0 : anO(n3 (log log n)1=2 =(log n)1=2 ) time exact algorithm and an O(n2:776) time approximation algorithm[1]. We brie y describe outline of the algorithms in this short article. Details of the algorithms andextensions to more practical versions of the problem will appear in Ref. [1].

2 Exact Algorithm
It is well known that RNA secondary structure prediction can be formalized as a problem of constructing an optimal parse tree for a stochastic context-free grammar (SCFG, in short) [2, 4]. For thisproblem and context-free recognition (i.e., deciding whether or not there exists a parse tree for a given
sequence), simple O(n3 ) time DP algorithms were well known. However, Valiant developed O(n2:376 )time algorithm for context-free recognition [5], by using fast matrix multiplication. Recently, we foundthat Valiant's algorithm can be modi ed for the construction of an optimal parse tree for SCFG byreplacing matrix multiplication with funny matrix multiplication. Using the current fastest algorithm
for funny matrix multiplication [3], we have:Theorem 1.

For RNA0 , an optimal RNA secondary structure can be computed in O(n3 (log log n)1=2 =)1=2 ) time.

(log n3 Approximation Algorithm
Although the above improvement is very slight and is not practical, it seems dicult to develop faster
algorithms. Thus, we developed an O(n2:776 ) time approximation algorithm which always outputs asecondary structure whose score (i.e., the number of base pairs) is at least 1 0  of the optimal, where > 0 is any xed constant.
This approximation algorithm is a combination of an exact algorithm Aexact and an approximation
algorithm Aapprox : Aexact is used when the optimal score is small (presizely, the optimal score is O(n )338where is a constant), otherwise Aapprox is used. Aexact is similar to the exact algorithm in Section 1and details are omitted here. Aapprox is obtained by modifying the original O(n3 ) time DP algorithm.
Let a1 : : : an be an input RNA sequence. Then, it is well known that the optimal score S (i; j ) for
subsequence ai : : : aj can be computed by the following simple DP procedure:

S (i; j ) = max(S (i + 1; j 0 1) + (ai ; aj );maxi<kj f S (i; k 0 1) + S (k; j ) g;

where we let S (i; j ) = 0 for all i  j , and (x; y) = 1 if (x; y ) is a base pair, otherwise (x; y ) = 0.
In Aapprox , we do not compute maxi<kj f S (i; k 0 1) + S (k; j ) g exactly. Instead, we computethe maximum of S (i; k 0 1) + S (k; j ) for O(n + n10 ) values of k's (see Fig. 1), where and(0 < ; < 1) are appropriate constants.
Making detailed analysis on Aexact and Aapprox , we can show the following:
Theorem 2. For RNA0 , an RNA secondary structure with the score at least 1 0  of the maximum
can be computed in O(n2:776 ) time, where  is any xed positive number.

(k - i)βii + nα

j - nαkjFigure 1: In Aapprox , maxk S (i; k 0 1) + S (k; j ) is computed not for all k, but for O(n + n10 ) valuesof k's, where such k's are represented by white circles in this gure.

References[1] Akutsu, T., Approximation and exact algorithms for RNA secondary structure prediction andrecognition of stochastic context-free languages, To appear in The 9th Int. Symp. Algorithms andComputation (ISAAC'98).
[2] Sakakibara, Y., Brown, M., Hughey, E., Mian, I.S., Sjlolander, K., Underwood, R.C. and Haussler,
D., Stochastic context-free grammars for tRNA modeling, Nucleic Acids Research, 22:5112{5120,1994.
[3] Takaoka, T., A new upper bound on the complexity of all pairs shortest path problem, Information
Processing Letters, 43:195{199, 1992.
[4] Uemura, Y., Hasegawa, A., Kobayashi, S. and Yokomori, T., Grammatically modeling and predicting RNA secondary structures, Proc. Genome Informatics Workshop VI, Universal Academy
Press, Tokyo, 67{76, 1995.
[5] Valiant, L.G., General context-free recognition in less than cubic time, Journal of Computer andSystem Sciences, 10:308{315, 1975.
[6] Waterman, M.S., Introduction to Computational Biology, Chapman & Hall, London, 1995.

339