Assigning NMR spectra of irregular RNAs by heuristic algorithms

• Autorzy: Szachniuk M.

Identyfikatory

DOI

10.1515/bpasts-2015-0037

• Języki publikacji: EN

Abstrakty

EN

Computer-aided analysis and preprocessing of spectral data is a prerequisite for any study of molecular structures by Nuclear Magnetic Resonance (NMR) spectroscopy. The data processing stage usually involves a considerable dedication of time and expert knowledge to cope with peak picking, resonance signal assignment and calculation of structure parameters. A significant part of the latter step is performed in an automated way. However, in peak picking and resonance assignment a multistage manual assistance is still essential. The work presented here is focused on the theoretical modeling and analyzing the assignment problem by applying heuristic approaches to the NMR spectra recorded for RNA structures containing irregular regions.

Słowa kluczowe

EN

bioinformatics; NMR; tabu search; beam search; RNA structure

PL

bioinformatyka; NMR; wyszukiwarka tabu; wyszukiwarka wiązki; struktura RNA

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2015
• Tom: Vol. 63, nr 1
• Strony: 329--338
• Opis fizyczny: Bibliogr. 28, rys., tab.

Twórcy

autor

Szachniuk M.

• Institute of Bioorganic Chemistry, Polish Academy of Sciences 12/14 Noskowskiego St., 61-704 Poznan, Poland
• Institute of Computing Science, Poznan University of Technology, 2 Piotrowo St., 60-965 Poznan, Poland

Bibliografia

