Protein threading by linear programming: theoretical analysis and computational results

Protein threading by linear programming: theoretical analysis and computational results

0.00 Avg rating0 Votes
Article ID: iaor20051787
Country: Netherlands
Volume: 8
Issue: 4
Start Page Number: 403
End Page Number: 418
Publication Date: Dec 2004
Journal: Journal of Combinatorial Optimization
Authors: , ,
Keywords: programming: integer
Abstract:

In a previous paper, 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 relaxation 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.

Reviews

Required fields are marked *. Your email address will not be published.