Summary The problem of designing efficient parallel algorithms to calculate the product of n numbers when the multipliers are large is a fundamental problem in many applications of computer science such as cryptography. In this work, we present a new parallel algorithm on exclusive read shared memory model. The performance of the introduced algorithm is measured based on three factors, namely, (1) the number of cores, (2) the size of the array, and (3) the size of the multiplier. The experimental study on a multi core system reveals that the introduced algorithm is faster than the best‐known optimal parallel algorithm. The improvement of the proposed algorithm in processing time compared to the best known parallel algorithm is 80% when the size of the array was 220 and the sizes of the multiplier were 1024, 2048, and 4096 bits. Moreover, our algorithm is a highly scalable parallel algorithm compared with the best‐known optimal parallel algorithm.

BACKGROUND: Restriction site analysis involves determining the locations of restriction sites after the process of digestion by reconstructing their positions based on the lengths of the cut DNA. Using different reaction times with a single enzyme to cut DNA is a technique known as a partial digestion. Determining the exact locations of restriction sites following a partial digestion is challenging due to the computational time required even with the best known practical algorithm. RESULTS: In this paper, we introduce an efficient algorithm to find the exact solution for the partial digest problem. The algorithm is able to find all possible solutions for the input and works by traversing the solution tree with a breadth-first search in two stages and deleting all repeated subproblems. Two types of simulated data, random and Zhang, are used to measure the efficiency of the algorithm. We also apply the algorithm to real data for the Luciferase gene and the E. coli K12 genome. CONCLUSION: Our algorithm is a fast tool to find the exact solution for the partial digest problem. The percentage of improvement is more than 75% over the best known practical algorithm for the worst case. For large numbers of inputs, our algorithm is able to solve the problem in a suitable time, while the best known practical algorithm is unable.

BACKGROUND: Given a set of DNA sequences s1, ..., st, the (l, d) motif problem is to find an l-length motif sequence M , not necessary existing in any of the input sequences, such that for each sequence si, 1 ≤ i ≤ t, there is at least one subsequence differing with at most d mismatches from M. Many exact algorithms have been developed to solve the motif finding problem in the last three decades. However, the problem is still challenging and its solution is limited to small values of l and d. RESULTS: In this paper we present a new efficient method to improve the performance of the exact algorithms for the motif finding problem. Our method is composed of two main steps: First, we process q ≤ t sequences to find candidate motifs. Second, the candidate motifs are searched in the remaining sequences. For both steps, we use the best available algorithms. Our method is a hybrid one, because it integrates currently existing algorithms to achieve the best running time. In this paper, we show how the optimal value of q is determined to achieve the best running time. Our experimental results show that there is about 24% speed-up achieved by our method compared to the best existing algorithm. Furthermore, we also present a parallel version of our method running on shared memory architecture. Our experiments show that the performance of our algorithm scales linearly with the number of processors. Using the parallel version, we were able to solve the (21, 8) challenging instance using 8 processors in 20.42 hours instead of 6.68 days of the serial version. CONCLUSIONS: Our method speeds up the solution of the exact motif problem. Our method is generic, because it can accommodate any new faster algorithm based on traditional methods. We expect that our method will help to discover longer motifs. The software we developed is available for free for academic research at http://www.nubios.nileu.edu.eg/tools/hymotif.

We consider the planted (l, d) motif search problem, which consists of finding a substring of length l that occurs in a set of input sequences {s1, s2, hellip, sn} with maximum Hamming distance, d, around the similar substring. In this paper, we present an experimental comparison between voting algorithm and its modification for planted motif on simulated data from (9, d) to (15, d) in case of challenging instances. The experimental results show that the modified voting algorithm is not better than voting algorithm as theoretically suggested. The results show that the running of voting algorithm is faster than modified voting algorithm in all the cases studied. We also determine, experimentally, the number of sequences that are required to make the modified voting algorithm faster than voting algorithm.