This paper proposes a novel tree decomposition based sidechain assignment
algorithm, which can obtain the globally optimal solution of the
sidechain packing problem very efficiently.
Theoretically, the computational complexity of this algorithm
is $O((N+M)n_{rot}^{tw+1})$ where $N$ is the number of residues in the protein,
$M$ the number of interacting residue pairs, $n_{rot}$ the average number
of rotamers for each residue and $tw (=O(N^{\frac{2}{3}}\log{N}) )$ the tree width of the residue
interaction graph. Based on this algorithm, we have developed a sidechain
prediction program SCATD (Side Chain Assignment via Tree Decomposition).
Experimental results show that after the Goldstein DEE is conducted,
$n_{rot}$ is around 3.5, $tw$ is only 3 or 4 for most of the test proteins
in the SCWRL benchmark and less than 10 for all the test proteins.
SCATD runs up to 90 times faster than SCWRL 3.0 on some large proteins in
the SCWRL benchmark and achieves an average of five times faster speed on
all the test proteins. If only the postDEE stage is taken into
consideration, then our treedecomposition based energy minimization algorithm
is more than 200 times faster than that in SCWRL 3.0 on some large
proteins. SCATD is freely available for academic research upon request.
