title: Finding an upper bound for the number of contacts in hydrophobic-hydrophilic protein structure prediction model.
abstract: 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.
authors.affiliation: Department of Industrial and Systems Engineering, KAIST, Daejeon, Republic of Korea.
authors.forename: Namsu
authors.initials: N
authors.lastname: Ahn
authors.forename: Sungsoo
authors.initials: S
authors.lastname: Park
mesh_terms: D000595:Amino Acid Sequence; D019295:Computational Biology / Q000379:methods*; D006801:Humans; D057927:Hydrophobic and Hydrophilic Interactions; D008958:Models, Molecular; D008969:Molecular Sequence Data; D017510:Protein Folding; D011506:Proteins / Q000737:chemistry* / Q000378:metabolism
chemical_list: D011506:Proteins