The inverse protein folding problem on 2D and 3D lattices Original Research Article

In this paper we investigate the inverse protein folding (IPF) problem under the Canonical model on 3D and 2D lattices [W.E. Hart, On the computational complexity of sequence design problems, Proceedings of the First Annual International Conference on Computational Molecular Biology 1997, pp. 128–136; E.I. Shakhnovich, A.M. Gutin, Engineering of stable and fast-folding sequences of model proteins, Proc. Natl. Acad. Sci. 90 (1993) 7195–7199]. In this problem, we are given a contact graph image of a protein sequence that is embeddable in a 3D (respectively, 2D) lattice and an integer image. The goal is to find an induced subgraph of G of at most K vertices with the maximum number of edges. In this paper, we prove the following results: