Tabu search for the RNA partial degradation problem

Rybarczyk, A. ; Hertz, A. ; Kasprzak, M. ; Blazewicz, J.

International Journal of Applied Mathematics and Computer Science, Tome 27 (2017) no. 2, pp. 401-415.

Résumé

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.

Détail

Keywords: RNA degradation, tabu search, bioinformatics
Mots-clés : rozkład RNA, algorytm tabu search, bioinformatyka

Bibliographie

[1] Adachi, H. and Yu, Y. (2014). Purification of radiolabeled RNA products using denaturing gel electrophoresis, Current Protocols in Molecular Biology 105: 4.20.1–4.20.13, DOI: 10.1002/0471142727.mb0420s105.

[2] Bibillo, A., Figlerowicz, M. and Kierzek, R. (1999). The non-enzymatic hydrolysis of oligoribonucleotides. VI: The role of biogenic polyamines, Nucleic Acids Research 27(19): 3931–3937, DOI: 10.1093/nar/27.19.3931.

[3] Bibillo, A., Figlerowicz, M., Ziomek, K. and Kierzek, R. (2000). The nonenzymatic hydrolysis of oligoribonucleotides. VII: Structural elements affecting hydrolysis, Nucleosides Nucleotides Nucleic Acids 19(5–6): 977–994, DOI: 10.1080/15257770008033037.

[4] Bilski, A. and Wojciechowski, J. (2016). Automatic parametric fault detection in complex analog systems based on a method of minimum node selection, International Journal of Applied Mathematics and Computer Science 26(3): 655–668, DOI: 10.1515/amcs-2016-0045.

[5] Blazewicz, J., Figlerowicz, M., Kasprzak, M., Nowacka, M. and Rybarczyk, A. (2011). RNA partial degradation problem: Motivation, complexity, algorithm, Journal of Computational Biology 18(6): 821–834, DOI: 10.1089/cmb.2010.0153.

[6] Blazewicz, J., Formanowicz, P., Guinand, F. and Kasprzak, M. (2002). A heuristic managing errors for DNA sequencing, Bioinformatics 18(5): 652–660, DOI: 10.1093/bioinformatics/18.5.652.

[7] Blazewicz, J., Formanowicz, P., Kasprzak, M., Jaroszewski, M. and Markiewicz, W. (2001). Construction of DNA restriction maps based on a simplified experiment, Bioinformatics 17(5): 398–404, DOI: 10.1093/bioinformatics/17.5.398.

[8] Blazewicz, J., Formanowicz, P., Kasprzak, M., Markiewicz, W. and Weglarz, J. (1999). DNA sequencing with positive and negative errors, Journal of Computational Biology 6(1): 113–123, DOI: 10.1089/ cmb.1999.6.113.

[9] Blazewicz, J., Glover, F. and Kasprzak, M. (2005). Evolutionary approaches to DNA sequencing with errors, Annals of Operations Research 138(67): 67–78, DOI: 10.1007/s10479-005-2445-2.

[10] Blazewicz, J. and Kasprzak, M. (2012). Complexity issues in computational biology, Fundamenta Informaticae 118(4): 385–401, DOI: 10.3233/FI-2012-721.

[11] Chanfreau, G. (2015). Two degrading decades for RNA, RNA 21(4): 584–585, DOI: 10.1261/rna.050146.115.

[12] Deutscher, M. (2003). Degradation of stable RNA in bacteria, Journal of Biological Chemistry 278(46): 45041–45044, DOI: 10.1074/jbc.R300031200.

[13] Dutkiewicz, M. and Ciesiolka, J. (2005). Structural characterization of the highly conserved 98-base sequence at the 3’ end of HCV RNA genome and the complementary sequence located at the 5’ end of the replicative viral strand, Nucleic Acids Research 33(2): 693–703, DOI: 10.1093/nar/gki218.

[14] Ender, C., Krek, A., Friedlander, M., Beitzinger, M., Weinmann, L., Chen, W., Pfeffer, S., Rajewsky, N. and Meister, G. (2008). A human snoRNA with microRNA-like functions, Molecular Cell 32(4): 519–528, DOI: 10.1016/j.molcel.2008.10.017.

[15] Garey, M. and Johnson, D. (1979). Computers and Intractability. A Guide to the Theory of NP-Completeness,W.H. Freeman Co., New York, NY.

[16] Glover, F. (1990). Tabu search: A tutorial, Interfaces 20: 74–94, DOI: 10.1287/inte.20.4.74.

