This paper studies the protein side-chain packing problem
using the tree-decomposition of a protein structure.
To obtain fast and accurate protein side-chain packing,
protein structures are modeled using a geometric neighborhood graph,
which can be easily decomposed into smaller blocks.
Therefore, the side-chain assignment of the whole protein can be
assembled from the assignment of the small blocks.
Although we will show that the side-chain packing problem is still
{\it NP}-hard,we can achieve a tree-decomposition based globally
optimal algorithm with time complexity of $O(Nn_{rot}^{tw+1})$
and several polynomial-time approximation schemes (PTAS),
where $N$ is the length of the protein sequence,
$n_{rot}$ the average number of rotamers for each residue,
and $tw=O(N^{2/3}\log{N})$ the treewidth of the protein structure
graph. Experimental results indicate that after Goldstein dead-end
elimination is conducted, $n_{rot}$ is equal to 4 and $tw$ is equal to
3 or 4 most of the time. Based on the globally optimal algorithm,
we developed a protein side-chain assignment program TreePack,
which runs up to 90 times faster than SCWRL 3.0, a widely-used side-
chain packing program, on some large test proteins in the SCWRL
benchmark database and an average of five times faster on all the test
proteins in this database. There are also some real-world instances
that TreePack can solve but that SCWRL 3.0 cannot.
The TreePack program is available at |