Abstract
This paper investigates the problem of maximum stacking base pairs from RNA secondary structure prediction. The basic version of maximum stacking base pairs problem as: given an RNA sequence, to find a maximum number of base pairs where each base pair is involved in a stacking. Ieong et al. showed this problem to be NP-hard, where the candidate base pairs follow some biology principle and are given implicitly. In this paper, we study the version of this problem that the candidate base pairs are given explicitly as input, and present a new approximation algorithm for this problem by the local search method, improving the approximation factor from 5/2 to 7/3. The time complexity is within \(O(n^{14})\), since we adopt 1-substitution and special 2-substitutions in the local improvement steps.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Tinoco Jr., I., Bustamante, C.: How RNA folds. J. Mol. Biol. 293, 271–281 (1999)
Nussinov, R., Pieczenik, G., Griggs, J.R., Kleitman, D.J.: Algorithms for loop matchings. SIAM J. Appl. Math. 35(1), 68–82 (1978)
Nussinov, R., Jacobson, A.B.: Fast algorithm for predicting the secondary structure of single-stranded RNA. Proc. Natl. Acad. Sci. USA 77, 6309–6313 (1980)
Zuker, M., Stiegler, P.: Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information. Nucleic Acids Res. 9, 133–148 (1981)
Zuker, M., Sankoff, D.: RNA secondary structures and their prediction. Bull. Math. Biol. 46, 591–621 (1984)
Sankoff, D.: Simultaneous solution of the RNA folding, alignment and protosequence problems. SIAM J. Appl. Math. 45, 810–825 (1985)
Lyngsø, R.B., Zuker, M., Pedersen, C.N.S.: Fast evaluation of interval loops in RNA secondary structure prediction. Bioinformatics 15, 440–445 (1999)
Lyngsø, R.B., Pedersen, C.N.S.: RNA pseudoknot prediction in energy based models. J. Comput. Biol. 7(3/4), 409–428 (2000)
Akutsu, T.: Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots. Discrete Appl. Math. 104(1–3), 45–62 (2000)
Rivas, E., Eddy, S.R.: A dynamic programming algorithm for RNA structure prediction including pseudoknots. J. Mol. Biol. 285(5), 2053–2068 (1999)
Uemura, Y., Hasegawa, A., Kobayashi, S., Yokomori, T.: Tree adjoining grammars for RNA structure prediction. Theoret. Comput. Sci. 210(2), 277–303 (1999)
Tinoco Jr., I., Borer, P.N., Dengler, B., Levine, M.D., Uhlenbeck, O.C., Crothers, D.M., Gralla, J.: Improved estimation of secondary structure in ribonucleic acids. Nature New Biol. 246, 40–42 (1973)
Ieong, S., Kao, M.-Y., Lam, T.-W., Sung, W.-K., Yiu, S.-M.: Predicting RNA secondary structure with arbitrary pseudoknots by maximizing the number of stacking pairs. J. Comput. Biol. 10, 981–995 (2003)
Lyngsø, R.B.: Complexity of pseudoknot prediction in simple models. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 919–931. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-27836-8_77
Jiang, M.: Approximation algorithms for predicting RNA secondary structures with arbitrary pseudoknots. IEEE/ACM Trans. Comput. Biol. Bioinform. 7(2), 323–332 (2010)
Berman, P.: A \(d\)/2 approximation for maximum weight independent set in \(d\)-Claw Free Graphs. Nordic J. Comput. 7, 178–184 (2000)
Zhou, A., Jiang, H., Guo, J., Feng, H., Liu, N., Zhu, B.: Improved Approximation algorithm for the maximum base pair stackings problem in RNA secondary structures prediction. In: Cao, Y., Chen, J. (eds.) COCOON 2017. LNCS, vol. 10392, pp. 575–587. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-62389-4_48
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Zhou, A., Jiang, H., Guo, J., Zhu, D. (2017). A New Approximation Algorithm for the Maximum Stacking Base Pairs Problem from RNA Secondary Structures Prediction. In: Gao, X., Du, H., Han, M. (eds) Combinatorial Optimization and Applications. COCOA 2017. Lecture Notes in Computer Science(), vol 10627. Springer, Cham. https://doi.org/10.1007/978-3-319-71150-8_7
Download citation
DOI: https://doi.org/10.1007/978-3-319-71150-8_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-71149-2
Online ISBN: 978-3-319-71150-8
eBook Packages: Computer ScienceComputer Science (R0)