A New Graph Theoretic Approach for Protein Threading

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.