Linear programming based approach to the derivation of a contact potential for protein threading

This paper proposes a novel method of deriving a contact potential (a pair score function) for protein threading. In this method, the constraint that the score of the native threading is minimum over all possible threadings is expressed in a form of linear inequalities, and then parameters defining the contact potential are determined by applying a program package of linear programming. The most important advantage of this method over the previous methods is that this method can learn a score function from a small number of training data. The proposed method was evaluated using Lathrop and Smith's algorithm for finding optimal threadings and was shown to be effective for computing nearly correct threadings.