Protein Threading by Linear Programming: Theoretical Analysis and Computational Results |
| |
Authors: | Jinbo Xu Ming Li Ying Xu |
| |
Affiliation: | (1) School of Computer Science, University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada;(2) Department of Biochemistry, University of Georgia, Athens, GA 30602-7229, USA |
| |
Abstract: | In a previous paper (Xu, Li, Kim, and Xu, Journal of Bioinformatics and Computational Biology, vol. 1, no. 1, pp. 95–117, 2003), we have used an integer programming approach to implement a protein threading program RAPTOR for protein 3D structure prediction, based on the threading model treating pairwise contacts rigorously and allowing variable gaps. We have solved the integer program by the canonical branch-and-bound method. In this paper we present a branch-and-cut method, a careful theoretical analysis of our formulation and why our approach is so effective. The result of cutting plane analysis is that two types of well-known cuts for this problem are already implied in the constraint set, which provides us some intuition that our formulation would be very effective. Experimental results show that for about 99 percent of real threading instances, the linear relaxations of their integer programs solve to integral optimal solutions directly. For the rest one percent of real instances, the integral solutions can be obtained with only several branch nodes. Experimental results also show that no special template or sequence features result in more possibilities of fractional solutions. This indicates that extra effort to seek for cutting planes to strengthen the existing formulation is unnecessary. |
| |
Keywords: | protein threading integer program branch-and-cut cutting plane CAFASP |
本文献已被 SpringerLink 等数据库收录! |
|