MicroRNA-target interaction: a parallel approach for computing pairing energy

MicroRNAs (or miRNA) are key regulators of gene expression, but the precise mechanisms underlying their interaction with their mRNA-targets are still poorly understood. Since miRNA are involved in the onset of many different diseases, the study of their interaction with the genome is very important to study. Different approaches can be used to recognize miRNA-targets. These efforts have focused primarily on the quality of the sequence match between microRNA and target rather than on the role of the mRNA secondary structure in which the target is embedded. Nonetheless, it is known that the miRNA secondary structures contribute to target recognition, because there is an energetic cost to freeing base-pairing interactions within mRNA in order to make the target accessible for microRNA binding. This second approach can provide good results even when little is know about the conservation of the miRNA, but it has the drawback of being computationally very expensive. In this paper we propose a parallelization of PITA, which is one of the most popular algorithm that exploits energetic considerations for computing the miRNA-target predictions. The parallel algorithm is based on a coarse-grained subdivision of the workload, which provides good speedup figures by minimizing communications overheads.