Çavuşlar, Gizem and Çatay, Bülent and Apaydın, Serkan Mehmet (2011) A tabu search approach for the NMR protein structure-based assignment problem. [Working Paper / Technical Report] Sabanci University ID:SU_FENS_2011/0001

There is a more recent version of this item available.
![[thumbnail of TechReport_TS_for_NMR_SBA.pdf]](https://research.sabanciuniv.edu/style/images/fileicons/application_pdf.png)
TechReport_TS_for_NMR_SBA.pdf
Restricted to Repository staff only
Download (422kB) | Request a copy
Abstract
Nuclear Magnetic Resonance (NMR) Spectroscopy is an experimental technique which exploits the magnetic properties of specic 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. Apaydın et al. (2010) used the Nuclear Vector Replacement (NVR) (Langmead et al., 2003) framework to model SBA as a binary integer programming problem (NVR-BIP). In this paper, we prove that this problem is NP-hard and propose a tabu search algorithm (NVR-TS) equipped with a guided perturbation mechanism to eciently solve it. NVR-TS uses a quadratic penalty relaxation of NVR-BIP where the violations in the Nuclear Overhauser Eect constraints are penalized in the objective function. We also implemented a memory structure that reports k best solutions. Experimental results indicate that our algorithm nds the optimal solution on NVR-BIP's data set which consists of 7 proteins with 24 templates (31 to 126 residues). Furthermore, it achieves high assignment accuracies on two additional large proteins, MBP and EIN (348 and
243 residues, respectively), which NVR-BIP failed to solve.
Item Type: | Working Paper / Technical Report |
---|---|
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 Faculty of Engineering and Natural Sciences > Academic programs > Manufacturing Systems Eng. |
Depositing User: | Bülent Çatay |
Date Deposited: | 04 Feb 2011 14:34 |
Last Modified: | 26 Apr 2022 10:49 |
URI: | https://research.sabanciuniv.edu/id/eprint/16336 |
Available Versions of this Item
- A tabu search approach for the NMR protein structure-based assignment problem. (deposited 04 Feb 2011 14:34) [Currently Displayed]