Finding an upper bound for the number of contacts in hydrophobic-hydrophilic protein structure prediction model

It is believed that the functional properties of the protein are dependent on its structure. Therefore, it is critical to predict the protein's structure to understand the functional properties. One of the most widely studied protein structure prediction models is the hydrophobic-hydrophilic (HP) model, which abstracts the dominant force in protein folding. That is, to explain the hydrophobic interaction, the HP model tries to maximize the number of contacts among hydrophobic amino acids. Although a number of heuristics have been proposed to find a tight lower bound for the number of contacts, these methods cannot guarantee the quality of the obtained solution since no information on upper bound has been obtained. In this research, we focus on identifying the efficiently computable upper bound. We present a new mathematical formulation of the HP model, which can provide an upper bound using linear relaxation of the formulation. Computational experiments using benchmark problems show that our formulation provides tight upper bound.