Algorithms for prediction of MHC binders using mathematical optimization models

预测抗原肽与主要组织相容性复合体(MHC)II类分子的结合能力在疫苗研制中具有重要意义。这种预测的一个关键是最大化从结合能力获得的信息的熵。这个问题可以表示为比率之和的最大化问题。本文针对这类线性比率求和问题，提出了两种利用线性松弛的算法，即一般比率求和问题的近似算法。在数值实验中得到了以下结果：1)新算法的平均CPU时间是现有算法的12%。2)该算法能在不到14分钟的时间内找到60个比值之和问题的最优解，数值结果表明该算法明显优于已有的算法。

Prediction of the binding ability of antigen peptides to major histocompatibility complex (MHC) class II molecules plays an important role in vaccine development. A key to such prediction is to maximize the entropy of information obtained from the the binding ability. This problem can be formulated as a maximization of the Sum of Ratios Problem. In this study, two kinds of algorithms which use linear relaxation were proposed to such a Sum of Linear Ratios Problem, that is an approximation of general Sum of Ratios Problem. The following results have been obtained in the numerical experiments.1) The new algorithm takes a 12% CPU time of the existing methods on average. 2) The proposed algorithm finds an optimal solution of the Sum of Linear Ratios Problem with 60 ratios in about less than 14 minutes (CPU time).These numerical results indicate that the proposed algorithms are much superior to theses existing algorithms.