Bioinformatics Vol. 17 no. 2 2001
Pages 137-148
© 2001 Oxford University Press
Original Paper |
The massively parallel genetic algorithm for RNA folding: MIMD implementation and population variation
1 Image Processing Section, Laboratory of
Experimental and Computational Biology, Division of Basic Sciences,
National Cancer Institute, Frederick Cancer Research and
Development Center, National Institutes of Health, Bldg 469, Rm
150, Frederick, MD 21702, USA
2 Science Applications International
Corporation at Frederick, LECB, NCI-FCRDC, Frederick, MD 21702, USA
3 SGI Inc., 12200-G Plum Orchard Drive,
Silver Spring, MD 20904, USA
Received on June 13, 2000
; revised on October 11, 2000
; accepted on October 11, 2000
A massively parallel Genetic Algorithm (GA) has been applied to RNA sequence folding on three different computer architectures. The GA, an evolution-like algorithm that is applied to a large population of RNA structures based on a pool of helical stems derived from an RNA sequence, evolves this population in parallel. The algorithm was originally designed and developed for a 16384 processor SIMD (Single Instruction Multiple Data) MasPar MP-2. More recently it has been adapted to a 64 processor MIMD (Multiple Instruction Multiple Data) SGI ORIGIN 2000, and a 512 processor MIMD CRAY T3E. The MIMD version of the algorithm raises issues concerning RNA structure data-layout and processor communication. In addition, the effects of population variation on the predicted results are discussed. Also presented are the scaling properties of the algorithm from the perspective of the number of physical processors utilized and the number of virtual processors (RNA structures) operated upon.
Contact: bshapiro{at}ncifcrf.gov; jcwu{at}ncifcrf.gov; bengalid{at}ncifcrf.gov; mark.potts{at}ieee.org
* To whom correspondence should be addressed.
4 Current address: HPC Applications Inc., 10080 Old Frederick Road, Ellicott City, MD 21042, USA.
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  S. D. Linnstaedt, W. K. Kasprzak, B. A. Shapiro, and J. L. Casey The fraction of RNA that folds into the correct branched secondary structure determines hepatitis delta virus type 3 RNA editing levels RNA, June 1, 2009; 15(6): 1177 - 1187. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 R. Guo, W. Lin, J. Zhang, A. E. Simon, and D. B. Kushner Structural Plasticity and Rapid Evolution in a Viral RNA Revealed by In Vivo Genetic Selection J. Virol., January 15, 2009; 83(2): 927 - 939. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
J. C. McCormack, X. Yuan, Y. G. Yingling, W. Kasprzak, R. E. Zamora, B. A. Shapiro, and A. E. Simon Structural Domains within the 3' Untranslated Region of Turnip Crinkle Virus J. Virol., September 1, 2008; 82(17): 8706 - 8720. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 G. B. Fogel Computational intelligence approaches for pattern discovery in biological systems Brief Bioinform, July 1, 2008; 9(4): 307 - 316. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
J. Zhang, G. Zhang, R. Guo, B. A. Shapiro, and A. E. Simon A pseudoknot in a preactive form of a viral RNA is part of a structural switch activating minus-strand synthesis. J. Virol., September 1, 2006; 80(18): 9181 - 9191. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
S. D. Linnstaedt, W. K. Kasprzak, B. A. Shapiro, and J. L. Casey The role of a metastable RNA secondary structure in hepatitis delta virus genotype III RNA editing RNA, August 1, 2006; 12(8): 1521 - 1533. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 J. H. A. Nagel, C. Flamm, I. L. Hofacker, K. Franke, M. H. de Smit, P. Schuster, and C. W. A. Pleij Structural parameters affecting the kinetics of RNA hairpin formation Nucleic Acids Res., July 19, 2006; 34(12): 3568 - 3576. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 K. C. Wiese and A. Hendriks Comparison of P-RnaPredict and mfold--algorithms for RNA secondary structure prediction Bioinformatics, April 15, 2006; 22(8): 934 - 942. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
E. BINDEWALD and B. A. SHAPIRO RNA secondary structure prediction from sequence alignments using a network of k-nearest neighbor classifiers. RNA, March 1, 2006; 12(3): 342 - 352. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
M. A. TORTORICI, B. A. SHAPIRO, and J. T. PATTON A base-specific recognition signal in the 5' consensus sequence of rotavirus plus-strand RNAs promotes replication of the double-stranded RNA genome segments RNA, January 1, 2006; 12(1): 133 - 146. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
W. Kasprzak, E. Bindewald, and B. A. Shapiro Structural polymorphism of the HIV-1 leader region explored by computational methods Nucleic Acids Res., December 20, 2005; 33(22): 7151 - 7163. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
C.-H. Huang, C. L. Lu, and H.-T. Chiu A heuristic approach for detecting RNA H-type pseudoknots Bioinformatics, September 1, 2005; 21(17): 3501 - 3508. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
G. B. Fogel, V. W. Porto, D. G. Weekes, D. B. Fogel, R. H. Griffey, J. A. McNeil, E. Lesnik, D. J. Ecker, and R. Sampath Discovery of RNA structural elements using evolutionary computation Nucleic Acids Res., December 1, 2002; 30(23): 5310 - 5317. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 K.-H. Pan, C.-J. Lih, and S. N. Cohen Analysis of DNA microarrays using algorithms that employ rule-based expert knowledge PNAS, February 19, 2002; 99(4): 2118 - 2123. [Abstract] [Full Text] [PDF]
|
|