Optimization and Performance Analysis of a Massively Parallel Dynamic Programming Algorithm for Rna Secondary Structure Prediction

Abstract

An optimized and parallelized form of a dynamic pro gramming algorithm capable of generating optimal and suboptimal RNA secondary structures is pre sented. Implementation of this algorithm on a MasPar MP-2 with 16K processors is shown to perform ex tremely well for very large nucleic acid sequences such as HIV (AIDS) and Rhinovirus (common cold). These sequences are, respectively, 9,128 and 7,208 nu cleotides in length. By taking advantage of the parallel nature of MasPar and also optimizing the communica tion requirements the implementation essentially re duced the algorithm from order O(n³) to 0(n ²). This reduction in complexity enables us to fold large RNA sequences in reasonable amounts of time. This capa bility has proven to be a valuable tool in studying the molecular structure and biological function of mole cules this large.

Get full access to this article

View all access options for this article.

References

Blank, T. 1990. The MasPar MP-I architecture. In Proc. IEEE Compcon Spring 1990 IEEE.

Dayton, E. , Konings, D. , Powell, D. , Shapiro, B. , Butini, L. , Maizel, J.V., Jr. , and Dayton, A. 1992. Extensive sequence-specific information throughout the CAR/RRE, the target sequence of the human immunodeficiency virus Type 1 Rev protein. J. Virology 66(2):1139-1151.

Jaeger, J. , Turner, D. , and Zuker, M. 1989a. Improved predictions of secondary structures for RNA . Proc. Natl. Acad. Sci. USA, Biochemistry 86: 7706-7710.

Jaeger, J. , Turner, D. , and Zuker, M. 1989b. Predicting optimal and suboptimal secondary structure for RNA. Methods in Enzymology 183:281-306.

Le, S. , Chen,J. , Currey, K. , and Maizel, J. 1988. A program for predicting significant RNA secondary structures . Computer Applications in the Biological Sciences 4:153.

Lewis, T. , and El-Rewini, H. 1992. Introduction to Parallel Computing , first edition. Prentice Hall.

Malim, M. , Hauber, J. , Le, S.-Y. , Maizel, J.V., Jr. , and Cullen, B.R. 1989. The HIV-l rev trans-activator acts through a structured target sequence to activate nuclear export of un-spliced viral mRNA. Nature 338:254-257.

Sdsc 1992. Computational Science Advances. San Diego Supercomputer Center.

Shapiro, B. , Lipkin, L. , and Maizel, J. 1982. An interactive technique for the display of nucleic acid secondary structure. Nucleic Acids Research 10: 7041-7052.

10.

Shapiro, B. , Maizel, J. , Lipkin, L. , Currey, K. , and Whitney, C. 1984. Generating non-overlapping displays of nucleic acid secondary structure. Nucleic Acids Research 12: 75-88.

11.

Turner, D. , Sugimoto, N. , and Freier, S. 1988. RNA structure predictions. Ann. Rev. Biophys. Biophys. Chem. 17:167-192.

12.

Watson, J. , Hopkins, N. , Roberts, J. , Argetsinger Steitz, J. , and Weiner, A. 1987. Molecular Biology of the Gene, fourth edition. Benjamin/Cummings.

13.

Zuker, M. 1989. On finding all suboptimal foldings of an RNA molecule . Science 244:48-52.