Access Restriction

Author Xu, Jinbo ♦ Berger, Bonnie
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2006
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Protein side-chain packing ♦ Approximate algorithm ♦ Polynomial-time approximation scheme ♦ Tree decomposition
Abstract This article 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 $\textit{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 $\textit{N}$ is the number of residues contained in the protein, $n_{rot}$ the average number of rotamers for each residue, and $\textit{tw}$ = $O(N^{2/3}$ log $\textit{N})$ the treewidth of the protein structure graph. Experimental results indicate that after Goldstein dead-end elimination is conducted, $n_{rot}$ is very small and $\textit{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
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2006-07-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 53
Issue Number 4
Page Count 25
Starting Page 533
Ending Page 557

Open content in new tab

   Open content in new tab
Source: ACM Digital Library