Embedding Cordially Labeled Paths : A Protein Folding Problem

Recently the protein folding problem has been shown to be NP-complete both for the two-and three-dimensional H-P models. The simplest model is that the protein is a sequence of 0s and 1s and folding entails embedding the sequence in the two-dimensional lattice. Each such folding is evaluated with a , equal to the number of pairs of 1s that are adjacent in the lattice without being adjacent in the sequence.On the otherhand cordial labeling is, basically an binary vertex labelling problem of graphs with extra global conditions e.g. vertex and edge labels balancing condition, imposed on the vertex and the induced edge labels.In this paper we have re-formulated protein folding problem for the given special (0,1)-sequences in terms of the cordiality conditions. Some preliminary results encourages us that there exits an efficient algorithm which maximize scores by embedding the cordially labelled paths into 2- and 3-dimensional lattice points. This may give a possible answer to the well-known , that is “How can a folding protein choose so quickly among so many possible foldings the one with minimum energy”