• [1] A.H. Kwan, M. Mobli, P.R. Gooley, G.F. King, and J.P. Mackay, “Macromolecular NMR spectroscopy for the nonspectroscopist”, FEBS J. 278 (5), 687-703 (2011).
• [2] J. Blazewicz, M. Szachniuk, and A. Wojtowicz, “Evolutionary approach to NOE paths assignment in RNA structure elucidation”, Proc. 2004 IEEE Symp. on Computational Intelligence in Bioinformatics and Computational Biology 1, 206-213 (2004).
• [3] G. Brix, H. Kolem, W.R. Nitz, M. Bock, A. Huppertz, C.J. Zech, and O. Dietrich, “Basics of magnetic resonance imaging and magnetic resonance spectroscopy” in eds. M.F. Reiser, W. Semmler, and H. Hricak, Magnetic Resonance Tomography, Springer, Berlin, 2008.
• [4] L. Popenda, L. Bielecki, Z. Gdaniec, and R.W. Adamiak, “Structure and dynamics of adenosine bulged RNA duplex reveals formation of the dinucleotide platform in the C:G-A triple”, ARKIVOC 3, 130-144 (2009).
• [5] D. Zimmerman, C. Kulikowski, Y. Huang, W. Feng, M.S. Tashiro, S. Shimotakahara, C. Chien, R. Powers, and G.T. Montelione, “Automated analysis of protein NMR assignments using methods from artificial intelligence”, J. Mol. Biol. 269 (4), 592-610 (1997).
• [6] H.S. Atreya, S.C. Sahu, K.V.R. Chary, and G. Govil, “A tracked approach for automated NMR assignments in proteins (TATAPRO)”, J. Biomol. NMR 17 (2), 125-136 (2000).
• [7] G. Cavuslar, B. Catay, and M.S. Apaydin, “A tabu search approach for the NMR protein structure-based assignment problem”, IEEE/ACM Trans. Comput. Biol. Bioinform. 9 (6), 1621-1628 (2012).
• [8] P. Guntert, M. Saltzmann, D. Braun, and K. Wuthrich, “Sequence-specific NMR assignment of proteins by global fragment mapping with program Mapper”, J. Biomol. NMR 18 (2), 129-137 (2000).
• [9] D. Stratmann, C. van Heijenoort, and E. Guittet, “NOEnet - use of NOE networks for NMR resonance assignment of proteins with known 3D structure”, Bioinformatics 25 (4), 474-481 (2009).
• [10] X.Wan and G. Lin, “CISA: combined NMR resonance connectivity information determination and sequential assignment”, IEEE ACM T. Comput. Bi. 4 (3), 336-348 (2007).
• [11] N.E.G Buchler, E.P.R. Zuiderweg, H. Wang, and R.A. Goldstein, “Protein heteronuclear NMR assignments using meanfield simulated annealing”, J. Mol. Resonance 125 (1), 34-42 (1997).
• [12] C. Bartels, P. Guntert, M. Billeter, and K. Wuthrich, “GARANT - A general algorithm for resonance assignment of multidimensional nuclear magnetic resonance spectra”, J. Comp. Chem. 18 (1), 139-149 (1997).
• [13] M. Leutner, R.M. Gschwind, J. Liermann, C. Schwarz, C. Gemmecker, and H. Kessler, “Automated backbone assignment of labeled proteins using the threshold accepting algorithm”, J. Biomol. NMR 11 (1), 31-43 (1998).
• [14] T.K. Hitchens, J.A. Lurkin, Y. Zhan, S.A. McCallum, and G.S. Rule, “MONTE: An automated Monte Carlo based approach to nuclear magnetic resonance assignment of proteins”, J. Biomol. NMR 25 (1), 1-9 (2003).
• [15] M.S. Apaydin, B. Catay, N. Patrick, and B.R. Donald, “NVRBIP: nuclear vector replacement using binary integer programming for NMR structure-based assignments”, Computer J. 54 (5), 708-716 (2011).
• [16] T. Zok, M. Popenda, and M. Szachniuk, “MCQ4Structures to compute similarity of molecule structures”, Central Eur. J. Operations Research 22 (3), 457-474 (2014).
• [17] R.W. Adamiak, J. Blazewicz, P. Formanowicz, Z. Gdaniec, M. Kasprzak, M. Popenda, and M. Szachniuk, “An algorithm for an automatic NOE pathways analysis of 2D NMR spectra of RNA duplexes”, J. Comp. Biol. 11 (1), 163-180 (2004).
• [18] M.W. Roggenbuck, T.J. Hyman, and P.N. Borer, “Path analysis in NMR spectra: application to an RNA octamer”, Structure and Methods 3, 309-317 (1990).
• [19] M. Szachniuk, M. Popenda, R.W. Adamiak, and J. Blazewicz, “An assignment walk through 3D NMR spectrum”, Proc. 2009 IEEE Symp. on Computational Intelligence in Bioinformatics and Computational Biology 1, 215-219 (2009).
• [20] J. Blazewicz, M. Szachniuk, and A. Wojtowicz, “Evolutionary algorithm for a reconstruction of NOE paths in NMR spectra of RNA chains”, Bull. Pol. Ac.: Tech. 53 (3), 221-230 (2004).
• [21] J. Blazewicz, M. Szachniuk, and A. Wojtowicz, “RNA tertiary structure determination: NOE pathway construction by tabu search”, Bioinformatics 21 (10), 2356-2361 (2005).
• [22] M. Szachniuk, L. Popenda, Z. Gdaniec, R.W. Adamiak, and J. Blazewicz, “NMR analysis of RNA bulged structures: tabu search application in NOE signal assignment”, Proc. 2005 IEEE Symp. on Computational Intelligence in Bioinformatics and Computational Biology 1, 172-178 (2005).
• [23] M. Szachniuk, M. Malaczynski, E. Pesch, E.K. Burke, and J. Blazewicz, “MLP accompanied beam search for the resonance assignment problem”, J. Heuristics 19 (3), 443-464 (2013).
• [24] W. Frohmberg, M. Kierzynka, J. Blazewicz, P. Gawron, and P. Wojciechowski, “G-DNA - a highly efficient multi- GPU/MPI tool for aligning nucleotide reads”, Bull. Pol. Ac.: Tech. 61 (4), 989-992 (2013).
• [25] F.A.L. Anet and A.J.R. Bourn, “Nuclear Magnetic Resonance spectral assignments from Nuclear Overhauser effects”, J. Am. Chem. Soc. 87 (22), 5250-5251 (1965).
• [26] M. Szachniuk, M.C. De Cola, G. Felici, D. de Werra, and J. Blazewicz, “Optimal pathway reconstruction on 3D NMR maps”, Discrete Applied Mathematics 182, 134-149 (2015).
• [27] M. Szachniuk, M.C. De Cola, G. Felici, and J. Blazewicz, “The orderly colored longest path problem - a survey of applications and new algorithms”, RAIRO Operations Research 48 (1), 25-51 (2014).
• [28] F. Glover and M. Laguna, Tabu Search, Kluwer Academic Publishers, Boston, 1997