A tabu search approach for the NMR protein structure-based assignment problem

Çavuşlar, Gizem and Çatay, Bülent and Apaydın, Serkan Mehmet (2012) A tabu search approach for the NMR protein structure-based assignment problem. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 9 (6). pp. 1621-1628. ISSN 1545-5963

This is the latest version of this item.

Full text not available from this repository. (Request a copy)

Abstract

Nuclear Magnetic Resonance (NMR) Spectroscopy is an experimental technique which exploits the magnetic properties of specific nuclei and enables the study of proteins in solution. The key bottleneck of NMR studies is to map the NMR peaks to corresponding nuclei, also known as the assignment problem. Structure Based Assignment (SBA) is an approach to solve this computationally challenging problem by using prior information about the protein obtained from a homologous structure. NVR-BIP used the Nuclear Vector Replacement (NVR) framework to model SBA as a binary integer programming problem. In this paper, we prove that this problem is NP-hard and propose a tabu search (TS) algorithm (NVR-TS) equipped with a guided perturbation mechanism to efficiently solve it. NVR-TS uses a quadratic penalty relaxation of NVR-BIP where the violations in the Nuclear Overhauser Effect constraints are penalized in the objective function. Experimental results indicate that our algorithm finds the optimal solution on NVRBIP’s data set which consists of 7 proteins with 25 templates (31 to 126 residues). Furthermore, it achieves relatively high assignment accuracies on two additional large proteins, MBP and EIN (348 and 243 residues, respectively), which NVR-BIP failed to solve. The executable and the input files are available for download at http://people.sabanciuniv.edu/catay/NVR-TS/NVR-TS.html
Item Type: Article
Uncontrolled Keywords: Automated NMR assignments , NMR structural biology , structural bioinformatics , tabu search
Subjects: T Technology > TA Engineering (General). Civil engineering (General) > TA164 Bioengineering
T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering
T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering > T57.6-57.97 Operations research. Systems analysis
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences > Academic programs > Manufacturing Systems Eng.
Faculty of Engineering and Natural Sciences
Depositing User: Bülent Çatay
Date Deposited: 10 Jan 2013 10:56
Last Modified: 01 Aug 2019 10:03
URI: https://research.sabanciuniv.edu/id/eprint/21332

Available Versions of this Item

Actions (login required)

View Item
View Item