Geometric separators and their applications to protein folding in the HP-model
We develop a new method for deriving a geometric separator for a set of grid points. Our separator has a linear structure, which can effectively partition a grid graph. For example, we prove that for a grid graph G with a set of n points P in a two-dimensional grid, there is a separator with at most 1.129 root n points in P that partitions G into two disconnected grid graphs each with at most 2n/3 points. Our separator theorem for grid graphs has a significantly smaller upper bound than that was obtained for the general planar graphs in [H. N. Djidjev and S. M. Venkatesan, Acta Inform., 34 (1997), pp. 231-234]. The protein folding problem in the HP-model is to put a sequence, consisting of two characters H and P, in a d-dimensional grid to have maximal number of HH-contacts, where an HH-contact is a pair of non-consecutive H letters that are put at two grid points of distance 1. Our separator is then applied to develop an exact algorithm for the protein-folding problem in the HP-model, which is NP-hard both in both two and three dimensions [B. Berger and T. Leighton, J. Comput. Biol., 5 (1998), pp. 27-40; P. Crescenzi et al., J. Comput. Biol., 5 (1998), pp. 423-465]. We design a 2(O)(n(1-1/d) log n) time algorithm for the d-dimensional protein folding problem in the HP-model. In particular, our algorithm has O(2(6.145 root n) (log n)) and O(2(6.913n) (2/3 log n)) computational time in two and three dimensions, respectively.
separator protein folding algorithm time complexity