An Algorithm for Simultaneous Backbone Threading and Side-Chain Packing |
| |
Authors: | Guojun Li Zhijie Liu Jun-tao Guo Ying Xu |
| |
Affiliation: | (1) School of Mathematics and Systems Sciences, Shandong University, Jinan 250100, People's Republic of China;(2) Department of Biochemistry and Molecular Biology, The University of Georgia, GA 30602, USA |
| |
Abstract: | To utilize fully all available information in protein structure prediction, including both backbone and side-chain structures,
we present a novel algorithm for solving a generalized threading problem. In this problem we consider simultaneous backbone
threading and side-chain packing during the process of a protein structure prediction. For a given query protein sequence
and a template structure, our goal is to find a threading alignment between the query sequence and the template structure,
along with a rotamer assignment for each side-chain of the query protein, which optimizes an energy function that combines
a backbone threading energy and a side-chain packing energy. This highly computationally challenging problem is solved through
first formulating this problem as a graph-based optimization problem. Various graph-theoretic techniques are employed to achieve
the computational efficiency to make our algorithm practically useful, which takes advantage of a number of special properties
of the graph representing this generalized threading problem. The overall framework of our algorithm is a dynamic programming
algorithm implemented on an optimal tree decomposition of the graph representation of our problem. By using various additional
heuristic techniques such as dead-end elimination, we have demonstrated that our algorithm can solve a generalized threading
problem within a practically acceptable amount of time and space, the first of its kind. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|