iTreePack: Protein Complex Side-Chain Packing by Dual Decomposition

Jian Peng, Raghavendra Hosur, Bonnie Berger, Jinbo XuarXiv 2015 · DOI · arXiv

Abstract

Protein side-chain packing is a critical component in obtaining the 3D coordinates of a structure and drug discovery. Single-domain protein side-chain packing has been thoroughly studied. A major challenge in generalizing these methods to protein complexes is that they, unlike monomers, often have very large treewidth, and thus algorithms such as TreePack cannot be directly applied. To address this issue, SCWRL4 treats the complex effectively as a monomer, heuristically excluding weak interactions to decrease treewidth; as a result, SCWRL4 generates poor packings on protein interfaces. To date, few side-chain packing methods exist that are specifically designed for protein complexes. In this paper, we introduce a method, iTreePack, which solves the side-chain packing problem for complexes by using a novel combination of dual decomposition and tree decomposition. In particular, iTreePack overcomes the problem of large treewidth by decomposing a protein complex into smaller subgraphs and novelly reformulating the complex side-chain packing problem as a dual relaxation problem; this allows us to solve the side-chain packing of each small subgraph separately using tree-decomposition. A projected subgradient algorithm is applied to enforcing the consistency among the side-chain packings of all the small subgraphs. Computational results demonstrate that our iTreePack program outperforms SCWRL4 on protein complexes. In particular, iTreePack places side-chain atoms much more accurately on very large complexes, which constitute a significant portion of protein-protein interactions. Moreover, the advantage of iTreePack over SCWRL4 increases with respect to the treewidth of a complex. Even for monomeric proteins, iTreePack is much more efficient than SCWRL and slightly more accurate.

Introduction

In structural biology, side-chain packing is the task of determining the 3D coordinates of a protein's side-chain atoms given its backbone structure. While this problem is well-solved for single-domain proteins (monomers), protein complexes—where multiple proteins interact—present a significant computational hurdle.

The primary difficulty lies in the treewidth of the residue interaction graph. Treewidth measures a graph's topological complexity. For monomers, this value is typically low (under 20), allowing for efficient solutions via tree decomposition. However, protein complexes are often highly "tangled," leading to high treewidths that cause standard algorithms to become computationally prohibitive. Existing tools like SCWRL4 address this by heuristically ignoring "weak" interactions to artificially lower the treewidth. While this saves compute time, it frequently results in poor accuracy at the protein-protein interface—the region most critical for drug discovery and binding analysis.

Methods

iTreePack introduces a "divide and conquer" strategy that combines dual decomposition with tree decomposition to handle high-treewidth complexes without sacrificing interaction data.

  1. Complex Decomposition via Vertex Duplication: The complex interaction graph is decomposed into smaller subgraphs. Residues at the interface are duplicated: one copy remains with the individual monomer subgraph, and another is assigned to a separate "interface graph."
  2. Dual Decomposition (Lagrangian Relaxation): The packing problem is reformulated as a dual relaxation. Initially, duplicated residues are permitted to have different configurations in their respective subgraphs.
  3. Tree Decomposition: Because the resulting subgraphs (monomers and interfaces) have significantly lower treewidth than the original complex, they can be solved optimally and efficiently using standard tree decomposition.
  4. Consistency Enforcement: A projected subgradient algorithm is used to iteratively penalize differences between duplicated residues. Over 10–20 iterations, the subproblems are forced into a consistent, globally near-optimal solution.
Decomposition of a protein complex interaction graph into subgraphs via vertex duplication.

Additionally, iTreePack incorporates Dead-End Elimination (DEE) to prune the search space by removing rotamers (side-chain orientations) that are mathematically guaranteed not to be part of the optimal solution.

Datasets

The performance of iTreePack was evaluated using two primary datasets:

  • Protein Complex Benchmark: A set of 547 protein complexes from the 3Dcomplex database, ranging from 202 to 3,084 residues and including up to 20 constituent monomers.
  • Monomer Dataset: The standard SCWRL4 dataset of 379 monomeric proteins, used to benchmark efficiency on simpler structures.

Key Results

iTreePack demonstrates significant improvements over the industry standard, SCWRL4, particularly as structural complexity increases.

  • Superior Accuracy on Large Complexes: On 122 complexes with high treewidth (>20), iTreePack outperformed SCWRL4 in 75% of cases.
  • Interface Performance: iTreePack correctly predicted an average of 5.66 more interfacial residues per complex than SCWRL4, highlighting the benefit of maintaining interface interactions.
  • Scalability: The algorithm successfully processed the massive 1jnb complex (3,084 residues, treewidth 136) by decomposing it into subgraphs with manageable treewidths between 17 and 21.
  • Efficiency: On the monomer dataset, iTreePack was 4 times faster than SCWRL4 (1.8s vs 7.6s on average), showing that dual decomposition is a more efficient way to navigate the energy landscape even for simpler proteins.
Performance comparison between iTreePack and SCWRL4 across different treewidth ranges.

Discussion and Conclusion

The success of iTreePack underscores that the computational bottleneck in side-chain packing is driven by connectivity (treewidth) rather than just protein size. By mathematically separating intra-protein and inter-protein interactions, iTreePack maintains physical integrity at the interface, leading to more realistic models with fewer steric clashes.

Despite these gains, a gap remains between the packing accuracy of monomers and complexes. Future work may involve developing specialized rotamer libraries for protein interfaces and refining energy functions to better capture the unique physics of protein-protein binding. Nevertheless, iTreePack represents a significant step forward in modeling the complex structural interactions vital for modern drug discovery.

Summary updated

Abstract

Protein side-chain packing is a critical component in obtaining the 3D coordinates of a structure and drug discovery. Single-domain protein side-chain packing has been thoroughly studied. A major challenge in generalizing these methods to protein complexes is that they, unlike monomers, often have very large treewidth, and thus algorithms such as TreePack cannot be directly applied. To address this issue, SCWRL4 treats the complex effectively as a monomer, heuristically excluding weak interactions to decrease treewidth; as a result, SCWRL4 generates poor packings on protein interfaces. To date, few side-chain packing methods exist that are specifically designed for protein complexes. In this paper, we introduce a method, iTreePack, which solves the side-chain packing problem for complexes by using a novel combination of dual decomposition and tree decomposition. In particular, iTreePack overcomes the problem of large treewidth by decomposing a protein complex into smaller subgraphs and novelly reformulating the complex side-chain packing problem as a dual relaxation problem; this allows us to solve the side-chain packing of each small subgraph separately using tree-decomposition. A projected subgradient algorithm is applied to enforcing the consistency among the side-chain packings of all the small subgraphs. Computational results demonstrate that our iTreePack program outperforms SCWRL4 on protein complexes. In particular, iTreePack places side-chain atoms much more accurately on very large complexes, which constitute a significant portion of protein-protein interactions. Moreover, the advantage of iTreePack over SCWRL4 increases with respect to the treewidth of a complex. Even for monomeric proteins, iTreePack is much more efficient than SCWRL and slightly more accurate.
BibTeX
@misc{peng2015itreepack,
  author = {Jian Peng and Raghavendra Hosur and Bonnie Berger and Jinbo Xu},
  title = {{iTreePack: Protein Complex Side-Chain Packing by Dual Decomposition}},
  year = {2015},
  eprint = {1504.05467},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1504.05467},
}

Loading related content...

Figure