Affiliations: [a] School of Electronics and Information Science, Jiangsu University of Science and Technology, Mengxi Road 2, Zhenjiang, Jiangsu 212003, China. [email protected] | [b] Department of Information Technology and Computer Science, Clayton State University, Morrow, GA 30260, USA. [email protected] | [c] Department of Biochemistry and Molecular Biology, University of Georgia, Athens, GA 30602, USA. [email protected], [email protected]
Correspondence:
[*]
Address for correspondence: School of Electronics and Information Science, Jiangsu University of Science and Technology, Mengxi Road 2, Zhenjiang, Jiangsu 212003, China.
Abstract: In this paper, we develop a novel graph theoretic approach for protein threading. In order to perform the protein sequence-structure alignment in threading both efficiently and accurately, we develop a graph model to describe the tertiary structure of a protein family and the alignment between a sequence and a family can be efficiently computed with a dynamic programming algorithm when the tree width of the graph model is a small integer. Our experiments show that this new approach is significantly faster than existing tools for threading and can achieve comparable prediction accuracy.
Keywords: protein threading, graph theoretic approach, dynamic programming
