### Fast and accurate algorithms for protein side-chain packingFast and accurate algorithms for protein side-chain packing

Access Restriction
Subscribed

 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 http://ttic.uchicago.edu/~jinbo/TreePack.htm. 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

Source: ACM Digital Library