Algorithms for solving the sum-of-ratios problem using polynomialrelaxations and its application to sequence alignment

使用多项式松弛求解比率和问题的算法及其在序列比对中的应用

• 批准号: 19510135
• 负责人: SHI Jianming
• 金额: $ 0.83万
• 依托单位: Muroran Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2007
• 资助国家: 日本
• 起止时间: 2007 至 2008
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-19510135/
• 关键词: 最適化; 分数和情報学計画; 生体情報学; Mathematical Programming; ACO; ACS; Sequence Multiple Alignment; Ant Algorithm; Sum of ratios problem; Fractional Programming; Motif finding; NP-hard problem; 数理計画; 分数和計画; モチーフ; バイオインフォマティクス

生体生命における情報の中に共通配列(モチーフ)を探し出すことを研究の目的である. モチーフを評価するため, 情報量に基き, ある種の分数和を最大化することが必要である. 本研究はこのような既存の分数和を最大にする計算方法(アルゴリズム)を研究し, 2005に発表されたモチーフ抽出アルゴリズムを大幅改良した. 数値実験の結果では,計算速度を2900倍に速くすることに成功した.

The common arrangement of information in living organisms is explored for the purpose of research. The amount of information is based on the evaluation of the score and the maximization of the score. This paper studies the calculation method of the existing fraction and the maximum of the existing fraction, and greatly improves the calculation method of the existing fraction and the maximum of the existing fraction. The calculation speed is 2900 times faster than that of the original calculation speed.

项目成果

ACOを用いたモチーフ抽出アルゴリズムに関する研究

基于ACO的基序提取算法研究

• 发表时间: 2007
• 期刊: IPSJ SIG Technical Report 2007-BIO-11
• 作者: Ai Mikami/Jianming Shi;三上あい/施建明
• 通讯作者: 三上あい/施建明

A Modified Algorithm for Sequence Alignment Using Ant Colony System

• DOI: 10.2197/ipsjtbio.2.63
• 发表时间: 2009-12
• 期刊: Ipsj Transactions on Bioinformatics
• 作者: A. Mikami;Jianming Shi

Optmization of Sum-Of-Ratios Problem and its Applications

比率和问题的优化及其应用

• 发表时间: 2007
• 作者: Ai Mikami/Jianming Shi;三上あい/施建明;Jianming Shi
• 通讯作者: Jianming Shi