We prove that the protein folding problem in the two-dimensional hydrophobic hydrophilic model is NP-complete. Our reduction is from the Hamilton cycle problem. As is common in previous proofs of weaker results, we start by showing that the folding problem for sets of sequences is NP-complete. We then proceed to establish the result for a single sequence, by resorting to certain interesting variants of the planar Hamilton cycle problem. In our proof we utilize an idea of Trevisan, whereby graphs can be embedded in the hypercube so that adjacency is captured by Hamming distance.
ON THE COMPLEXITY OF PROTEIN FOLDING / P. CRESCENZI; D. GOLDMAN; C.H. PAPADIMITRIOU; A. PICCOLBONI; M. YANNAKAKIS. - STAMPA. - (1998), pp. 597-603. (Intervento presentato al convegno THIRTIETH ANNUAL ACM SYMPOSIUM ON THE THEORY OF COMPUTING) [10.1145/276698.276875].
ON THE COMPLEXITY OF PROTEIN FOLDING
CRESCENZI, PIERLUIGI;
1998
Abstract
We prove that the protein folding problem in the two-dimensional hydrophobic hydrophilic model is NP-complete. Our reduction is from the Hamilton cycle problem. As is common in previous proofs of weaker results, we start by showing that the folding problem for sets of sequences is NP-complete. We then proceed to establish the result for a single sequence, by resorting to certain interesting variants of the planar Hamilton cycle problem. In our proof we utilize an idea of Trevisan, whereby graphs can be embedded in the hypercube so that adjacency is captured by Hamming distance.
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
