NDLI: Fast and accurate algorithms for protein side-chain packing

Content Provider	ACM Digital Library
Author	Xu, Jinbo Berger, Bonnie
Copyright Year	2006
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.
Starting Page	533
Ending Page	557
Page Count	25
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/1162349.1162350
Journal	Journal of the ACM (JACM)
Volume Number	53
Issue Number	4
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2006-07-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Protein side-chain packing Approximate algorithm Polynomial-time approximation scheme Tree decomposition
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Information Systems Control and Systems Engineering Artificial Intelligence Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Fast and accurate algorithms for protein side-chain packing (2006)

Fast and accurate algorithms for protein side-chain packing (2006)

Fast and accurate algorithms for protein side-chain packing (2006)

A quasi-polynomial time approximation scheme for minimum weight triangulation

On the Sum-of-Squares algorithm for bin packing

Fast Probabilistic Algorithms for Verification of Polynomial Identities

A Convergent Algorithm for Solving Polynomial Algorithms

Minimum cuts in near-linear time

Polynomial-time algorithm for the orbit problem

Fast and accurate algorithms for protein side-chain packing

Similar Documents

Fast and accurate algorithms for protein side-chain packing (2006)

Fast and accurate algorithms for protein side-chain packing (2006)

Fast and accurate algorithms for protein side-chain packing (2006)

A quasi-polynomial time approximation scheme for minimum weight triangulation

On the Sum-of-Squares algorithm for bin packing

Fast Probabilistic Algorithms for Verification of Polynomial Identities

A Convergent Algorithm for Solving Polynomial Algorithms

Minimum cuts in near-linear time

Polynomial-time algorithm for the orbit problem

Fast and accurate algorithms for protein side-chain packing