New enumeration algorithm for protein structure comparison and classification

作者：Ashby Cody; Johnson Daniel; Walker Karl; Kanj Iyad A; Xia Ge^*; Huang Xiuzhen

来源：BMC Genomics, 2013, 14(S2): S1.

DOI：10.1186/1471-2164-14-S2-S1

Background: Protein structure comparison and classification is an effective method for exploring protein structure-function relations. This problem is computationally challenging. Many different computational approaches for protein structure comparison apply the secondary structure elements (SSEs) representation of protein structures.
Results: We study the complexity of the protein structure comparison problem based on a mixed-graph model with respect to different computational frameworks. We develop an effective approach for protein structure comparison based on a novel independent set enumeration algorithm. Our approach (named: ePC, efficient enumeration-based Protein structure Comparison) is tested for general purpose protein structure comparison as well as for specific protein examples. Compared with other graph-based approaches for protein structure comparison, the theoretical running-time O(1.47(rn)n(2)) of our approach ePC is significantly better, where n is the smaller number of SSEs of the two proteins, r is a parameter of small value.
Conclusion: Through the enumeration algorithm, our approach can identify different substructures from a list of high-scoring solutions of biological interest. Our approach is flexible to conduct protein structure comparison with the SSEs in sequential and non-sequential order as well. Supplementary data of additional testing and the source of ePC will be available at http://bioinformatics.astate.edu/.

• 出版日期2013-2-15