Recent Advances in RNA Secondary Structure Prediction with Pseudoknots

It has recently been recognized that pseudoknots of RNAs have important roles and not a small number of RNAs contain pseudoknots. Therefore, recent studies on RNA secondary structure prediction focus on pseudoknots. Several algorithms have been developed based on dynamic programming. Though optimality of a solution is guaranteed, these algorithms suffer from high time complexities. Thus, heuristic algorithms have also been developed, some of which are supposed to produce near optimal solutions in reasonable CPU time. Recently, another approach based on comparative modeling has been proposed. Several practical programs and web-based server programs are also developed based on the above-mentioned algorithms. The purpose of this review paper is to introduce the basic ideas in important algorithms for RNA secondary structure prediction with pseudoknots. This paper also tries to reveal relations among important algorithms.