A Tabu search approach for the nuclear magnetic resonance protein structure based assignment problem

Çavuşlar, Gizem (2011) A Tabu search approach for the nuclear magnetic resonance protein structure based assignment problem. [Thesis]

[thumbnail of GizemCavuslar_408696.pdf] PDF

Download (791kB)


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. [17] used the Nuclear Vector Replacement (NVR) [29] framework to model SBA as a binary integer programming problem (NVR-BIP). In this thesis, we prove that this problem is NP-hard and propose a tabu search 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 NVR-BIP's data set which consists of 7 proteins with 25 templates (31 to 126 residues). Furthermore, for two additional large proteins, MBP and EIN (348 and 243 residues, respectively) which NVR-BIP failed to solve, it achieves 91% and 41% assignment accuracies. The executable and the input files are available for download at http://people.sabanciuniv.edu/catay/NVR-TS/NVR-TS.html.
Item Type: Thesis
Uncontrolled Keywords: Nuclear magnetic resonance. -- Structure based assignments. -- Nuclear vector replacement. -- Metaheuristics. -- Tabu search. -- Nükleer manyetik rezonans. -- Yapı tabanlı atama. -- Nükleer vektör değiştirme. -- Metasezgisel yaklaşımlar. -- Tabu arama sezgiseli.
Subjects: T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Industrial Engineering
Faculty of Engineering and Natural Sciences
Depositing User: IC-Cataloging
Date Deposited: 05 Jul 2014 22:42
Last Modified: 26 Apr 2022 10:01
URI: https://research.sabanciuniv.edu/id/eprint/24308

Actions (login required)

View Item
View Item