Multiple Methods for Protein Side Chain Packing Using Maximum Weight Cliques

J.B. Brown[1] (
Dukka Bahadur K.C.[2] (
Etsuji Tomita[3] (
Tatsuya Akutsu[1] (

[1]Bioinformatics Center, Institute for Chemical Research, Kyoto University, Uji, 611-0011 Kyoto, Japan
[2]Center for the Study of Systems Biology, School of Biology, Georgia Institute of Technology, 250 14th Street, 30318 Atlanta GA, USA
[3]Department of Information and Communication Engineering, The University of Electro-Communications, Chofu, 182-8585 Tokyo, Japan


In this paper, we present several methods for computing a solution to the protein side chain packing problem, with all methods having a common solution approach of breaking the polymer into subpolymers and using maximum edge weight cliques to prune the search space for the optimal side chain packing. We characterize the graph sizes generated for each method and compare their prediction accuracies. These methods are demonstrated for computing proteins up to approximately 8000 residues. In addition, we update a result published previously.

[ Full-text PDF | Table of Contents ]

Japanese Society for Bioinformatics