Time Algorithm for d-Dimensional Protein Folding in the HP-Model
Bin Fu, Wei Wang · 2004
The protein folding problem in the HP-model is NP-hard in both 2D and 3D (4,6). The problem is to put a sequence, consisting of two characters H and P, on a d-dimensional grid to have the maximal number of HH contacts. We design a 2 O(n 1− 1 d log n) time algorithm for d- dimensional protein folding in the HP-model. In particular, our algorithm