Abstract
We present a new method for predicting RNA secondary structure based on a genetic algorithm. The algorithm is designed to run on a massively parallel SIMD computer. Statistical analysis shows that the program performs well when compared to a dynamic programming algorithm used to solve the same problem. The program has also pointed out a long-standing simplification in the implementation of the original dynamic programming algorithm that sometimes causes it not to find the optimal secondary structure.
Similar content being viewed by others
References
Ackley, D.H. 1987.A Connectionist Machine for Genetic Hillclimbing. Kluwer Academic, Boston.
Davis, L., ed. 1991.Handbook of Genetic Algorithms. Van Nostrand Reinhold, New York.
Freier, S., Kierzek, R., Jaeger, J., Sugimoto, N., Caruthers, M., Neilson, T., and Turner, D. 1986. Improved free-energy parameters for predictions of RNA duplex stability.Proc. Nat. Acad. Sci. USA, 83: 9373–9377.
Goldberg, D.E. (1989a).Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Reading, Mass.
Goldberg, D.E. (1989b). Sizing populations in serial and parallel genetic algorithms. InProc., Third Internat. Conf. on Genetic Algorithms (J.D. Schaffer, ed.) (San Mateo, June 4–7), Morgan Kaufmann Pub., pp. 70–79.
Goldberg, D.E., and Deb, K. 1991. A comparative analysis of selection schemes used in genetic algorithms. InFoundations of Genetic Algorithms (G.J. Rawlins, ed.), Morgan Kaufmann Pub., San Mateo, Calif., pp. 69–93.
Holland, J.H. 1975.Adaptation in Natural and Artificial Systems. Univ. of Mich. Press, Ann Arbor, Mich.
Jaeger, J.A., Turner, D.H., and Zucker, M. 1989. Improved predictions of secondary structures for RNA.Proc., Nat. Acad. Sci. USA, Biochemistry, 86: 7706–7710.
Jaeger, J.A., Turner, D.H., and Zuker, M. 1990. Predicting optimal and suboptimal secondary structure for RNA.Methods in Enzymology, 183: 281–306.
MasPar. 1992.MasPar System Overview. MasPar Comp. Corp.
Spears, W.M., and De Jong, K.A. 1991. An analysis of multi-point crossover. InFoundations of Genetic Algorithms (G.J. Rawlins, ed.), Morgan Kaufmann Pub., San Mateo, Calif., pp. 301–315.
Syswerda, G. 1989. Uniform crossover in genetic algorithms. InProc., Third Internat. Conf. on Genetic Algorithms (J.D. Schaffer, ed.) (San Mateo, June 4–7), pp. 2–9.
ten Dam, E., Pleij, K., and Draper, D. 1992. Structural and functional aspects of RNA pseudoknots.Biochemistry, 31(47): 11665–11676.
Turner, D.H., Sugimoto, N., and Freier, S.M. 1988. RNA structure predictions.Ann. Rev. Biophys. Biophys. Chem. 17: 167–192.
Zuker, M. 1989. On finding all suboptimal foldings of an RNA molecule.Science, 244: 48–52.
Zuker, M., and Stiegler, P. 1981. Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information.Nucleic Acids Research, 9: 133–148.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Shapiro, B.A., Navetta, J. A massively parallel genetic algorithm for RNA secondary structure prediction. J Supercomput 8, 195–207 (1994). https://doi.org/10.1007/BF01204728
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01204728