Optimization of memory use of fragment extension-based protein–ligand docking with an original fast minimum cost flow algorithm. (June 2018)

• Record Type: Journal Article
• Authors: Yanagisawa, Keisuke; Komine, Shunta; Kubota, Rikuto; Ohue, Masahito; Akiyama, Yutaka
• Is Part Of: Computational biology and chemistry. Volume 74(2018)
• Page Start: 399
• Page End: 406
• Publication Date: 2018-06
• Subjects: Virtual screening -- Protein–ligand docking -- Weighted offline cache problem -- Minimum cost flow problem; Chemistry -- Data processing -- Periodicals; Biology -- Data processing -- Periodicals; Biochemistry -- Data processing; Biology -- Data processing; Molecular biology -- Data processing; Periodicals; Electronic journals; 542.85
• DOI: 10.1016/j.compbiolchem.2018.03.013
• Languages: English
• ISSNs: 1476-9271

Abstract

Graphical abstract: Highlights: In drug discovery research, protein–ligand docking is widely used. Existing docking tools cannot reuse fragment results efficiently. We formulate optimization of fragment reuse as a minimum cost flow (MCF) problem. We propose a fast, exact MCF algorithm specialized for this problem. It was 7.5–7.8 times faster than existing algorithms for real compound data. Abstract: 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.