Progress in Nuclear Vector Replacement for NMR Protein Structure-Based Assignments

ŞeymaÇetnİkaya; Ekren, Şeyma Nur; Apaydın, Mehmet Serkan

RAIRO - Operations Research - Recherche Opérationnelle, Special issue: Research on Optimization and Graph Theory dedicated to COSI 2013 / Special issue: Recent Advances in Operations Research in Computational Biology, Bioinformatics and Medicine, Tome 50 (2016) no. 2, pp. 341-349.

Nuclear Magnetic Resonance (NMR) Spectroscopy is an important technique to obtain structural information of a protein. In this technique, an essential step is the backbone resonance assignment and Structure Based Assignment (SBA) aims to solve this problem with the help of a template structure. Nuclear Vector Replacement (NVR) is an NMR protein SBA program, that takes as input ${}^{15}N$ and $H^N$ chemical shifts and unambiguous NOEs, as well as RDCs, HD-exchange and TOCSY data. NVR does not utilize ${}^{13}C$ chemical shifts although this data is widely available for many proteins. In addition, NVR is a proof-of-principle approach and has been run with specific and manually set parameters for some proteins. NA-NVR-ACO [M. Akhmedov, B.Çatay and M.S. Apaydın, $𝐽.\mathrm{𝐵𝑖𝑜𝑖𝑛𝑓𝑜𝑟𝑚}.\mathrm{𝐶𝑜𝑚𝑝𝑢𝑡}.\mathrm{𝐵𝑖𝑜𝑙}.$$\mathbf{13}$ (2015) 1550020.] remedies this problem for the NOE data and standardizes NOE usage, while using an ant colony optimization based algorithm. In this paper, we standardize NA-NVR-ACO’s scoring function by using the same parameters for all the proteins and incorporating ${}^{13}{C}_{\alpha }$ chemical shifts. We also use a larger protein database and state-of-the-art chemical shift prediction tools, SHIFTX2 [B. Han, Y. Liu, S.W. Ginzinger and D.S. Wishart, $𝐽.\mathrm{𝐵𝑖𝑜𝑚𝑜𝑙}.\mathrm{𝑁𝑀𝑅}\mathbf{50}$ (2011) 43–57.] and SPARTA$+$ [Y. Shen and A. Bax, $𝐽.\mathrm{𝐵𝑖𝑜𝑚𝑜𝑙}.\mathrm{𝑁𝑀𝑅}\mathbf{48}$ (2010) 13–22], to extract the chemical shift statistics. Other practical improvements include automatizing data file preparation and obtaining a degree of reliability for individual peak-amino acid assignments. Our results show that our improvements bring NA-NVR-ACO closer to a practical tool, able to handle a variety of different data types.

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 (2004) 163–180. | DOI

M. Akhmedov, B. Çatay and M.S. Apaydın, Automating unambiguous NOE data usage in NVR for NMR protein structure-based assignments. J. Bioinform. Comput. Biol. 13 (2015) 1550020. | DOI

M.S. Apaydın, V. Conitzer and B.R. Donald, Structure-based protein NMR assignments using native structural ensembles. J. Biomol. NMR 40 (2008) 263–276. | DOI

M.S. Apaydın, B. Çatay, N. Patrick and B.R. Donald, NVR-BIP: Nuclear vector replacement using binary integer programming for NMR structure-based assignments. Comput. J. 54 (2011) 708–716. | DOI

J. Aslanov, B.Çatay and M.S. Apaydın, An Ant Colony Optimization Approach for Solving the Nuclear Magnetic Resonance Structure Based Assignment Problem. GECCO (2013).

J. Blazewicz, M. Szachniuk and A. Wojtowicz, RNA tertiary structure determination$:$ NOE pathways construction by tabu search. Bioinform. 21 (2005) 2356–2361. | DOI

G. Cavuslar, B. Çatay and M.S. Apaydın, A Tabu search approach for the NMR protein structure-based assignment problem. IEEE/ACM Trans. Comput. Biology Bioinform. 9 (2012) 1621–1628. | DOI

F.A. Chao, J. Kim, Y. Xia, M. Milligan, N. Rowe and G. Veglia, FLAMEnGO 2.0$:$ An enhanced fuzzy logic algorithm for structure-based assignment of methyl group resonances. J. Magn. Reson. 245 (2014) 17–23. | DOI

B. Han, Y. Liu, S.W. Ginzinger and D.S. Wishart, SHIFTX2$:$ significantly improved protein chemical shift prediction. J. Biomol. NMR 50 (2011) 43–57. | DOI

R. Jang, Fast and Robust Mathematical Modeling of NMR Assignment Problems. Ph.D. thesis, University of Waterloo, Canada (2012).

Y.S. Jung and M. Zweckstetter, Backbone assignment of proteins with known structure using residual dipolar couplings. J. Biomol. NMR 30 (2004) 25–35. | DOI

C.J. Langmead and B.R. Donald, An expectation/maximization nuclear vector replacement algorithm for automated NMR resonance assignments. J. Biomol. NMR 29 (2004) 111–138. | DOI

C.A. Macraild and R.S. Norton, RASP$:$ rapid and robust backbone chemical shift assignments from protein structure. J. Biomol. NMR 58 (2014) 155–163. | DOI

S. Neal, A.M. Nip, H. Zhang and D.S. Wishart, Rapid and accurate calculation of protein 1H, 13C and 15N chemical shifts. J. Biomol. NMR 26 (2003) 215–240. | DOI

E. Schmidt and P. Güntert, A new algorithm for reliable and general NMR resonance assignment. J. Am. Chem. Soc. 134 (2012) 12817–12829. | DOI

Y. Shen and A. Bax, SPARTA$+$: a modest improvement in empirical NMR chemical shift prediction by means of an artificial neural network. J. Biomol. NMR 48 (2010) 13–22. | DOI

M. Szachniuk, M. Malaczynski, E. Pesch, E.K. Burke and J. Blazewich, MLP accompanied beam search for the resonance assignment problem. J. Heuristics 19 (2013) 443–464. | DOI

M. Szachniuk, M.C. De Cola, G. Felici and J. Blazewich, The orderly colored longest path problem - A survey of applications and new algorithms. RAIRO: OR 48 (2014) 25–51. | DOI | Numdam | MR | Zbl

W.F. Vranken, W. Boucher, T.J. Stevens, R.H. Fogh, A. Pajon, M. Llinas, E.L. Ulrich, J.L. Markley, J. Ionides and E.D. Laue, The CCPN data model for NMR spectroscopy: Development of a software pipeline. Proteins: Structure, Function, and Bioinform. 59 (2005) 687–696. | DOI

X.P. Xu and D.A. Case, Automated prediction of 15N, 13C$\alpha$, 13C$\beta$ and 13C chemical shifts in protein using a density functional database. J. Biomol. NMR 21 (2001) 321–333. | DOI