zbMATH — the first resource for mathematics

Exploiting parallelization for RNA secondary structure prediction in cluster. (English) Zbl 1120.92300
Sunderam, Vaidy S. (ed.) et al., Computational science – ICCS 2005. 5th international conference, Atlanta, GA, USA, May 22-25, 2005. Proceedings, Part III. Berlin: Springer (ISBN 3-540-26044-7/pbk). Lecture Notes in Computer Science 3516, 979-982 (2005).
Summary: RNA structure prediction remains one of the most compelling, yet elusive areas of computational biology. Many computational methods have been proposed in an attempt to predict RNA secondary structures. A popular dynamic programming (DP) algorithm uses a stochastic context-free grammar to model RNA secondary structures, its time complexity is \(O(N^{4})\) and spatial complexity is \(O(N^{3})\). In this paper, a parallel algorithm, which is time-wise and space-wise optimal with respect to the usual sequential DP algorithm, can be implemented using \(O(N^{4}/P)\) time and \(O(N^{3}/P)\) space in cluster. High efficient utilization of processors and good load balancing are achieved through dynamic mapping of DP matrix to processors. As experiments shown, dynamic mapping algorithm has good speedup.
For the entire collection see [Zbl 1073.68010].

92-08 Computational methods for problems pertaining to biology
92C40 Biochemistry, molecular biology
Full Text: DOI