Heuristic-based tabu search algorithm for folding two-dimensional AB off-lattice model proteins.
The protein structure prediction problem is a classical NP hard problem in bioinformatics. The lack of an effective global optimization method is the key obstacle in solving this problem. As one of the global optimization algorithms, tabu search (TS) algorithm has been successfully applied in many optimization problems. We define the new neighborhood conformation, tabu object and acceptance criteria of current conformation based on the original TS algorithm and put forward an improved TS algorithm. By integrating the heuristic initialization mechanism, the heuristic conformation updating mechanism, and the gradient method into the improved TS algorithm, a heuristic-based tabu search (HTS) algorithm is presented for predicting the two-dimensional (2D) protein folding structure in AB off-lattice model which consists of hydrophobic (A) and hydrophilic (B) monomers. The tabu search minimization leads to the basins of local minima, near which a local search mechanism is then proposed to further search for lower-energy conformations. To test the performance of the proposed algorithm, experiments are performed on four Fibonacci sequences and two real protein sequences. The experimental results show that the proposed algorithm has found the lowest-energy conformations so far for three shorter Fibonacci sequences and renewed the results for the longest one, as well as two real protein sequences, demonstrating that the HTS algorithm is quite promising in finding the ground states for AB off-lattice model proteins.
Network Information Center, Nanjing University of Information Science and Technology, Nanjing 210044, PR China; School of Computer and Software, Nanjing University of Information Science and Technology, Nanjing 210044, PR China. Electronic address: jfliu@nuist.edu.cn.
Jingfa
J
Liu
Yuanyuan
Y
Sun
Gang
G
Li
Beibei
B
Song
Weibo
W
Huang
D000465:Algorithms; D008958:Models, Molecular; D011487:Protein Conformation; D017510:Protein Folding; D011506:Proteins / Q000737:chemistry*
D011506:Proteins
2D; 2D AB off-lattice model; ACMC; CSA; ELP+; HTS; Heuristic-based tabu search algorithm; Local search; M-QPSO; MPSO; PSO; Protein structure prediction; SA; STA; TS; annealing contour Monte Carlo algorithm; conformational space annealing; heuristic-based tabu search; improved energy landscape paving method; multi particle swarm optimization; multiple-layer quantum-behaved particle swarm optimization; nPERMis; new pruned-enriched-Rosenbluth method with importance sampling; particle swarm optimization; simulating annealing; statistical temperature annealing; tabu search; two-dimensional