Kafes model yapısındaki protein yapı tahmini problemini yöneylem araştırma bakış açısıyla ele alma

Protein structure prediction (PSP) consists of predicting the native structure of a protein from its sequence of amino acids by minimizing an energy function. The problem is of vital importance in medical science, molecular biology, biochemistry, and biophysics. PSP being NP-hard, even when abstracted to lattice models, is computationally challenging. In this study, we develop several mixed integer linear programming (MILP) models for PSP problem under lattices, along with variety of valid inequalities, and two symmetry breaking techniques. We then propose three metaheuristic algorithms. While the focus of our study is on the hydrophobic-polar (HP) model under cubic and square lattices, next, we address some of the drawbacks of the HP model, by proposing extensions of our optimization methods to other more sophisticated PSP models. Finally, we evaluate the performance of these optimization methods with computational experiments. We demonstrate that our MILP models outperform the state of the art models both in terms of running times in finding the optimal integer solutions, and in finding tight bounds on the objective value provided by linear programming (LP) relaxations of the models. We also show that the metaheuristic algorithms are able to find the optimal solutions for many benchmark instances. We then use the solution provided by these metaheuristic algorithms as initial solutions for the MILP models, and for constraining the feasible region. Integrated methods outperform significantly the state of the art models proposed for HP model in lattices. Finally, the computational results establish the robustness of our extended methods.