Research article

Computational enzymology for degradation of chemical warfare agents: promising technologies for remediation processes

  • Chemical weapons are a major worldwide problem, since they are inexpensive, easy to produce on a large scale and difficult to detect and control. Among the chemical warfare agents, we can highlight the organophosphorus compounds (OP), which contain the phosphorus element and that have a large number of applications. They affect the central nervous system and can lead to death, so there are a lot of works in order to design new effective antidotes for the intoxication caused by them. The standard treatment includes the use of an anticholinergic combined to a central nervous system depressor and an oxime. Oximes are compounds that reactivate Acetylcholinesterase (AChE), a regulatory enzyme responsible for the transmission of nerve impulses, which is one of the molecular targets most vulnerable to neurotoxic agents. Increasingly, enzymatic treatment becomes a promising alternative; therefore, other enzymes have been studied for the OP degradation function, such as phosphotriesterase (PTE) from bacteria, human serum paraoxonase 1 (HssPON1) and diisopropyl fluorophosphatase (DFPase) that showed significant performances in OP detoxification. The understanding of mechanisms by which enzymes act is of extreme importance for the projection of antidotes for warfare agents, and computational chemistry comes to aid and reduce the time and costs of the process. Molecular Docking, Molecular Dynamics and QM/MM (quantum-mechanics/molecular-mechanics) are techniques used to investigate the molecular interactions between ligands and proteins.

    Citation: Alexandre A. de Castro, Letícia C. Assis, Daniela R. Silva, Silviana Corrêa, Tamiris M. Assis, Giovanna C. Gajo, Flávia V. Soares, Teodorico C. Ramalho. Computational enzymology for degradation of chemical warfare agents: promising technologies for remediation processes[J]. AIMS Microbiology, 2017, 3(1): 108-135. doi: 10.3934/microbiol.2017.1.108

    Related Papers:

    [1] Xue Li, Lei Wang . Application of improved ant colony optimization in mobile robot trajectory planning. Mathematical Biosciences and Engineering, 2020, 17(6): 6756-6774. doi: 10.3934/mbe.2020352
    [2] Shaofeng Yan, Guohui Zhang, Jinghe Sun, Wenqiang Zhang . An improved ant colony optimization for solving the flexible job shop scheduling problem with multiple time constraints. Mathematical Biosciences and Engineering, 2023, 20(4): 7519-7547. doi: 10.3934/mbe.2023325
    [3] Teng Fei, Xinxin Wu, Liyi Zhang, Yong Zhang, Lei Chen . Research on improved ant colony optimization for traveling salesman problem. Mathematical Biosciences and Engineering, 2022, 19(8): 8152-8186. doi: 10.3934/mbe.2022381
    [4] Xiangyang Ren, Xinxin Jiang, Liyuan Ren, Lu Meng . A multi-center joint distribution optimization model considering carbon emissions and customer satisfaction. Mathematical Biosciences and Engineering, 2023, 20(1): 683-706. doi: 10.3934/mbe.2023031
    [5] Tian Xue, Liu Li, Liu Shuang, Du Zhiping, Pang Ming . Path planning of mobile robot based on improved ant colony algorithm for logistics. Mathematical Biosciences and Engineering, 2021, 18(4): 3034-3045. doi: 10.3934/mbe.2021152
    [6] Kaidong Yang, Peng Duan, Huishan Yu . An improved genetic algorithm for solving the helicopter routing problem with time window in post-disaster rescue. Mathematical Biosciences and Engineering, 2023, 20(9): 15672-15707. doi: 10.3934/mbe.2023699
    [7] Chikun Gong, Yuhang Yang, Lipeng Yuan, Jiaxin Wang . An improved ant colony algorithm for integrating global path planning and local obstacle avoidance for mobile robot in dynamic environment. Mathematical Biosciences and Engineering, 2022, 19(12): 12405-12426. doi: 10.3934/mbe.2022579
    [8] Liwei Yang, Lixia Fu, Ping Li, Jianlin Mao, Ning Guo, Linghao Du . LF-ACO: an effective formation path planning for multi-mobile robot. Mathematical Biosciences and Engineering, 2022, 19(1): 225-252. doi: 10.3934/mbe.2022012
    [9] Yuzhuo Shi, Huijie Zhang, Zhisheng Li, Kun Hao, Yonglei Liu, Lu Zhao . Path planning for mobile robots in complex environments based on improved ant colony algorithm. Mathematical Biosciences and Engineering, 2023, 20(9): 15568-15602. doi: 10.3934/mbe.2023695
    [10] Xiang Gao, Yipeng Zhang . Advancing remote consultation through the integration of blockchain and ant colony algorithm. Mathematical Biosciences and Engineering, 2023, 20(9): 16886-16912. doi: 10.3934/mbe.2023753
  • Chemical weapons are a major worldwide problem, since they are inexpensive, easy to produce on a large scale and difficult to detect and control. Among the chemical warfare agents, we can highlight the organophosphorus compounds (OP), which contain the phosphorus element and that have a large number of applications. They affect the central nervous system and can lead to death, so there are a lot of works in order to design new effective antidotes for the intoxication caused by them. The standard treatment includes the use of an anticholinergic combined to a central nervous system depressor and an oxime. Oximes are compounds that reactivate Acetylcholinesterase (AChE), a regulatory enzyme responsible for the transmission of nerve impulses, which is one of the molecular targets most vulnerable to neurotoxic agents. Increasingly, enzymatic treatment becomes a promising alternative; therefore, other enzymes have been studied for the OP degradation function, such as phosphotriesterase (PTE) from bacteria, human serum paraoxonase 1 (HssPON1) and diisopropyl fluorophosphatase (DFPase) that showed significant performances in OP detoxification. The understanding of mechanisms by which enzymes act is of extreme importance for the projection of antidotes for warfare agents, and computational chemistry comes to aid and reduce the time and costs of the process. Molecular Docking, Molecular Dynamics and QM/MM (quantum-mechanics/molecular-mechanics) are techniques used to investigate the molecular interactions between ligands and proteins.


    The winner determination problem (WDP) in combinatorial auction aims to determine a bid-winning scheme according to the combination of items submitted by various bidders as well as their bids. The object of WDP is to maximize the revenue of auctioneers, where the revenue is measured by the total price of the selected bids. Compared with traditional auction mechanisms, WDP can improve the efficiency of the auction process and reduce the number of failure bids [1]. WDP is widely used in cloud computing [2], online reverse auctions [3,4], spectrum license sales by America's Federal Communications Commission (FCC)*, e-commerce [5], wireless network [6], production management [7], game theory [8], and multi-agent system resource allocation [9,10], etc. Solving the winner determination problem effectively can improve the utilization of items, which is conducive to sustainable development. However, the process of determining the winning criterion is NP-hard problem [11]. How to solve WDP effectively has become a hot topic in the field of combinatorial optimization.

    *http://wireless.fcc.gov/auctions

    Nowadays, the memetic algorithm which integrates the population-based method and the heuristic or meta-heuristic method performs well on many combinatorial optimization problems [12,13,14,15]. The population-based methods, which can expand the search space of the problem, include genetic algorithm [16], ant colony algorithm [17], bee colony algorithm colony [18], and so on.

    Among the population-based methods, the ant colony algorithm (ACO), which uses the pheromone model and heuristic information of the problem to construct solutions in a probabilistic way [19]. Pheromone trails are the result of a learning mechanism that tries to identify the solution components that, when appropriately combined, lead to high-quality solutions. However, as well known, ACO and other population-based methods have strong robustness, but its convergence speed is slow and is easy to fall into the local optima.

    Therefore, in many combinatorial problems, the heuristic or meta-heuristic methods are essential for obtaining competitive solutions, which can be used to prevent the search from premature convergence, including local search [20], tabu search [21], and simulated annealing [22], etc. Tabu search (TS) is a widely studied heuristic method for its distinguishing features of adaptive memory and responsive exploration [23]. This method maintains a short-term memory of the specific changes in some recent moves within the search space, and prevent future moves from undoing those changes. Due to its capacity of searching effectively, TS has been applied to solve various combinatorial problems, such as minimum weight vertex independent dominating set problem [24], the multi-compartment vehicle routing problem [25], and multi-AGV routing problem [26].

    Consequently, in this paper, we focus on improving the basic ACO by blending an effective local search procedure for solving WDP. To be specific, a hash tabu method is proposed to prevent the revisiting of those crucial solutions marked in the search history. As the searching direction is guided by the scoring function of the local search, we further propose a deep scoring strategy, which not only considers the environment of incumbent solutions, but also takes subsequent operations into account. We present the computational results of the proposed algorithm on 44 basics and 13 extended benchmark instances commonly used in the literature, and compare our results with those of the state-of-the-art algorithms for WDP. The results indicate that DHS-ACO is quite efficient on basic benchmark instances and outperforms other competitors on extended test suits. Furthermore, the verification experiments on different components of DHS-ACO are conducted to verify the effectiveness of the hash tabu strategy, the deep scoring strategy, the local search, and the ant colony algorithm.

    The remainder of this paper is organized as follows. In the next section, we introduce the related work of practical algorithms for solving the WDP. In Section 3, we introduce some preliminary knowledge about both DHS-ACO and WDP. Section 4 describes the details of the components in the local search. Based on the above, DHS-ACO is presented. Then, we carry out comparison and verification experiments to evaluate DHS-ACO in Section 5. In the last section, we conclude the paper and introduce some future work.

    In recent years, WDP and its variants have been well studied due to their extensive applications. Vangerven et al. [27] adapted the winner determination problem for geometrical combinatorial auctions. Then, a new subclass of WDP, i.e., the network winner determination problem (NWDP), was proposed in [28], which characterized different problems in NWDP class and analyzed their computational complexity. Afterwards, Remli et al. [29] addressed the winner determination problem for TL transportation procurement auctions under uncertain shipment volumes and uncertain carriers' capacity. It extended an existing two-stage robust formulation proposed for WDP with uncertain shipment volumes. In the same year, Qian et al. [30] conducted a research on winner determination of loss-averse buyers with incomplete information in multi-attribute reverse auctions for clean energy device procurement. It was the same team that further studied a revised winner determination problem with disruption risk of bidders for a fourth party logistics (4PL) provider to purchase transportation services via combinatorial reverse auction [31]. In 2020, Lee et al. [32] resolved the integration difficulty between scheduling and routing aspects of the multiple automated guided vehicle (AGV) problem that were modelled by the winner determination problem.

    For the WDP studied in this work, a number of exact algorithms have been proposed. Fujishima et al. [33] proposed a method, which is guaranteed to be optimal, to reduce the running time by structuring the search space. Nisan [34] suggested an approach based on linear programming (LP) and proved that the LP approach finds an optimal allocation if and only if prices can be attached to single items in the auction. Leyton-Brown et al. [35] proved the correctness of a branch-and-bound algorithm, which incorporates a specialized dynamic programming procedure. Sandholm and Suri [36] presented a more sophisticated search algorithm, including several technologies, for determining winners in many generalizations. Günlük and Ladányi [37] presented a column generation-based algorithm to solve the WDP given in the XOR-of-OR language and a methodology to generate realistic test problems. Escudero et al. [38] proposed a new and tighter formulation of WDP and new valid inequalities; then they presented a branch-and-cut algorithm which shows its efficiency in a big number of instances.

    However, the exact methods can obtain the optimal solution of WDP, while they may fail to return a high-quality solution within a reasonable time or for large-scale of instances. Therefore, Hoos and Boutilier [39] proposed a stochastic local search algorithm (named Casanova), which added a bid to the current solution by considering bids' scores and history information. Based on the basic framework of the simulated annealing algorithm, Guo et al. [40] introduced the SAGII algorithm with three hybrid moving operators, i.e., the branch-and-bound move, the greedy local search move and the exchange move. Experimental results showed that SAGII performed better than Casanova algorithm. A new strategy was proposed in [41], in which a bid was added randomly with probability p at each local iteration, and the bid with maximum profits was added into the solution with probability 1p. Experimental results showed that this strategy had a remarkable effect on the improvement of the algorithm. Wang [42] proposed a new super-heuristic algorithm (named SHH) by combining the selection function and random strategy. Based on the framework of the ant colony algorithm, Dowlatshahi et al. [43] performed a multi-neighborhood local search algorithm. By combining a stochastic local search component with a specific crossover operator, Boughaci et al. [44] presented a memetic algorithm for the winner determination problem. An efficient local search algorithm (named abcWDP) was proposed in [45], which used a pattern monitoring strategy to guide the search. Experimental results illustrated that this algorithm was the state-of-the-art heuristic algorithm for WDP. In addition, Lin et al. [46] raised to transform the combinatorial auction optimization problem into an unconstrained integer programming problem, and proposed a DCM algorithm to solve it.

    Before we give the formulation of WDP, some notations are firstly introduced. Suppose that the collection of items auctioned is MS={M1,M2,...,Mt}, where t is the quantity of items. The set of bids provided by all bidders is BS={B1,B2,...,Bn}, where n is the number of bids. Each bid Bj={Sj,Pj} has two properties: Sj is a non-empty subset of MS that represents the combination of items to bid Bj, while Pj is the bid price of Bj and Pj0. Assume that a Boolean array X={x1,x2,...,xn} is a feasible solution of WDP, where xj{0,1}. xj=1 means that the bid Bj is selected by the auctioneer, i.e., Bj is the winning bid, i.e., Bj is selected in the solution; otherwise, xj=0 indicates that Bj is not selected by the auctioneer, i.e., it is a losing bid. Given above, the constraint of WDP is described as follows:

    maxf(x)=nj=1Pjxj (3.1)
    subjectto:nj=1aijxj1i{1,2,3,...,t},aij{0,1} (3.2)

    where aij=1 represents MiSj, otherwise, MiSj, i[1,t]. Constraint 3.2 guarantees that each item can be allocated at most once. Therefore, Eq (3.1) aims to maximize the auctioneer's revenue by selecting a set of winning bids.

    In order to make the auction process clearly, Figure 1 shows the composite auction scene. Note that two bids containing at least a same item are considered as conflicting bids, which cannot exist simultaneously in the solution. For example, in this scene, B2 and B3 conflict with each other as they both contain M1. All feasible solutions of WDP are composed of different non-conflicting bids. Therefore, all feasible solutions in this example are : C1={{B1},12}, C2={{B2},6}, C3={{B3},8}, C4={{B4},6}, C5={{B2,B4},12}, C6={{B3,B4},14}. Among all feasible solutions, C6 is the optimal solution, as it brings maximum benefit to the auctioneer. That is, when the auctioneer selects B3 and B4, the auctioneer will get the highest income $14.

    Figure 1.  A scene of WDP.

    Ant colony algorithm (ACO) constructs the solution step by step in the way of selecting probability. For WDP, the specific calculation method of selection probability can be calculated as follows. An initial solution C is given to store all winning bids. Let FB={B|CB(B)C=}{BSC} collect all bids without any conflict bids in C, where CB(B) represents all bids that conflict with B in BS. Given the candidate bid set FB, the chosen probability of bid BjFB is:

    pj=(τj)α×(ηj)βBkFB(τk)α×(ηk)β (3.3)

    where α and β represent the influence factors of pheromone and heuristic information of the ant colony algorithm respectively, and ηj is the heuristic factor for solving WDP. Considering the goal of WDP, which is to maximize the auctioneer's revenue, we use the bid price Pj to replace the heuristic factor ηj.

    The basic process of ACO for solving WDP is as follows: firstly, initialize the pheromone vector of each element τj=pvi, where pvi is the initial pheromone concentration. Then, the algorithm enters the search phase. At each iteration, every ant chooses bids from FB according to Eq (3.3). Then, the colony pheromones are updated as Eq (3.4) shows.

    τj=(1ρ)×τj+Δ×xj,j{1,2,...,n} (3.4)

    where ρ[0,1] represents the volatility of the pheromone. Δ is defined as:

    Δ=Fitness(C)nk=1Pk (3.5)

    where Fitness(C) represents the fitness of solution C, calculated as:

    Fitness(C)=BjCPj (3.6)

    After the pheromone updating process is completed, ACO judges whether the stop condition is met. If not, the algorithm enters the next iteration. Otherwise, ACO ends in outputting the best solution ever found.

    In this section, the proposed algorithm named DHS-ACO is introduced. Firstly, the main strategies of the local search are described with detailed explanations. Then, the whole profile of the local search is introduced. Finally, the framework of DHS-ACO is given.

    Local search is an effective method to enhance the quality of the newly generated solutions by exploiting their surroundings. In this section, two key methods for the local search are introduced, including the hash tabu method and the deep scoring strategy. Then, the description of the move operator used in the local search is given. Finally, the local search framework is summarized.

    To avoid the repeated visiting of the same solution in the local search procedure, the hash tabu strategy is designed to efficiently determine whether the current solution has been visited. Given a solution C and a prime number pr, the hash value corresponding to solution C is defined as:

    hash(C)=(BiC2i1)modpr,i{1,2,...,n} (4.1)

    The hash tabu strategy employs a Boolean hash table HT, whose length is pr. The larger the pr value is, the longer the hash table length is, and the less the possibility of hash clash is. Specifically, the method uses a hash table to judge whether the algorithm returns to the visited solution again. In other words, HTh=1 indicates that the solution with a hash value of h has been marked in the search history, while HTh=0 indicates that the solution has not been marked. At the beginning of the algorithm, each element in HT is set to 0, and a hash secondary array H with length n (n is the number of bids) is created, in which each element Hi=2i1modpr. In the initialization, we first set H1=20(modpr)=1, and the subsequent elements are calculated according to the following equation:

    Hi=2Hi1modpr,i{2,3,...,n} (4.2)

    When adding or removing the bid Bi to the solution C, the corresponding hash value of C is updated according to the following equations:

    hash(C{Bi})=[hash(C)+Hi](modpr) (4.3)
    hash(CBi)=[hash(C)+prHi](modpr) (4.4)

    Then, the specific usage of the hash tabu strategy is introduced. In the local search procedure, if the quality of the local search solution decreases in the previous step, while improved in the current step, one of the following situations which will be executed determined by the value of HTh, and h=hash(C).

    1)If HTh=1, the last move will be cancelled with probability ph. In this case, the selected bid Bwin will be removed and prohibited from being added to the current solution until any of its conflicted bids are removed from C. With probability 1ph, the algorithm will rebuild C according to Eq (3) and restart the local search to avoid repeated visiting.

    2) Otherwise, the algorithm will set HTh=1 and continue to search.

    The deep scoring strategy is applied in the bid selection of the local search. The main idea of this mechanism is that if FB, then a bid with the largest SScore value is selected from FB to be added to the current solution. FB stores those bids that are not conflicted with the current solution and SScore is calculated as follows:

    SScore(Bi)=Score(Bi)Subscore(Bi) (4.5)

    where Score() reflects the fitness value change of C after Bi is added:

    Score(Bi)=PiBjCBjCB(Bi)Pj (4.6)

    Clearly, if BiFB and CB(Bi)=, the time complexity of the Eq (4.6) will reduce to O(1). The Score() reflects the greedy degree of the local search, because it only considers the impact of adding one bid to the current solution and does not consider the impact on subsequent local search operators. Regarding this, we introduce the Subscore() evaluation function to estimate the loss of FB set after adding one bid to C, which is calculated as follows:

    Subscore(Bi)=BjFBCB(Bi)Pj|Sj| (4.7)

    On the one hand, the deep scoring strategy ensures that the local search can choose those bids in FB first. Since there are no conflict bids between FB and C, it is unnecessary to conduct conflict detection process and remove the conflicting bid when a bid in FB is added. Therefore, giving priority to select bids in FB will significantly reduce the selecting time. On the other hand, when selecting bids in FB, the deep scoring strategy uses SScore() to comprehensively consider the impact on the solution and the impact on FB loss, which makes the bid selection more reasonable.

    The local search procedure exploits the neighborhoods of the current solution by performing the move operator, whose pseudo-code is shown in Algorithm 1.

    Algorithm 1: Move
    Input: the current solution C, configuration checking table CC
    Output: A feasible solution of given auction

     | Show Table
    DownLoad: CSV

    In algorithm 1, the input data includes the current solution C and the configuration checking vector CC. CC was proposed by [45], whose updating method is as follows: at the beginning of the local search, all elements of CC are initialized to 1. When a bid is removed from the current solution C, the bid CC value is set to 0, and all bids that conflict with the bid CC value are set to 1.

    The algorithm first detects whether FB is empty. If FB, the bid with the largest SScore will be selected into C. Otherwise, the following steps are executed:

    1) In the case of probability p, the algorithm puts the bid with CC=1 into a temporary set L and calls OldestGoodBid(). The OldestGoodBid() function performs the following operations: if L=, then the bid to be added into C will be randomly selected from BSC. Otherwise, c T={B|BLScoreScore(B)δstdB}, where Score is the maximum score of all bids in L, δ is the parameter that controls the scale of T, and stdB is the standard deviation of all bids' prices. Finally, the bid with the longest iterations outside C will be selected into C.

    2) Randomly select a bid from BSC with probability 1p and add it into C to enhance the diversity of the algorithm.

    After completing any of the above cases, the algorithm removes all bids that conflict with Bpick in C and returns C.

    Based on the ideas proposed above, the pseudo-code of the local search is given in Algorithm 2. At the beginning, the local search procedure initializes the best solution C as the current solution C, the non-improved number of the fitness N=0, and the boolean variable lastStepImproved=1, presenting the condition that the fitness of C has been improved after the last move (line 1). Moreover, all elements in CC are initialized to 1 to allow the case that all bids are enabled to be added (line 2). Then, the algorithm iterates until N reaches the limit max_no_improved (lines 3–25). At each iteration of the loop, the Move operator is applied to exploit the neighborhood of C (line 5). If the Move operator failed to find a better solution, the algorithm will set N=N+1 and mark lastStepImproved as 0 (lines 6–8). Otherwise, the algorithm will refresh N=0 (line 10), and attempt to update C (line 11). Afterwards, the hash tabu strategy described in Section 4.1.1 is executed (lines 12–23). Finally, the best solution C found during the search will be returned (line 25).

    Algorithm 2: Local_search
    Input: current solution C
    Output: the best solution C found

     | Show Table
    DownLoad: CSV

    In this section, we design a hybrid ant colony algorithm called DHS-ACO to solve WDP. The pseudo-code of the DHS-ACO algorithm is given in Algorithm 3.

    Algorithm 3: DHS-ACO
    Input: bids set BS, items set MS
    Output: the best solution found bestC

     | Show Table
    DownLoad: CSV

    At the start of the algorithm, DHS-ACO initializes the pheromone vector τ, the hash table HT, the hash auxiliary array H and the best solution bestC (lines 1–2). In each subsequent iteration, the algorithm firstly builds each ant by using the pheromone (line 5). Then, the local search procedure is adopted to exploit the neighborhood of the new ant (line 6). After all ants have finished the local search, DHS-ACO updates the pheromone vector τ (line 8). The loop will end when the running time exceeds the time limit (line 3). Finally, DHS-ACO outputs the best solution bestC (line 9).

    In this section, the complexity of the key components of DHS-ACO are calculated, including the ant construction, the pheromone updating, and the local search procedure. For a brief instruction, some notations are recalled: AntNum=pa, |FB|=sf.

    The ant construction process builds an ant by selecting bids from FB one by one until FB=. The selected bids are determined within O(sf) time. Since |C|n and sfn, the time complexity of constructing one ant is no more than O(n2). As for the pheromone updating, all n elements of τ are updated according to the fitness of all pa ants. Therefore, it takes O(npa) time. In the local search procedure, it takes O(n) for the Move operator in each iteration. Besides, at most O(n2) time would be taken if the hash tabu strategy decides to rebuild the current solution. Thus, the worst case time complexity of one iteration of the local search is O(n+n2), i.e., O(n2).

    To show the efficiency of the proposed algorithm, we carry out extensive experiments in this section. Firstly, the benchmarks used in the experiments are introduced. Then, we compare DHS-ACO against a number of state-of-the-art competitors, including abcWDP [45], DCM [46], MA [44] and HBHSA [47], to show the algorithmic efficiency. Furthermore, the strategy verification experiments are performed to verify the effectiveness of the hash tabu method, the deep scoring strategy, the ant colony framework and the local search procedure proposed in this paper.

    The benchmarks used in this work are selected from a set of LG benchmarks proposed in [48]. As shown in Table 1, it contains 500 instances and is divided into five classes according to the number of bids and items. All classes are named as REL_X_Y, where X represents the number of bids and Y is the number of items. Each class contains 100 examples. We refer to [44,45,46,47] and only select 44 samples from them as the basic benchmarks.

    Table 1.  The message of the basic benchmarks.
    Class Instances Selected instances
    REL_1000_500 in101 - in200 in101 – in110
    REL_1000_1000 in201 - in300 in201 – in210
    REL_500_1000 in401 - in500 in401 – in410
    REL_1500_1000 in501 - in600 in501 – in504
    REL_1500_1500 in601 - in700 in601 – in610

     | Show Table
    DownLoad: CSV

    In addition, due to the small performance gap between DHS-ACO and other competitors on the basic benchmarks, we use the CATS platform [49] to generate a larger set of 13 extended instances, to further compare the performance of DHS-ACO and the state-of-the-art solvers on large-scale instances. Compared with the basic benchmarks, the number of bids and items increases significantly, which will become the obstruction for algorithms. Note that abcWDP performs best among the competitors and thus is chosen as the comparison on extended benchmarks. The extended benchmarks are listed in Table 2. All instances used in this work can be found on the website.

    https://github.com/wujunzero/WDP

    Table 2.  The message of extended benchmarks.
    Name Number of bids Number of items
    CATS_2000 2000 2005
    CATS_2500 2500 2504
    CATS_3000 3000 3004
    CATS_3500 3500 3504
    CATS_4000 4000 4001
    CATS_4500 4500 4504
    CATS_5000 5000 5002
    CATS_5500 5500 5501
    CATS_6000 6000 6000
    CATS_6500 6500 6505
    CATS_7000 7000 7005
    CATS_7500 7500 7505
    CATS_8000 8000 8005

     | Show Table
    DownLoad: CSV

    The DHS-ACO is implemented in C++. For DHS-ACO and abcWDP, all experiments are conducted 10 times on a computer with Intel(R) Xeon(R) CPU E7-4820 v4 @ 2.00 GHz, 64 GB. The experimental results of DCM and MA are taken from [46], while the results of HBHSA are taken from [47]. The operating environment is Intel i3-2330@2.2 GHz, Intel Pentium IV@2.8 GHz and 3.4 GHz AMD processors, respectively. Obviously, their CPU base frequency is higher than that of the experimental environment in this paper (2.00 GHz).

    We use the automatic tuning tool irace [50] to tune the parameters. We randomly select 50 examples from all the examples as the training set. The parameter tuning process is budgeted to run 2,000 times, each with a budgeted run time of 1000 seconds. The final values obtained by irace are shown in Table 3. The results of each experiment will be introduced and analyzed in the following part.

    Table 3.  Parameter setting of DHS-ACO.
    Parameters Description Ranges Final values
    AntNum number of ants {6,8,10,12} 10
    pvi initial pheromone concentration {5,10,15,20} 10
    ρ volatility of pheromone {0,0.1,,0.9} 0.1
    α influence factors of pheromone {0,1,,5} 1
    β influence factors of heuristic information {0,1,,5} 1
    δ parameter that controls the scale of establish set {0.1,0.2,,0.9} 0.5
    p allow probability of adding a bid into current solution {0.91,0.92,,0.99} 0.95
    max_no_improved maximum non-improved steps {80,90,100,110} 100
    pr length of the Boolean hash table {109,109+1,,109+10} 109+7
    ph cancel probability of a move operator {0.90,0.91,,0.99} 0.95

     | Show Table
    DownLoad: CSV

    The experimental results of DHS-ACO and its competitors on basic benchmarks are presented in Tables 48. The columns named f and t stand for the average fitness and the average convergence time, respectively. Table 9 summarizes the average of the fitness ("avg_f") and the total time ("total_t", in seconds) of all algorithms in each class of basic benchmarks shown in Tables 48. Figure 2 shows the average convergence time ("avg_t") and the number of reaching the optimal fitness among all reference algorithms ("best_num") of the best solution obtained by each compared algorithm on all 44 basic instances.

    Table 4.  Results on subset of REL_1000_500.
    Instances DHS-ACO abcWDP DCM MA HBHSA
    f t f t f t f t f t
    in101 72724.62 2.41 72724.62 5.55 67330.25 40.46 67101.93 129.62 67973.71 59.51
    in102 72518.22 4.19 72518.22 10.31 70186.90 43.67 67797.61 132.18 70706.86 58.16
    in103 72129.50 2.35 72129.50 12.51 67496.73 45.38 66350.99 133.34 69151.79 58.28
    in104 72709.65 3.77 72709.65 62.78 69791.24 44.60 64618.41 135.14 71184.80 59.24
    in105 75646.13 1.78 75646.13 1.35 69274.29 47.05 66376.83 153.96 72725.20 62.98
    in106 71258.61 1.40 71258.61 1.49 65110.89 42.82 65481.64 140.96 66461.43 57.67
    in107 69713.40 1.32 69713.40 1.93 67026.55 40.11 66245.70 146.40 68476.54 56.38
    in108 75813.21 3.32 75813.21 1.54 73357.63 46.34 74588.51 161.03 72729.34 58.18
    in109 69475.90 1.16 69475.90 1.36 64548.53 41.34 62492.66 144.71 66023.87 59.74
    in110 68295.29 3.72 68295.29 3.73 65547.86 45.32 65171.19 149.01 66405.36 59.11

     | Show Table
    DownLoad: CSV
    Table 5.  Results on subset of REL_1000_1000.
    Instances DHS-ACO abcWDP DCM MA HBHSA
    f t f t f t f t f t
    in201 81557.74 0.22 81557.74 0.17 78856.30 70.34 77499.82 98.26 80079.58 80.92
    in202 90708.13 1.37 90708.13 3.93 88850.75 79.42 90464.19 106.68 90490.79 85.73
    in203 86239.21 0.99 86239.21 0.89 82551.15 75.48 86239.21 102.28 84491.86 82.22
    in204 87075.43 0.78 87075.43 0.55 83666.49 72.00 81969.05 97.40 85057.33 84.55
    in205 86515.95 0.92 86515.95 1.87 84130.23 71.92 82469.19 91.26 85422.67 116.05
    in206 91518.96 0.48 91518.96 0.69 86333.52 72.40 86881.42 93.99 89211.10 121.07
    in207 93129.25 3.03 93129.25 2.18 89753.32 71.05 91033.51 100.90 92042.88 123.39
    in208 94904.68 0.46 94904.68 0.48 85927.42 75.51 83667.76 101.29 87803.87 80.96
    in209 87268.97 7.16 87268.97 17.45 84752.54 73.26 81966.65 96.42 85265.19 84.45
    in210 89962.40 0.73 89962.40 0.61 86229.86 71.30 85079.98 97.78 87917.57 84.54

     | Show Table
    DownLoad: CSV
    Table 6.  Results on subset of REL_500_1000.
    Instances DHS-ACO abcWDP DCM MA HBHSA
    f t f t f t f t f t
    in401 77417.48 0.03 77417.48 0.04 75438.49 26.59 72948.07 37.07 76035.94 40.63
    in402 76273.34 0.13 76273.34 0.25 75146.65 24.51 71454.78 37.20 76273.34 40.70
    in403 74843.96 0.02 74843.96 0.01 71309.10 25.70 74843.96 38.81 72465.39 41.04
    in404 78761.69 0.06 78761.69 0.03 76877.34 26.42 78761.68 38.78 77091.37 38.37
    in405 75915.90 0.22 75915.90 0.14 75104.28 28.18 72674.25 39.29 75684.28 40.38
    in406 72863.32 0.03 72863.32 0.05 72055.10 28.31 71791.03 38.09 72203.10 37.46
    in407 76365.72 0.13 76365.72 0.04 74443.52 28.45 73935.28 40.95 73650.63 36.00
    in408 77018.83 0.05 77018.83 0.08 74766.64 27.55 72580.04 39.07 74747.72 38.66
    in409 73188.62 0.03 73188.62 0.03 71965.11 25.62 68724.53 36.28 71924.64 40.47
    in410 73791.66 0.06 73791.66 0.06 73092.48 25.49 71791.57 41.90 73726.39 40.22

     | Show Table
    DownLoad: CSV
    Table 7.  Results on subset of REL_1500_1000.
    Instances DHS-ACO abcWDP DCM MA HBHSA
    f t f t f t f t f t
    in501 88656.96 3.13 88656.96 3.75 86353.64 149.28 79132.03 107.82 87341.22 196.18
    in502 86236.91 1.33 86236.91 1.09 84207.64 128.05 80340.76 108.71 84896.64 204.67
    in503 87812.38 12.80 87812.38 10.51 84547.97 137.57 83277.71 114.15 86313.22 197.64
    in504 85600.00 6.70 85600.00 19.69 82742.72 139.61 81903.02 116.11 84604.71 202.92

     | Show Table
    DownLoad: CSV
    Table 8.  Results on subset of REL_1500_1500.
    Instances DHS-ACO abcWDP DCM MA HBHSA
    f t f t f t f t f t
    in601 108800.45 1.78 108800.45 1.57 103273.33 154.69 99044.32 110.62 104402.60 191.21
    in602 105611.48 4.44 105611.48 3.84 102390.49 144.28 98164.23 114.18 103152.40 202.68
    in603 105121.02 6.56 105121.02 7.46 98794.90 137.20 94126.96 110.71 104928.00 187.35
    in604 107733.81 8.76 107733.81 12.83 103522.86 138.49 103568.86 110.60 106694.10 197.08
    in605 109840.98 2.12 109840.98 7.74 103600.76 143.48 102404.76 122.40 106322.10 188.35
    in606 107113.07 0.59 107113.07 1.47 102906.98 141.04 104346.07 107.79 104499.70 195.60
    in607 113180.28 2.63 113180.28 2.55 103297.49 141.11 105869.44 113.26 108241.00 197.03
    in608 105266.11 10.95 105266.11 38.20 100547.10 139.90 95671.77 109.15 104428.30 197.22
    in609 109472.33 2.91 109472.33 0.78 102506.90 139.33 98566.94 111.12 106122.20 198.18
    in610 113716.97 20.14 113716.97 62.95 109516.88 138.17 102468.60 120.17 113716.97 198.16

     | Show Table
    DownLoad: CSV
    Table 9.  Results on basic benchmarks.
    Class DHS-ACO abcWDP DCM MA HBHSA
    avg_f total_t avg_f total_t avg_f total_t avg_f total_t avg_f total_t
    REL_1000_500 72028.45 25.42 72028.45 102.55 67967.09 437.068 66622.55 1426.35 69183.89 589.25
    REL_1000_1000 88888.07 16.14 88888.07 28.82 85105.16 732.68 84727.08 986.26 86778.28 943.88
    REL_ 500_1000 75644.05 0.76 75644.05 0.73 74019.87 266.814 72950.52 387.44 74380.28 393.93
    REL_1500_1000 87076.56 23.96 87076.56 35.04 84462.99 554.518 81163.38 446.79 85788.95 801.41
    REL_1500_1500 108585.65 60.88 108585.65 139.39 103035.77 1417.688 100423.2 1130 106250.7 1952.86

     | Show Table
    DownLoad: CSV
    Figure 2.  Results of best_num and avg_t on basic benchmarks.

    Since the performance gap between DHS-ACO and abcWDP is small on basic benchmarks, we use the extended benchmarks to compare the performance of DHS-ACO and abcWDP. As shown in Table 10, compared with abcWDP algorithm, DHS-ACO algorithm is superior to abcWDP on the average objective function values obtained, which demonstrates that DHS-ACO performs better than abcWDP in solving large-scale instances. "Total" in the last row means the execution time of the tested instances in seconds.

    Table 10.  Results on extended benchmarks.
    Instances DHS-ACO abcWDP
    f t f t
    CATS_2000 92095.11 222.20 88243.66 306.92
    CATS_2500 108426.00 382.62 103076.51 350.32
    CATS_3000 134062.11 303.03 125171.43 195.10
    CATS_3500 154289.60 306.95 143439.39 323.06
    CATS_4000 177537.83 301.17 165046.76 297.31
    CATS_4500 203493.37 360.22 186831.08 322.06
    CATS_5000 223222.27 358.04 204797.15 257.33
    CATS_5500 242498.90 314.37 223389.47 271.43
    CATS_6000 268460.02 433.72 247635.80 310.24
    CATS_6500 286753.35 424.86 262688.31 295.27
    CATS_7000 293800.27 428.23 270759.39 402.83
    CATS_7500 332319.45 508.10 304366.45 417.81
    CATS_8000 339733.32 397.65 309655.66 218.48
    Total (s) 4741.16 3968.16

     | Show Table
    DownLoad: CSV

    Therefore, according to the results in Tables 49 and Figure 2, DHS-ACO algorithm is obviously superior to HBHSA, DCM and MA regarding the performance on each group of the basic benchmarks. Compared with the reference algorithms, DHS-ACO can obtain the same fitness values on all basic benchmarks, owing to the exploration of the heuristic method. And the average convergence time of DHS-ACO is faster and performs 1–2 orders of magnitude faster than the competitors, which reflects the effectiveness and efficiency of DHS-ACO on basic benchmarks. Moreover, for the extended benchmarks (the results of the comparison are shown in Table 10), due to the large-scale of these benchmarks, it is difficult for DCM, MA and HBHSA to solve them, while DHS-ACO obtains the better solutions by reducing the convergence time in each search iteration. Note that DHS-ACO can also find the better solutions on all extended benchmarks than abcWDP, although it requires more execution time than abcWDP in total. It is because of DHS-ACO explored enlarged feasible search space, benefited of the population-based framework.

    In order to verify the effectiveness of each key component of DHS-ACO, we compare DHS-ACO with its four variants, which are introduced as follows:

    ● DHS-ACOnoh: DHS-ACO algorithm without using the hash tabu strategy.

    ● DHS-ACOnofbs: DHS-ACO algorithm without using the deep scoring strategy.

    ● DHS-ACOnols: DHS-ACO algorithm without local search.

    ● DHS-ACOnoaco: DHS-ACO algorithm without ant colony framework. This means DHS-ACOnoaco only uses the local search to solve the benchmarks. When the hash tabu strategy decides to rebuild the solution, the solution will be initialized randomly rather than use the construction method of ACO.

    Since the comparison experiment shows that DHS-ACO algorithm can solve all basic test cases stably, we select all extended cases in Table 2 to test the effectiveness of each key component. The comparisons between DHS-ACO and its variants are listed in Table 11 to Table 14.

    Table 11.  Results obtained by DHS-ACO and DHS-ACOnoh.
    Instances DHS-ACO DHS-ACOnoh
    f t f t
    CATS_2000 92095.11 222.20 92053.91 283.39
    CATS_2500 108426.00 382.62 108262.94 315.93
    CATS_3000 134062.11 303.03 133861.27 328.99
    CATS_3500 154289.60 306.95 154234.50 341.62
    CATS_4000 177537.83 301.17 177404.69 390.68
    CATS_4500 203493.37 360.22 203570.93 397.36
    CATS_5000 223222.27 358.04 222909.74 365.98
    CATS_5500 242498.90 314.37 242434.70 392.56
    CATS_6000 268460.02 433.72 268433.42 418.30
    CATS_6500 286753.35 424.86 286460.81 399.11
    CATS_7000 293800.27 428.23 294079.34 419.63
    CATS_7500 332319.45 508.10 331237.09 446.86
    CATS_8000 339733.32 397.65 339644.22 339.03

     | Show Table
    DownLoad: CSV
    Table 12.  Results obtained by DHS-ACO and DHS-ACOnofbs.
    Instances DHS-ACO DHS-ACOnofbs
    f t f t
    CATS_2000 92095.11 222.20 92103.01 305.01
    CATS_2500 108426.00 382.62 109000.30 202.89
    CATS_3000 134062.11 303.03 133422.57 375.12
    CATS_3500 154289.60 306.95 154051.85 307.68
    CATS_4000 177537.83 301.17 176574.29 213.85
    CATS_4500 203493.37 360.22 203507.10 379.32
    CATS_5000 223222.27 358.04 222270.79 414.67
    CATS_5500 242498.90 314.37 241873.75 375.88
    CATS_6000 268460.02 433.72 267820.75 463.77
    CATS_6500 286753.35 424.86 286299.25 424.79
    CATS_7000 293800.27 428.23 293537.66 437.80
    CATS_7500 332319.45 508.10 331171.41 462.54
    CATS_8000 339733.32 397.65 338324.77 461.95

     | Show Table
    DownLoad: CSV
    Table 13.  Results obtained by DHS-ACO and DHS-ACOnols.
    Instances DHS-ACO DHS-ACOnols
    f t f t
    CATS_2000 92095.11 222.20 85292.66 2.65
    CATS_2500 108426.00 382.62 100334.73 3.14
    CATS_3000 134062.11 303.03 122329.02 5.69
    CATS_3500 154289.60 306.95 141815.45 7.67
    CATS_4000 177537.83 301.17 162805.02 10.27
    CATS_4500 203493.37 360.22 188135.22 13.94
    CATS_5000 223222.27 358.04 205140.48 19.58
    CATS_5500 242498.90 314.37 223106.47 25.55
    CATS_6000 268460.02 433.72 249082.54 30.69
    CATS_6500 286753.35 424.86 266662.91 35.89
    CATS_7000 293800.27 428.23 270262.84 39.84
    CATS_7500 332319.45 508.10 305819.14 51.85
    CATS_8000 339733.32 397.65 312315.06 56.36

     | Show Table
    DownLoad: CSV
    Table 14.  Results obtained by DHS-ACO and DHS-ACOnoaco.
    Instances DHS-ACO DHS-ACOnoaco
    f t f t
    CATS_2000 92095.11 222.20 87859.02 239.43
    CATS_2500 108426.00 382.62 102506.50 171.21
    CATS_3000 134062.11 303.03 124633.43 199.47
    CATS_3500 154289.60 306.95 143283.79 211.61
    CATS_4000 177537.83 301.17 165032.62 147.11
    CATS_4500 203493.37 360.22 186365.41 240.25
    CATS_5000 223222.27 358.04 204715.67 180.20
    CATS_5500 242498.90 314.37 223167.11 141.10
    CATS_6000 268460.02 433.72 246538.17 251.53
    CATS_6500 286753.35 424.86 262135.68 250.56
    CATS_7000 293800.27 428.23 270097.45 222.24
    CATS_7500 332319.45 508.10 303594.47 309.95
    CATS_8000 339733.32 397.65 309485.41 245.40

     | Show Table
    DownLoad: CSV

    Table 11 shows that DHS-ACOnoh algorithm gains lower f values than DHS-ACO on 11 instances, while obtains higher values on the remaining 2 instances. It can be seen that the intervention of the hash tabu strategy of the local search shows a negative effect, because the local search selects bids with randomness, which means the subsequent searches for those solutions marked by hash tabu strategy have little chance to find better solutions. However, in general, the hash tabu strategy makes DHS-ACO avoid repeated visiting efficiently and improve the local search significantly.

    As can be seen from Table 12, DHS-ACO outperforms DHS-ACOnofbs on 10 out of 13 instances. One can see that the deep scoring strategy is counterproductive in a few test cases, because it focuses too much on the selection and maintenance of FB, and ignores the bids outside FB. Nevertheless, the deep scoring strategy improves the performance of DHS-ACO from an overall perspective.

    According to Table 13, DHS-ACOnols obtains worse solutions on all instances without using the local search. Meanwhile, its convergence time is greatly reduced compared with DHS-ACO. It is clear that the proposed local search provides a powerful neighborhood search capability for DHS-ACO, which makes DHS-ACO effective in exploiting the solution space.

    Table 14 indicates the effectiveness of the ant colony algorithm framework of DHS-ACO. Without the new solutions generated by the ant colony framework, DHS-ACOnoaco performs significantly worse than DHS-ACO on all test cases. It demonstrates the necessary of using the ant colony framework to provide high-quality solutions for DHS-ACO based on pheromones and heuristics.

    In this paper, we propose a new swarm algorithm called DHS-ACO, which can effectively deal with the WDP on a wide instances. Based on the ant colony framework, the algorithm combines an effective local search with a hash tabu method and a deep scoring strategy. Extensive computational evaluations of the algorithm on two set of benchmarks demonstrated its competitiveness compared to the state-of-the-art methods. In particular, the algorithm can find the same best solutions on all basic benchmarks with less time reported in the literature and the best solutions on all extended benchmarks.

    Furthermore, owing to the random nature of the swarm intelligent algorithms, DHS-ACO need more time than its competitor abcWDP on large-scale benchmarks, although it can give better solutions. It would be interesting to reduce the consumption time on the large-scale benchmarks in the future.

    This work is supported by the Fundamental Research Funds for the Central Universities 2412018QD022, NSFC (under Grant No.61976050, 61972384) and Jilin Provincial Science and Technology Department under Grant No. 20190302109GX.

    The authors declare that there is no conflict of interests regarding the publication of this paper.

    [1] Castro AA, Caetano MS, Silva TC, et al. (2016) Molecular docking, metal substitution and hydrolysis reaction of chiral substrates of phosphotriesterase. Comb Chem High Throughput Screen 19: 334–344.
    [2] Calvert GM, Karnik J, Mehler L, et al. (2008) Acute pesticide poisoning among agricultural workers in the United States, 1998–2005. Am J Ind Med 51: 883–898.
    [3] Berny P (2007) Pesticides and the intoxication of wild animals. J Vet Pharmacol Ther 30: 93–100.
    [4] Lima WEA, Pereira AF, Castro AA, et al. (2016) Flexibility in the molecular design of Acetylcholinesterase Reactivators: Probing Representative Conformations by Chemometric Techniques and Docking/QM Calculations. Lett Drug Des Discov 13: 360–371.
    [5] Sartorelli J, Castro AA, Ramalho TC, et al. (2016) Asymmetric biocatalysis of the nerve agent VX by human serum paraoxonase 1: molecular docking and reaction mechanism calculations. Med Chem Res 25: 2521–2533.
    [6] King, AM, Aaron CK (2015) Organophosphate and carbamate poisoning. Emerg Med Clin North Am 33: 133–151.
    [7] Ramalho TC, Castro AA, Silva DR, et al. (2016) Computational enzymology and organophosphorus degrading enzymes: Promising approaches toward remediation technologies of warfare agents and pesticides. Curr Med Chem 23: 1041–1061.
    [8] Iyer R, Iken B, Damania A (2013) A comparison of organophosphate degradation genes and bioremediation applications. Environ Microbiol Rep 5: 787–798.
    [9] Iyer R, Iken B (2015) Protein engineering of representative hydrolytic enzymes for remediation of organophosphates. Biochem Eng J 94: 134–144.
    [10] Kuca K, Bartosova L, Jun D, et al. (2005) New quaternary pyridine aldoximes as casual antidotes against nerve agents intoxications. Biomed Pap Med Fac Univ Palacky Olomouc Czech Repub 149: 75–82.
    [11] Nemukhin AV, Grigorenko BL, Lushchekina SV, et al. (2012) Quantum chemical modelling in the research of molecular mechanisms of enzymatic catalysis. Russ Chem Rev 81: 1011–1025.
    [12] van der Kamp MW, Mulholland AJ (2008) Computational enzymology: insight into biological catalysts from modelling. Nat Prod Rep 25: 1001–1014.
    [13] Puri KD, Di Paolo JA, Gold MR (2013) B-cell receptor signaling inhibitors for treatment of autoimmune inflammatory diseases and B-cell malignancies. Int Rev Immunol 32: 397–427.
    [14] Chen YC (2015) Beware of docking! Trends Pharmacol Sci 36: 78–95.
    [15] Thomsen R, Christensen MH (2006) MolDock: a new technique for high-accuracy molecular docking. J Med Chem 49: 3315–3321.
    [16] Jones G, Willett P, Glen RC, et al. (1997) Development and validation of a genetic algorithm for flexible docking. J Mol Biol 267: 727–748.
    [17] Goodsell DS, Olson AJ (1990) Automated docking of substrates to proteins by simulated annealing. Proteins Struct Funct Bioinforma 8: 195–202.
    [18] Morris GM, Goodsell DS, Olson AJ (1996) Automated docking of flexible ligands: applications of AutoDock. J Comput Aided Mol Des 10: 293–304.
    [19] Rarey M, Kramer B, Lengauer T, et al. (1996) A fast flexible docking method using an incremental construction algorithm. J Mol Biol 261: 470–489.
    [20] Azevedo LS, Moraes FP, Xavier MM, et al. (2012) Recent progress of molecular docking simulations applied to development of drugs. Curr Bioinform 7: 352–365.
    [21] Liu M, Wang S (1999) MCDOCK: a Monte Carlo simulation approach to the molecular docking problem. J Comput Aided Mol Des 13: 435–451.
    [22] Rosenfeld RJ, Goodsell DS, Musah RA, et al. (2003) Automated docking of ligands to an arti cial active site: augmenting crystallographic analysis with computer modeling. J Comput Aided Mol Des 17: 525–536.
    [23] da Cunha EFF, Ramalho TC, Reynolds RC (2008) Binding mode analysis of 2,4-diamino-5-methyl-5-deaza-6-substituted pteridines with Mycobacterium tuberculosis and human dihydrofolate reductases. J Biomol Struct Dyn 25: 377–385.
    [24] Assis LC, Santos-Garcia L, Ramalho TC, et al. (2013) Interactions of pyrimidine derivatives with dihydrofolate reductase and thymidylate synthase: directions toward combating toxoplasmosis. Curr Bioact Compd 9: 153–166.
    [25] Kuntz ID, Blaney JM, Oatley SJ, et al. (1982) A geometric approach to macromolecule-ligand interactions. J Mol Biol 161: 269–288.
    [26] Kirkpatrick S, Gelatt Jr CD, Vecchi MP (1983) Optimization by simmulated annealing. Science 220: 671–680.
    [27] Assis TM, Mancini DT, Ramalho TC, et al. (2014) In silico study of Leishmania donovani α-β tubulin and inhibitors. J Chem 2014: 1–8.
    [28] Giacoppo JOS, Mancini DT, Guimaraes AP, et al. (2015) Molecular modeling toward selective inhibitors of dihydrofolate reductase from the biological warfare agent Bacillus anthracis. Eur J Med Chem 91: 63–71.
    [29] Mulholland AJ (2007) Chemical accuracy in QM/MM calculations on enzyme-catalysed reactions. Chem Cent J 1: 1–5.
    [30] Santos-Garcia L, Assis LC, Silva DR, et al. (2016) QSAR analysis of nicotinamidic compounds and design of potential Bruton's tyrosine kinase (Btk) inhibitors. J Biomol Struct Dyn 34: 1421–1440.
    [31] Namba AM, Silva VB, Silva CHTP (2008) Dinâmica molecular: teoria e aplicações em planejamento de fármacos. Ecl Quim 33: 13–23.
    [32] Fattebert JL, Lau EY, Bennion BJ, et al. (2015) Large-scale first-principles molecular dynamics simulations with electrostatic embedding: application to acetylcholinesterase catalysis. J Chem Theory Comput 11: 5688–5695.
    [33] de Azevedo WF (2011) Molecular dynamics simulations of protein targets identified in Mycobacterium tuberculosis. Curr Med Chem 18: 1353–1366.
    [34] Weiner PK, Kollman PA (1981) AMBER: Assisted model building with energy refinement. A general program for modeling molecules and their interactions. J Comput Chem 2: 287–303.
    [35] Brooks BR, Bruccoleri RE, Olafson BD, et al. (1983) CHARMM: A program for macromolecular energy, minimization, and dynamics calculations. J Comput Chem 4: 187–217.
    [36] Kalé L, Skeel R, Bhandarkar M, et al. (1999) NAMD2: greater scalability for parallel molecular dynamics. J Comput Phys 151: 283–312.
    [37] Phillips JC, Braun R, Wang W, et al. (2005) Scalable molecular dynamics with NAMD. J Comput Chem 26: 1781–1802.
    [38] Scott WRP, Hünenberger PH, Tironi IG, et al. (1999) The GROMOS biomolecular simulation program package. J Phys Chem A 103: 3596–3607.
    [39] Dubey KD, Tiwari RK, Ojha RP (2013) Recent advances in protein-ligand interactions: molecular dynamics simulations and binding free energy. Curr Comput Aided-Drug Des 9: 518–531.
    [40] Durrant JD, McCammon JA (2011) Molecular dynamics simulations and drug discovery. BMC Biol 9: 1–9.
    [41] Karplus M, McCammon JA (2002) Molecular dynamics simulations of biomolecules. Nat Struct Biol 9: 646–652.
    [42] Ochoa R, Rodriguez CA, Zuluaga AF (2016) Perspectives for the structure-based design of acetylcholinesterase reactivators. J Mol Graph Model 68: 176–183.
    [43] Zheng M, Waller MP (2016) Adaptive quantum mechanics/molecular mechanics methods. Wiley Interdiscip Rev Comput Mol Sci 6: 369–385.
    [44] Ryde, U (2016) QM/MM calculations on proteins, In: Voth GA, Methods in enzymology: computational approaches for studying enzyme mechanism Part A, 1 Ed., Elsevier Inc., 119–158.
    [45] Lodola A, Mulholland AJ (2013) Computational enzymology. Methods Mol Biol 924: 67–89.
    [46] Senn HM, Thiel W (2009) QM/MM methods for biomolecular systems. Angew Chem Int Ed Engl 48: 1198–1229.
    [47] van der Kamp MW, Mulholland AJ (2013) Combined quantum mechanics/molecular mechanics (QM/MM) methods in computational enzymology. Biochemistry 52: 2708–2728.
    [48] Silva MC, Torres JA, Castro AA, et al. (2015) Combined experimental and theoretical study on the removal of pollutant compounds by peroxidases: affinity and reactivity toward a bioremediation catalyst. J Biomol Struct Dyn 34: 1–35.
    [49] Silva TC, Pires MS, Castro AA, et al. (2015) Molecular insight into the inhibition mechanism of plant and rat 4-hydroxyphenylpyruvate dioxygenase by molecular docking and DFT calculations. Med Chem Res 24: 3958–3971.
    [50] Balali-Mood M, Abdollahi M (2014) Basic and clinical toxicology of organophosphorus compounds, 1 Ed., London: Springer International Publishing.
    [51] Kumar DN, Alex SA, Chandrasekaran N, et al. (2016) Acetylcholinesterase (AChE)-mediated immobilization of silver nanoparticles for the detection of organophosphorus pesticides. RSC Adv 6: 64769–64777.
    [52] Jang YJ, Kim K, Tsay O, et al. (2015) Update 1 of: destruction and detection of chemical warfare agents. Chem Rev 115: PR1–PR76.
    [53] Kim K, Tsay OG, Atwood DA, et al. (2011) Destruction and detection of chemical warfare agents. Chem Rev 111: 5345–5403.
    [54] Roberts JR, Reigart JR (2013) Recognition and management of pesticide poisoning, 6 Eds., Washington: United States Environmental Protection Agency Office of Pesticide Programs.
    [55] Cavalcanti LPAN, Aguiar AP, Lima JA, Lima ALS (2016) Organophosphorous poisoning: treatment and analytical methodologies applied in evaluation of reactivation and inhibition of acetylcholinesterase. Rev Virtual Química 8: 739–766.
    [56] Giacoppo JOS, França TCC, Kuča K, et al. (2014) Molecular modeling and in vitro reactivation study between the oxime BI-6 and acetylcholinesterase inhibited by different nerve agents. J Biomol Struct Dyn 33: 2048–2058.
    [57] Dvir H, Silman I, Harel M, et al. (2010) Acetylcholinesterase: from 3D structure to function. Chem Biol Interact 187: 10–22.
    [58] Patočka J, Cabal J, Kuča, K, et al. (2005) Oxime reactivation of acetylcholinesterase inhibited by toxic phosphorus esters: In vitro kinetics and thermodynamics. J Appl Biomed 3: 91–99.
    [59] Tafuri J, Roberts J (1987) Organophosphate poisoning. Ann Emerg Med 16: 193–202.
    [60] Mileson B (1998) Common mechanism of toxicity: a case study of organophosphorus pesticides. Toxicol Sci 41: 8–20.
    [61] Eddleston M (2004) Self poisoning with pesticides. BMJ 328: 42–44.
    [62] Delfino RT, Ribeiro TS, Figueroa-Villar JD (2009) Organophosphorus compounds as chemical warfare agents: A review. J Braz Chem Soc 20: 407–428.
    [63] Hörnberg A, Tunemalm AK, Ekström F (2007) Crystal structures of acetylcholinesterase in complex with organophosphorus compounds suggest that the acyl pocket modulates the aging reaction by precluding the formation of the trigonal bipyramidal transition state. Biochemistry 46: 4815–4825.
    [64] DuBois, KP (1971) The toxicity of organophosphorus compounds to mammals. Bull World Health Organ 44: 231–240.
    [65] Pasquet J, Mazuret A, Fournel J, et al. (1976) Acute oral and percutaneous toxicity of phosalone in the rat, in comparison with azinphosmethyl and Parathion. Toxicol Appl Pharm 37: 85–92.
    [66] Jamal GA, Hansen S, Julu PO (2002) Low level exposures to organophosphorus esters may cause neurotoxicity. Toxicology 182: 23–33.
    [67] Brunton LL, Chabner BA, Knollmann BC (2010) The Pharmacological Basis of Therapeutics.
    [68] Kavalci C, Durukan P, Ozer M, et al. (2009) Organophosphate poisoning due to a wheat bagel. Intern Med 48: 85–88.
    [69] Mercey G, Verdelet T, Renou J, et al. (2012) Reactivators of acetylcholinesterase inhibited by organophosphorus nerve agents. Acc Chem Res 45: 756–766.
    [70] Wilson IB, Ginsburg S (1955) A powerful reactivator of alkylphosphate-inhibited acetylcholinesterase. Biochim Biophys Acta 18: 168–170.
    [71] Soares S, Vieira AA, Delfino RT, et al. (2013) NMR determination of Electrophorus electricus acetylcholinesterase inhibition and reactivation by neutral oximes. Bioorg Med Chem 21: 5923–5930.
    [72] Kuca K, Jun D, Musilek K (2006) Structural requirements of acetylcholinesterase reactivators. Mini-Reviews Med Chem 6: 269–277.
    [73] Musilek K, Dolezal M, Gunn-Moore F, et al. (2011) Design, evaluation and structure-activity relationship studies of the AChE reactivators against organophosphorus pesticides. Med Res Rev 31: 548–575.
    [74] Husain K (2013) Delayed neurotoxicity of organophosphorus compounds. J Enviromental Immunol Toxicol 1: 14–21.
    [75] Sahu AK, Sharma R, Gupta B, et al. (2016) Oxime-mediated in vitro reactivation kinetic analysis of organophosphates-inhibited human and electric eel acetylcholinesterase. Toxicol Mech Methods 6516: 1–8.
    [76] Szinicz L (2005) History of chemical and biological warfare agents. Toxicology 214: 167–181.
    [77] Singh BK, Walker A (2006) Microbial degradation of organophosphorus compounds. FEMS Microbiol Rev 30: 428–471.
    [78] Omburo GA, Kuo JM, Mullins LS, et al. (1992) Characterization of the zinc-binding site of bacterial phosphotriesterase. J Biol Chem 267: 13278–13283.
    [79] Perezgasga L, Sanchez-Sanchez L, Aguila S, et al. (2012) Substitution of the catalytic metal and protein PEGylation enhances activity and stability of bacterial phosphotriesterase. Appl Biochem Biotechnol 166: 1236–1247.
    [80] Tsai PC, Fox N, Bigley AN, et al. (2012) Enzymes for the homeland defense: optimizing phosphotriesterase for the hydrolysis of organophosphate nerve agents. Biochemistry 51: 6463–6475.
    [81] Singh BK (2009) Organophosphorus-degrading bacteria: ecology and industrial applications. Nat Rev Microbiol 7: 156–164.
    [82] Theriot CM, Grunden AM (2011) Hydrolysis of organophosphorus compounds by microbial enzymes. Appl Microbiol Biotechnol 89: 35–43.
    [83] Bigley AN, Raushel FM (2013) Catalytic mechanisms for phosphotriesterases. Biochim Biophys Acta 1834: 443–453.
    [84] Rochu D, Viguié N, Renault F, et al. (2004) Contribution of the active-site metal cation to the catalytic activity and to the conformational stability of phosphotriesterase: temperature- and pH-dependence. Biochem J 380: 627–633.
    [85] Chen SL, Fang WH, Himo F (2008) Technical aspects of quantum chemical modeling of enzymatic reactions: the case of phosphotriesterase. Theor Chem Acc 120: 515–522.
    [86] Vanhooke JL, Benning MM, Raushel FM, et al. (1996) Three-dimensional structure of the zinc-containing phosphotriesterase with the bound substrate analog diethyl 4-methylbenzylphosphonate. Biochemistry 35: 6020–6025.
    [87] Lotti M (2002) Promotion of organophosphate induced delayed polyneuropathy by certain esterase inhibitors. Toxicology 181: 245–248.
    [88] Chen-Goodspeed M, Sogorb MA, Wu F, et al. (2001) Structural determinants of the substrate and stereochemical specificity of phosphotriesterase. Biochemistry 40: 1325–1331.
    [89] Chen-Goodspeed M, Sogorb MA, Wu F, et al. Enhancement, relaxation, and reversal of the stereoselectivity for phosphotriesterase by rational evolution of active site residues. Biochemistry 40: 1332–1339.
    [90] Nowlan C, Li Y, Hermann JC, et al. (2006) Resolution of chiral phosphate, phosphonate, and phosphinate esters by an enantioselective enzyme library. J Am Chem Soc 128: 15892–15902.
    [91] Hong SB, Raushel FM (1999) Stereochemical preferences for chiral substrates by the bacterial phosphotriesterase. Chem Biol Interact 119: 225–234.
    [92] Tsai PC, Bigley A, Li Y, et al. (2010) Stereoselective hydrolysis of organophosphate nerve agents by the bacterial phosphotriesterase. Biochemistry 49: 7978–7987.
    [93] Lewis VE, Donarski WJ, Wild JR, et al. (1988) Mechanism and stereochemical course at phosphorus of the reaction catalyzed by a bacterial phosphotriesterase. Biochemistry 27: 1591–1597.
    [94] Aubert SD, Li YC, Raushel FM (2004) Mechanism for the hydrolysis of organophosphates by the bacterial phosphotriesterase. Biochemistry 43: 5707–5715.
    [95] Bigley AN, Xu C, Henderson TJ, et al. (2013) Enzymatic neutralization of the chemical warfare agent VX: evolution of phosphotriesterase for phosphorothiolate hydrolysis. J Am Chem Soc 135: 10426–10432.
    [96] Nachon F, Brazzolotto X, Trovaslet M, et al. (2013) Progress in the development of enzyme-based nerve agent bioscavengers. Chem Biol Interact 206: 536–544.
    [97] Furlong CE (2008) Paraoxonases: An historical perspective, In: Mackness B, Mackness M, Aviram M, et al., The paraoxonases: their role in disease development and xenobiotic metabolism, Springer, 3–31.
    [98] Aharoni A, Gaidukov L, Khersonsky O, et al. (2005) The 'evolvability' of promiscuous protein functions. Nat Genet 37: 73–76.
    [99] Khersonsky O, Tawfik DS (2006) The histidine 115-histidine 134 dyad mediates the lactonase activity of mammalian serum paraoxonases. J Biol Chem 281: 7649–7656.
    [100] Cannard K (2006) The acute treatment of nerve agent exposure. J Neurol Sci 249: 86–94.
    [101] Gaidukov L, Tawfik DS (2007) The development of human sera tests for HDL-bound serum PON1 and its lipolactonase activity. J Lipid Res 48: 1637–1646.
    [102] Yeung DT, Lenz DE, Cerasoli DM (2008) Human paraoxonase I: A potential bioscavenger of organophosphorus nerve agents, In: Mackness B, Mackness M, Aviram M, et al., The paraoxonases: their role in disease development and xenobiotic metabolism, Springer, 151–170.
    [103] Lenz DE, Yeung D, Smith JR, et al. (2007) Stoichiometric and catalytic scavengers as protection against nerve agent toxicity: A mini review. Toxicology 233: 31–39.
    [104] Rochu D, Chabriere E, Masson P (2007) Human paraoxonase: A promising approach for pre-treatment and therapy of organophosphorus poisoning. Toxicology 233: 47–59.
    [105] La Du BN, Aviram M, Billecke S, et al. (1999) On the physiological role(s) of the paraoxonases. Chem Biol Interact 119: 379–388.
    [106] Ahmed Z, Ravandi A, Maguire GF, et al. (2002) Multiple substrates for paraoxonase-1 during oxidation of phosphatidylcholine by peroxynitrite. Biochem Biophys Res Commun 290: 391–396.
    [107] Shih DM, Gu LJ, Xia YR, et al. (1998) Mice lacking serum paraoxonase are susceptible to organophosphate toxicity and atherosclerosis. Nature 394: 284–287.
    [108] Mackness B, Mackness M (2010) Anti-inflammatory properties of paraoxonase-1 in atherosclerosis, In: Reddy ST, Paraoxonases in inflammation, infection, and toxicology, Humana Press, 143–151.
    [109] Koren-Gluzer M, Aviram M, Meilin E, et al. (2011) The antioxidant HDL-associated paraoxonase-1 (PON1) attenuates diabetes development and stimulates beta-cell insulin release. Atherosclerosis 219: 510–518.
    [110] Li WF, Furlong CE, Costa LG (1995) Paraoxonase protects against chlorpyrifos toxicity in mice. Toxicol Lett 76: 219–226.
    [111] Camps J, Pujol I, Ballester F, et al. (2011) Paraoxonases as potential antibiofilm agents: their relationship with quorum-sensing signals in gram-negative bacteria. Antimicrob Agents Chemother 55: 1325–1331.
    [112] Yeung DT, Lenz DE, Cerasoli DM (2005) Analysis of active-site amino-acid residues of human serum paraoxonase using competitive substrates. FEBS J 272: 2225–2230.
    [113] Harel M, Aharoni A, Gaidukov L, et al. (2004) Structure and evolution of the serum paraoxonase family of detoxifying and anti-atherosclerotic enzymes. Nat Struct Mol Biol 11: 412–419.
    [114] Fairchild SZ, Peterson MW, Hamza A, et al. (2011) Computational characterization of how the VX nerve agent binds human serum paraoxonase 1. J Mol Model 17: 97–109.
    [115] Kuo CL, La Du BN (1998) Calcium binding by human and rabbit serum paraoxonases-structural stability and enzymatic activity. Drug Metab Dispos 26: 653–660.
    [116] Blum MM, Timperley CM, Williams GR, et al. (2008) Inhibitory potency against human acetylcholinesterase and enzymatic hydrolysis of Fluorogenic nerve agent mimics by human paraoxonase 1 and squid diisopropyl fluorophosphatase. Biochemistry 47: 5216–5224.
    [117] Hu X, Jiang X, Lenz DE, et al. (2009) In silico analyses of substrate interactions with human serum paraoxonase 1. Proteins 75: 486–498.
    [118] Otto TC, Harsch CK, Yeung DT, et al. (2009) Dramatic differences in organophosphorus hydrolase activity between human and chimeric recombinant mammalian paraoxonase-1 enzymes. Biochemistry 48: 10416–10422.
    [119] Sanan TT, Muthukrishnan S, Beck JM, et al. (2010) Computational modeling of human paraoxonase 1: preparation of protein models, binding studies, and mechanistic insights. J Phys Org Chem 23: 357–369.
    [120] Dumas DP, Caldwell SR, Wild JR, et al. (1989) Purification and properties of the phosphotriesterase from Pseudomonas diminuta. J Biol Chem 264: 19659–19665.
    [121] Muthukrishnan S, Shete VS, Sanan TT, et al. (2012) Mechanistic insights into the hydrolysis of organophosphorus compounds by paraoxonase-1: exploring the limits of substrate tolerance in a promiscuous enzyme. J Phys Org Chem 25: 1247–1260.
    [122] Wymore T, Field MJ, Langan P, et al. (2014) Hydrolysis of DFP and the nerve agent (S)-sarin by DFPase proceeds along two different reaction pathways: Implications for engineering bioscavengers. J Phys Chem B 118: 4479–4489.
    [123] Chen JCH, Mustyakimov M, Schoenborn BP, et al. (2010) Neutron structure and mechanistic studies of diisopropyl fluorophosphatase (DFPase). Acta Crystallogr D 66: 1131–1138.
    [124] Katsemi V, Lücke C, Koepke J, et al. (2005) Mutational and structural studies of the diisopropylfluorophosphatase from Loligo vulgaris shed new light on the catalytic mechanism of the enzyme. Biochemistry 44: 9022–9033.
    [125] Elias M, Liebschner D, Koepke J, et al. (2013) Hydrogen atoms in protein structures: high-resolution X-ray diffraction structure of the DFPase. BMC Res Notes 6: 1–7.
    [126] Hoskin FCG, Rosenberg P, Brzin M (1966) Re-examination of the effect of DFP on electrical and cholinesterase activity of squid giant axon. Proc Natl Acad Sci USA 55: 1231–1235.
    [127] Hoskin FCG, Long RJ (1972) Purification of a DFP-hydrolyzing enzyme from squid head ganglion. Arch Biochem Biophys 150: 548–555.
    [128] Gay DD, Hoskin FCG (1979) Stereospecificity and active site requirements in a diisopropylphosphorofluoridate-hydrolyzing enzyme. Biochem Pharmacol 28: 1259–1261.
    [129] Hoskin FCG, Kirkish MA, Steinmann KE (1984) Two enzymes for the detoxication of organophosphorus compounds-sources, similarities, and significance. Fundam Appl Toxicol 4: 165–172.
    [130] Hartleib J, Rüterjans H (2001) Insights into the reaction mechanism of the diisopropyl fluorophosphatase from Loligo vulgaris by means of kinetic studies, chemical modification and site-directed mutagenesis. Biochim Biophys Acta 1546: 312–324.
    [131] Hartleib J, Geschwindner S, Scharff EI, et al. (2001) Role of calcium ions in the structure and function of the di-isopropylfluorophosphatase from Loligo vulgaris. Biochem J 353: 579–589.
    [132] Hartleib J, Rüterjans H (2001) High-yield expression, purification, and characterization of the recombinant diisopropylfluorophosphatase from Loligo vulgaris. Protein Expr Purif 21: 210–219.
    [133] Scharff EI, Koepke J, Fritzsch G, et al. (2001) Crystal structure of diisopropylfluorophosphatase from Loligo vulgaris. Structure 9: 493–502.
    [134] Blum MM, Löhr F, Richardt A, et al. (2006) Binding of a designed substrate analogue to diisopropyl fluorophosphatase: Implications for the phosphotriesterase mechanism. J Am Chem Soc 128: 12750–12757.
    [135] Melzer M, Chen JCH, Heidenreich A, et al. (2009) Reversed enantioselectivity of diisopropyl fluorophosphatase against organophosphorus nerve agents by rational design. J Am Chem Soc 131: 17226–17232.
    [136] Koepke J, Scharff EI, Lücke C, et al. (2003) Statistical analysis of crystallographic data obtained from squid ganglion DFPase at 0.85 A resolution. Acta Crystallogr D 59: 1744–1754.
  • This article has been cited by:

    1. YoungSu Yun, Mitsuo Gen, Tserengotov Nomin Erdene, Applying GA-PSO-TLBO approach to engineering optimization problems, 2022, 20, 1551-0018, 552, 10.3934/mbe.2023025
    2. Xiyu Zhao, Jun Liu, Simulation of Film and Television Transmission Path Based on Ant Colony Optimization Algorithm, 2022, 2022, 1939-0122, 1, 10.1155/2022/2826527
    3. Yimeng Shi, Hongyuan Zhang, Zheng Chen, Yueyue Sun, Xuecheng Liu, Jin Gu, A Study on the Deployment of Mesoscale Chemical Hazard Area Monitoring Points by Combining Weighting and Fireworks Algorithms, 2023, 15, 2071-1050, 5779, 10.3390/su15075779
    4. Yanhu Han, Huimin Xin, The capacitated location problem of precast concrete component factory, 2023, 10641246, 1, 10.3233/JIFS-222923
    5. Sameer Sabir, Sousso Kelouwani, Nilson Henao, Kodjo Agbossou, Michaël Fournier, Shaival Hemant Nagarsheth, A Computationally Efficient Method for Energy Allocation in Spot Markets With Application to Transactive Energy Systems, 2022, 10, 2169-3536, 111351, 10.1109/ACCESS.2022.3215954
    6. Jiahui Chen, UAV path planning method based on modeling in complex forest environment, 2024, 2824, 1742-6588, 012005, 10.1088/1742-6596/2824/1/012005
    7. Shuo Sun, Liang Ma, Yong Liu, Chunjian Shang, Volleyball premier league algorithm with ACO and ALNS for simultaneous pickup–delivery location routing problem, 2023, 149, 15684946, 111004, 10.1016/j.asoc.2023.111004
    8. Mingqiang Yin, Hao Wang, Qiang Liu, Xiaohu Qian, He Zhang, Xianming Lang, A sampling-based winner determination model and algorithm for logistics service procurement auctions under double uncertainty, 2025, 15, 2045-2322, 10.1038/s41598-025-94748-x
  • Reader Comments
  • © 2017 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(7658) PDF downloads(1038) Cited by(10)

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog