Algorithms for prediction of MHC binders using mathematical optimization models

使用数学优化模型预测 MHC 结合物的算法

• 批准号: 23510152
• 负责人: SHI Jianming
• 金额: $ 2万
• 依托单位: Tokyo University of Science (2013)Muroran Institute of Technology (2011-2012)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2011
• 资助国家: 日本
• 起止时间: 2011 至 2013
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-23510152/
• 关键词: 分数計和計画問題; 数理最適化; アルゴリズム; 遺伝子機能予測; 主要組織適合抗原(MHC)クラスII; 分数和計画問題; オペレーションズリサーチ; 数理計画; MHC クラス II; ペプチド結合予測

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.

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

项目成果

A linear relaxation algorithm with lower dimension for solving the sum of linear ratios problem

求解线性比率和问题的低维线性松弛算法

• 发表时间: 2013
• 期刊: Operations Research Letters
• 影响因子: 1.1
• 作者: 大堀;木下;加地;西川;J. G. Carlsson and J. Shi
• 通讯作者: J. G. Carlsson and J. Shi

Algorithms for the sum of linear ratios program with lower dimension and related problems

低维线性比率求和程序的算法及相关问题

• 发表时间: 2013
• 作者: 江口 彰;山田 秀;加地;Y. Hu and J.Shi
• 通讯作者: Y. Hu and J.Shi

The LP-Newton method for standard form linear programming problems

标准形式线性规划问题的 LP-Newton 方法

• 发表时间: 2013
• 期刊: Operations Research Letters
• 影响因子: 1.1
• 作者: T. Kitahara;S. Mizuno and J. Shi
• 通讯作者: S. Mizuno and J. Shi

A new algorithm for linear programming, INFORMS

线性规划的新算法 INFORMS

• 发表时间: 2012
• 作者: 八木;加地;J. Shi
• 通讯作者: J. Shi

Algorithms for the Sum of Linear Ratios Problem with Lower Dimension and Related Problems

低维线性比和问题的算法及相关问题

• 发表时间: 2013
• 作者: 大堀;木下;加地;西川;Toshio Kimura and Naoki Makimoto;Yongwen Hu and Jianming Shi
• 通讯作者: Yongwen Hu and Jianming Shi