Algorithms for prediction of MHC binders using mathematical optimization models

预测抗原肽与主要组织相容性复合体（MHC）II类分子的结合能力在疫苗开发中起着重要作用。这种预测的关键是最大化从结合能力获得的信息的熵。这个问题可以用公式表示为比率和问题的最大化。本文针对这类线性比率和问题，即一般比率和问题的近似问题，提出了两种线性松弛算法。数值实验结果表明：（1）新算法的计算时间平均为现有算法的12%。2)该算法在不到14分钟（CPU时间）的时间内找到了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.