A combinatorial algorithm for effective generation of long maximally compact lattice chains

We investigate the problem of generation of maximally compact lattice chains which are useful in understanding folding of model proteins. The term, maximally compact chain, refers to a lattice self-avoiding walk that visits every lattice site. Generation of a representative sample of compact conformations is extremely difficult by conventional simulation methods such as static growth methods or dynamic Monte Carlo techniques. Growing a random walk is ineffective for generating long walks in a compact shape because a large number of walks are rejected due to overlap (attrition). In the interest of an unbiased sample, one needs to enumerate all possible compact conformations that are realizable or produce a representative sample, the former of which is intractable for long chains. In this paper a method is proposed for generation of compact chains on a lattice based on a mathematical programming approach. The method, which we refer to as the Hamiltonian path generation method, generates a random sample of lattice filling self-avoiding walks. A detailed description of a randomized generation algorithm is presented, which is effective for producing a static sample of compact lattice chains. There is a statistical evidence of fair generation of conformations from the conformational space using this scheme. This method generates a compact conformation on a 60×60×60 cubic lattice in forty minutes on a Sparc-2 workstation.