Optimization of memory use of fragment extension-based protein-ligand docking with an original fast minimum cost flow algorithm

被引:1
作者
Yanagisawa, Keisuke [1 ,2 ]
Komine, Shunta [1 ,2 ]
Kubota, Rikuto [1 ]
Hue, Masahito [1 ,3 ]
Akiyama, Yutaka [1 ,2 ,3 ]
机构
[1] Tokyo Inst Technol, Sch Comp, Dept Comp Sci, Meguro Ku, W8-76 2-12-1 Ookayama, Tokyo 1528550, Japan
[2] Tokyo Inst Technol, Educ Acad Computat Life Sci ACLS, Midori Ku, J3-141 4259 Nagatsutacho, Yokohama, Kanagawa 2268501, Japan
[3] Tokyo Inst Technol, Adv Computat Drug Discovery Unit ACDD, Inst Innovat Res, Midori Ku, 4259 Nagatsutacho, Yokohama, Kanagawa 2268501, Japan
关键词
Virtual screening; Protein-ligand docking; Weighted offline cache problem; Minimum cost flow problem;
D O I
10.1016/j.compbiolchem.2018.03.013
中图分类号
Q [生物科学];
学科分类号
07 ; 0710 ; 09 ;
摘要
The need to accelerate large-scale protein-ligand docking in virtual screening against a huge compound database led researchers to propose a strategy that entails memorizing the evaluation result of the partial structure of a compound and reusing it to evaluate other compounds. However, the previous method required frequent disk accesses, resulting in insufficient acceleration. Thus, more efficient memory usage can be expected to lead to further acceleration, and optimal memory usage could be achieved by solving the minimum cost flow problem. In this research, we propose a fast algorithm for the minimum cost flow problem utilizing the characteristics of the graph generated for this problem as constraints. The proposed algorithm, which optimized memory usage, was approximately seven times faster compared to existing minimum cost flow algorithms. (C) 2018 The Authors. Published by Elsevier Ltd. This is an open access article under the CC BY license.
引用
收藏
页码:399 / 406
页数:8
相关论文
共 15 条
  • [1] [Anonymous], 2003, Linear programming 2: theory and extensions
  • [2] [Anonymous], 1991, THESIS
  • [3] [Anonymous], 1960, J. Oper. Res. Soc. Jpn.
  • [4] [Anonymous], 8 MIT OP RES CTR
  • [5] The Design of Competitive Online Algorithms via a Primal Dual Approach
    Buchbinder, Niv
    Naor, Joseph
    [J]. FOUNDATIONS AND TRENDS IN THEORETICAL COMPUTER SCIENCE, 2007, 3 (2-3): : 93 - 263
  • [6] Busacker R. G., 1960, 15 J HOPK U OP RES C
  • [7] LEMON - an Open Source C++ Graph Template Library
    Dezso, Balazs
    Juttner, Alpar
    Kovacs, Peter
    [J]. ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 2011, 264 (05) : 23 - 45
  • [8] Glide: A new approach for rapid, accurate docking and scoring. 1. Method and assessment of docking accuracy
    Friesner, RA
    Banks, JL
    Murphy, RB
    Halgren, TA
    Klicic, JJ
    Mainz, DT
    Repasky, MP
    Knoll, EH
    Shelley, M
    Perry, JK
    Shaw, DE
    Francis, P
    Shenkin, PS
    [J]. JOURNAL OF MEDICINAL CHEMISTRY, 2004, 47 (07) : 1739 - 1749
  • [9] FASTER SCALING ALGORITHMS FOR NETWORK PROBLEMS
    GABOW, HN
    TARJAN, RE
    [J]. SIAM JOURNAL ON COMPUTING, 1989, 18 (05) : 1013 - 1036
  • [10] ZINC: A Free Tool to Discover Chemistry for Biology
    Irwin, John J.
    Sterling, Teague
    Mysinger, Michael M.
    Bolstad, Erin S.
    Coleman, Ryan G.
    [J]. JOURNAL OF CHEMICAL INFORMATION AND MODELING, 2012, 52 (07) : 1757 - 1768