title: A tree-decomposition approach to protein structure prediction.
abstract: 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 O(|V|((2/3))log|V|). The computational complexity of the tree-decomposition based graph labeling algorithms is O(|V|Delta(tw+1)) where Delta is the average number of possible labels for each vertex and tw( = O(|V|((2/3))log|V|)) 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.
authors.affiliation: Department of Mathematics and CSAIL, Massassachusetts Institute of Technology, Cambridge, MA 02139, USA. j3xu@theory.csail.mit.edu
authors.forename: Jinbo
authors.initials: J
authors.lastname: Xu
authors.forename: Feng
authors.initials: F
authors.lastname: Jiao
authors.forename: Bonnie
authors.initials: B
authors.lastname: Berger
mesh_terms: D000465:Algorithms; D000595:Amino Acid Sequence; D003198:Computer Simulation; D008956:Models, Chemical; D008958:Models, Molecular; D008969:Molecular Sequence Data; D011487:Protein Conformation; D011506:Proteins / Q000737:chemistry* / Q000648:ultrastructure*; D020539:Sequence Analysis, Protein / Q000379:methods*
chemical_list: D011506:Proteins