Abstract

Bioinformatics is faced with accelerating increase of data set sizes originating from powerful high-throughput measuring devices. Extensive computational power is the basic requirement for solving problems in bioinformatics. One of the key solutions to time-efficient data processing is the proper implementation of computational intensive tasks using parallel technology. A large number of cores is combined into a single chip to improve the overall performance of the multi-core processors. This depicts the current trends in processor architecture. This paper proposes a new software-only speculative parallelization scheme for implementing RNA Secondary Structure Prediction algorithm in parallel. The scheme is developed after a systematic evaluation of the design options available. It is also shown to be efficient, robust and to outperform previously proposed schemes used for parallel implementation of RNA Secondary Structure Prediction.

References

• M. Andronescu, R. Aguirre-Hernandez, A. Condon, and H. H. Hoos, "RNAsoft: a suite of RNA secondary structure prediction and design software tools. " Nucleic Acids Research,31(13):3416–3422, 2003.
• A. Bhowmik, M. Franklin , " A general compiler framework for speculative multithreading. " In: SPAA,pp. 99–108 , 2002.
• K. J. Doshi, J. J. Cannone, C. W. Cobaugh, and R. R. Gutell, "Evaluation of the suitability of free-energy minimization using nearest-neighbor energy parameters for RNA secondary structure prediction. ", BMC Bioinformatics, 2004
• S. R. Eddy, "Computational analysis of conserved RNA secondary structure in transcriptomes and genomes", Technical Report, HHMI Janelia Farm Research Campus, 2013.
• M. Fekete, I. L. Hofacker, and P. F. Stadler, "Prediction of RNA base pairing probabilities on massively parallel computers. ", J. Computational Biology, 7(1-2):171–182, 2000.
• P. P. Gardner and R. Giegerich," A comprehensive comparison of comparative RNA structure prediction approaches. ", BMC Bioinformatics, 5(140), 2004.
• J. Gregory Steffan, , C. B. Colohan, , A. Zhai, T. C. Mowry, " A scalable approach to thread-level speculation. ", In: ISCA, pp. 1–12 , 2000.
• I. L. Hofacker, P. F. Stadler, L. S. Bonhoeffer, M. Tacker, and P. Schuster, "Fast folding and comparison of RNA secondary structures. ", Monatshefte f¨ur Chemie, 125:167–188, 1994.
• Mathuriya, D. Bader,C. Heitsch, S. Harvey, S,"GTfold: A Scalable Multicore Code for RNA Secondary Structure Prediction. ", Technical report, Georgia Institute of Technology 2008.
• N. R. Markham, M. Zuker, "UNAFold: Software for Nucleic Acid Folding and Hybridization. ", In Bioinformatics: Structure, Function, and Applications, Volume 453 of Methods in Molecular Biology. 2008:3–31.
• P . Marcuello, A. González, " Clustered speculative multithreaded processors. ", In: ICS, pp. 365–372,1999.
• B. K. Pandey, S. K. Pandey, D. Pandey," A Survey of Bioinformatics Applications on Parallel Architectures" International Journal of Computer Applications (0975 – 8887)Volume 23– No. 4, June 2011
• Z. Sukosd ,M. S. Swenson, J. Kjems ,C. E. Heitsch, "Evaluating the accuracy of SHAPE directed RNA secondary structure predictions. ",Journal of Nuclear Acids Research. 41:2807–16, 2013
• M. Taufer, T. Solorio, A. Licon, D. Mireles, and M. -Y. Leung, "On the effectiveness of rebuilding RNA secondary structures from sequence chunks. ", In 7th IEEE Int'l Workshop on High Performance Computational Biology (HiCOMB), pages 1–8, 2008.
• W. Zhou and D. K. Lowenthal, "A parallel, out-of-core algorithm for RNA secondary structure prediction. ", In Int'l Conf. on Parallel Processing (ICPP), pages 74–81, 2006.
• M. Zuker and P. Stiegler, "Optimal computer folding of large RNA sequences using thermodynamic and auxiliary information. ", Nucleic Acids Research, 9(1):133–148, 1981.
• C. Zilles, G. Sohi, "Master/slave speculative parallelization. ", In: MICRO, pp. 85–96 , 2002.