online read us now
Paper details
Number 2 - June 2017
Volume 27 - 2017
Tabu search for the RNA partial degradation problem
Agnieszka Rybarczyk, Alain Hertz, Marta Kasprzak, Jacek Blazewicz
Abstract
In recent years, a growing interest has been observed in research on RNA (ribonucleic acid), primarily due to the discovery
of the role of RNA molecules in biological systems. They not only serve as templates in protein synthesis or as adapters
in the translation process, but also influence and are involved in the regulation of gene expression. The RNA degradation
process is now heavily studied as a potential source of such riboregulators. In this paper, we consider the so-called
RNA partial degradation problem (RNA PDP). By solving this combinatorial problem, one can reconstruct a given RNA
molecule, having as input the results of the biochemical analysis of its degradation, which possibly contain errors (false
negatives or false positives). From the computational point of view the RNA PDP is strongly NP-hard. Hence, there is a
need for developing algorithms that construct good suboptimal solutions. We propose a heuristic approach, in which two
tabu search algorithms cooperate, in order to reconstruct an RNA molecule. Computational tests clearly demonstrate that
the proposed approach fits well the biological problem and allows to achieve near-optimal results.
The algorithm is freely
available at http://www.cs.put.poznan.pl/arybarczyk/tabusearch.php.
Keywords
RNA degradation, tabu search, bioinformatics