To enable extensive research on the ribonucleic acid (RNA) molecule, predicting its spatial structure stands as a much-valued research field. In this regard, Nussinov and Jacobson published the (now) de facto solution to predict the halfway secondary structure, which runs in cubic time for an n-nucleotide sequence. We design our contribution starting from two of the several works conducted to improve this running time. First, those of Frid and Gusfield, which associate a speedup named sparsification with an on-demand Four-Russians paradigm to achieve the fastest theoretical solution known to date. And second, those of Palkowski and Bielecki, which efficiently restructure the classical Nussinov loop nest with a novel tiling technique. Alongside other loop transformations, this paper shows that, owing to loop restructuring promoting cache reuse and variable-grained parallelism, applying the latter approach to the Frid and Gusfield doubly sped-up loop nest yields outperforming improvements both in sequential and in parallel. In fact, following empirical evaluation, we have obtained relatively to Palkowski's sequential basis, speedups up to x3.26 sequentially and up to x28.50 on 32 threads of a multicore processor with a 30,000-nucleotide sequence. Furthermore, the massive parallel environment in graphics cards has led this speedup factor to reach x44.37.

Summary This article presents a fast sequential algorithm for the matrix chain ordering problem. Our solution is based on Yao's sequential algorithm that solves this problem in time by reducing the total number of distinct subproblems to be performed. We solve them fastly by avoiding some unnecessary computations. Our strategy consists in organizing the evaluation of the subproblems according to their dependencies instead of their precedence order as in the previous solutions. In many cases, our solution runs in time. An experimental study is conducted to benchmark the performance of our algorithm by measuring the average of the results obtained on five random data sets. This shows that our algorithm is 18.93 faster than Yao's sequential algorithm and 5.07 faster than the previous best CGM‐based parallel solutions on 32 processors.

The coarse-grained multicomputer parallel model (CGM for short) has been used for solving several classes of dynamic programming problems. In this paper, we propose a parallel algorithm on the CGM model, with p processors, for solving the optimal binary search tree problem (OBST problem), which is a polyadic non-serial dynamic programming problem. Firstly, we propose a dynamic graph model for solving the OBST problem and show that each instance of this problem corresponds to a one-to-all shortest path problem in this graph. Secondly, we propose a CGM parallel algorithm based on our dynamic graph to solve the OBST problem through one-to-all shortest paths in this graph. It uses our new technique of irregular partitioning of the dynamic graph to try to bring a solution to the well-known contradictory objectives of the minimization of the communication time and the load balancing of the processors in this type of graph. Our solution is based on Knuth’s sequential solution and required $${\mathcal {O}}\left( \dfrac{n^2}{p} \right)$$ time steps per processor and $$\lceil \sqrt{2p} \rceil + k \times \left( {\left\lceil \dfrac{\lceil \sqrt{2p} \rceil }{2} \right\rceil } + 1 \right)$$ communication rounds. Integer k is a parameter used in the partitioning technique of our algorithm. This new CGM algorithm performs better than the previously most efficient solution, which uses regular partitioning of the tasks graph.