[17] Glover, F., Kelly, J. and Laguna, M. (1995). Genetic algorithms and tabu search: Hybrids for optimization, Computers and Operations Research 22(1): 111–134, DOI: 10.1016/0305-0548(93)E0023-M.

[18] Glover, F. and Laguna, M. (1997). Tabu Search, Kluwer Academic Publishers, Norwell, MA.

[19] Haussecker, D., Huang, Y., Lau, A., Parameswaran, P., Fire, A. and Kay, M. (2010). Human tRNA-derived small RNAs in the global regulation of RNA silencing, RNA 16(4): 673–695, DOI: 10.1261/rna.2000810.

[20] Jackowiak, P., Nowacka, M., Strozycki, P. and Figlerowicz, M. (2011). RNA degradome—ITS biogenesis and functions, Nucleic Acids Research 39(17): 7361–7370, DOI: 10.1093/nar/gkr450.

[21] Jankowiak, K., Lesicka, J., Pacak, A., Rybarczyk, A. And Szweykowska-Kulinska, Z. (2004). A comparison of group II introns of plastid tRNALys UUU genes encoding maturase protein, Cellular and Molecular Biology Letters 9(2): 239–251.

[22] Jankowiak, K., Rybarczyk, A., Wyatt, R., Odrzykoski, I., Pacak, A. and Szweykowska-Kulinska, Z. (2005). Organellar inheritance in the allopolyploid moss rhizomnium pseudopunctatum, Taxon 54(2): 383–388, DOI: 10.2307/25065367.

[23] Kierzek, R. (1992). Hydrolysis of oligoribonucleotides: influence of sequence and length, Nucleic Acids Research 20(19): 5073–5077, DOI: 10.1093/nar/20.19.5073.

[24] Kierzek, R. (2001). Nonenzymatic cleavage of oligoribonucleotides, Methods in Enzymology 341: 657–675.

[25] Kuppusamy, L. and Mahendran, A. (2016). Modelling DNA and RNA secondary structures using matrix insertion–deletion systems, International Journal of Applied Mathematics and Computer Science 26(1): 245–258, DOI: 10.1515/amcs-2016-0017.

[26] Nowacka, M., Jackowiak, P., Rybarczyk, A., Magacz, T., Strozycki, P., Barciszewski, J. and Figlerowicz, M. (2012). 2D-PAGE as an effective method of RNA degradome analysis, Molecular Biology Reports 39(1): 139–146, DOI: 10.1007/s11033-011-0718-1.

[27] Podkowinski, J., Zmienko, A., Florek, B., Wojciechowski, P., Rybarczyk, A., Wrzesinski, J., Ciesiolka, J., Blazewicz, J., Kondorosi, A., Crespi, M. and Legocki, A. (2009). Translational and structural analysis of the shortest legume ENOD40 gene in Lupinus luteus, Acta Biochimica Polonica 56(1): 89–102.

[28] Rybarczyk, A., Jackowiak, P., Figlerowicz, M. and Blazewicz, J. (2016). Computational prediction of nonenzymatic RNA degradation patterns, Acta Biochimica Polonica 63(4): 745–751, DOI: 10.18388/abp.2016 1331.

[29] Rybarczyk, A., Szostak, N., Antczak, M., Zok, T., Popenda, M., Adamiak, R., Blazewicz, J. and Szachniuk, M. (2015). New in silico approach to assessing RNA secondary structures with non-canonical base pairs, BMC Bioinformatics 16: 276, DOI: 10.1186/s12859-015-0718-6.

[30] Szostak, N., Royo, F., Rybarczyk, A., Szachniuk, M., Blazewicz, J., del Sol, A. and Falcon-Perez, J. (2014). Sorting signal targeting mRNA into hepatic extracellular vesicles, RNA Biology 11(7): 836–844, DOI: 10.4161/rna.29305.

[31] Yao, B., Hu, P., Zhang, M. and Jin, M. (2014). A support vector machine with the tabu search algorithm for freeway incident detection, International Journal of Applied Mathematics and Computer Science 24(2): 397–404, DOI: 10.2478/amcs-2014-0030.

[32] Zhang, S., Sun, L. and Kragler, F. (2009). The phloem-delivered RNA pool contains small noncoding RNAs and interferes with translation, Plant Physiology 150(1): 378–387, DOI: 10.1104/pp.108.134767.

[33] Zok, T., Antczak, M., Riedel, M., Nebel, D., Villmann, T., Lukasiak, P., Blazewicz, J. and Szachniuk, M. (2015). Building the library of RNA 3D nucleotide conformations using the clustering approach, International Journal of Applied Mathematics and Computer Science 25(3): 689–700, DOI: 10.1515/amcs-2015-0050.