This paper proposes a tree decomposition of protein structures, which can be used to efficiently solve two key subproblems of protein structure prediction: protein threading for backbone prediction and protein side-chain prediction. To develop a unified tree-decomposition based approach to these two subproblems, we model them as a geometric neighborhood graph labeling problem. Theoretically, we can have a low-degree polynomial time algorithm to decompose a geometric neighborhood graph G = (V, E) into components with size 0( \geqslant \left| V \right|^{\frac{2}{3}} \log \left| V \right|). The computational complexity of the tree-decomposition based graph labeling algorithms is 0(\left| V \right|\Delta ^{tw + 1}) where Δ is the average number of possible labels for each vertex and tw( = 0(\left| V \right|^{\frac{2}{3}} \log \left| V \right|)) the tree width of G. Empirically, tw is very small and the tree-decomposition method can solve these two problems very efficiently. This paper also compares the computational efficiency of the tree-decomposition approach with the linear programming approach to these two problems and identifies the condition under which the tree-decomposition approach is more efficient than the linear programming approach. Experimental result indicates that the tree-decomposition approach is more efficient most of the time.