text:
Thank you for visiting nature.com. You are using a browser version with limited support for CSS. To obtain the best experience, we recommend you use a more up to date browser (or turn off compatibility mode in Internet Explorer). In the meantime, to ensure continued support, we are displaying the site without styles and JavaScript.

# A general pharmacodynamic interaction model identifies perpetrators and victims in drug interactions

## Abstract

Assessment of pharmacodynamic (PD) drug interactions is a cornerstone of the development of combination drug therapies. To guide this venture, we derive a general pharmacodynamic interaction (GPDI) model for ≥2 interacting drugs that is compatible with common additivity criteria. We propose a PD interaction to be quantifiable as multidirectional shifts in drug efficacy or potency and explicate the drugs’ role as victim, perpetrator or even both at the same time. We evaluate the GPDI model against conventional approaches in a data set of 200 combination experiments in Saccharomyces cerevisiae: 22% interact additively, a minority of the interactions (11%) are bidirectional antagonistic or synergistic, whereas the majority (67%) are monodirectional, i.e., asymmetric with distinct perpetrators and victims, which is not classifiable by conventional methods. The GPDI model excellently reflects the observed interaction data, and hence represents an attractive approach for quantitative assessment of novel combination therapies along the drug development process.

## Introduction

Combination therapies are prevalent in many therapeutic areas1, such as infectious diseases, oncology or neurology. There is a strong focus in drug development programs to early identify, quantify and evaluate pharmacokinetic (PK) interactions. However, for pharmacodynamic (PD) interactions, although at least equally important as PK, there is substantially less focus. Reasons for neglecting PD interactions may lay in the very heterogeneous methodological landscape2, statistical traps3,4, but also a general difficulty to adapt current PD interaction assessment methods to different stages of drug development.

Moreover, limitations of the current methodology landscape to evaluate PD interactions are numerous: (i) graphical approaches such as the isobologram method5, fractional inhibitory concentration (FIC) indices6 or the combination index7 are conceptually straightforward and useful, but their results are difficult to interpret when interactions are concentration dependent or isoboles are “curvilinear”8, e.g., when a combination partner is a partial agonist. (ii) Response surface approaches9 are a frequently employed in such situations as they can elucidate concentration dependencies in the interaction space but, as outlined above, cannot be used for calculating an interaction score or parameter such as FIC indices. As response surface analyses represent a pure comparison between observed and additive response, they cannot be used for longitudinal simulations of the observed interaction pattern at (changing) concentrations over time (PK–PD simulations). (iii) FIC indices, but also model-based approaches with a single interaction parameter10,11 provide interaction scores for statistical interaction assessment and can be compared, but the single point estimate might not mirror the complexity of response surfaces; model-based approaches with more interaction parameters, e.g., polynomials to describe the interaction surface12, might be more flexible to fit to the data, but their interaction polynomials are not interpretable. (iv) Most approaches are limited to two interacting drugs2,10, (v) tied to a single underlying additivity concept, or even no established additivity criterion12,13, and (vi) cannot be adapted to the various complexity of information obtained along the drug development process, i.e., reduced or more complex nested models of the same type can be applied. Finally, (vii) we aimed to explore the roles of each drug in PD interaction studies. Recent and current work is addressing these limitations, e.g., through more efficient factorial designs14, innovative mechanism-independent statistical models15, re-scaling techniques to facilitate correct interaction scoring in two16 and three drug combinations17,18. Moreover, the genetic impact on drug interactions is also increasingly studied19 to assess the genetic robustness of PD interactions.

Yet, all these efforts could be complemented by a general pharmacodynamic interaction (GPDI) model overcoming all limitations (i–vii). In addition, the GPDI model should (a) provide quantitatively interpretable interaction point estimates, (b) not require knowledge on the precise mode of action, (c) be flexible enough to adapt to multi-drug combination data of various complexity, (d) enable compatibility with established additivity criteria such as Loewe Additivity20 or Bliss Independence21, (e) provide insight into perpetrators and victims in PD interaction networks, (f) offer time-course prediction to avoid confounders arising from analysis of sole endpoint data22, and (g) allow for computer simulations for therapeutic profiling, bridging pre-clinical to clinical phase as well as clinical trial simulation.

In order to evaluate and compare the performance and interaction classification of the here newly derived GPDI approach against conventional methods, we utilize a large-scale high-throughput screening data set23. Isobole analysis5,23 and the Greco model24 as methods derived from Loewe Additivity, as well as an empiric Bliss Independence model23 are used as conventional approaches and compared to the result of the GPDI analyses.

## Results

### The general pharmacodynamic interaction model

Single drug effects were characterized with the sigmoidal maximal effect (Emax) model25,26, parameterized by PD parameters Emax (maximal drug effect), EC50 (drug concentration stimulating 50% of Emax, i.e., drug potency) and H (Hill factor for sigmoidicity). The concept of the GPDI approach is simple: we propose a PD interaction to be quantifiable as shift in Emax (allosteric type) or EC50 (competitive type), which provides an intuitive, mechanistically motivated, quantitative, and statistically interpretable (point) estimate of a PD interaction. A central aspect to the GPDI model is its ability to define perpetrators and victims of a PD interaction: a perpetrator alters the PD parameter of the victim drug leading to a PD interaction, i.e., either synergy or antagonism. The interactions in the GPDI approach are directionally quantified, i.e., the drug can take the role of perpetrator, victim, or even both at the same time. This definition of perpetrator and victim is to our best knowledge new in the context of PD interactions, yet similar to the use of such terms in the context of PK interactions, where, e.g., drug elimination of a victim drug is reduced by a perpetrator drug27. To include PD interactions, we extended the sigmoidal Emax model of the victim drug by a perpetrator sigmoidal Emax term (“GPDI term”) to capture the interaction effect on the level of the PD parameters. This concept generalizes the idea behind receptor-based interaction as suggested by Ariëns28. The PD interaction is parameterized by INT (maximum fractional change of the victims PD parameter caused by the perpetrator), EC50INT (interaction potency), and H INT (interaction sigmoidicity).

For example, for two drugs A and B with a competitive-type interaction (EC50-level), the drug effects E A and E B are given by

$$E_{\rm {A}} = \frac{{{{\rm Emax}}_{\rm {A}} \times \it C_{\rm {A}}^{H_{\rm {A}}}}}{{\left( {{\mathrm{EC5}}0_{\rm {A}} \times \left( {1 + \frac{{{\mathrm{INT}}_{{\mathrm{AB}}} \times C_{\mathrm{B}}^{H_{{\mathrm{INT,AB}}}}}}{{{\mathrm{EC}}50_{{\mathrm{INT}},{\mathrm{AB}}}^{H_{{\mathrm{INT}},{\mathrm{AB}}}} + C_{\mathrm{B}}^{H_{{\mathrm{INT,AB}}}}}}} \right)} \right)^{H_{\rm {A}}} + C_{\rm {A}}^{H_{\rm {A}}}}},$$
(1)
$$E_{\mathrm{B}} = \frac{{{\rm Emax}_{\mathrm{B}} \times \it C_{\mathrm{B}}^{H_{\mathrm{B}}}}}{{\left( {{\mathrm{EC}}50_{\mathrm{B}} \times \left( {1 + \frac{{{\mathrm{INT}}_{{\mathrm{BA}}} \times C_{\rm {A}}^{H_{{\mathrm{INT,BA}}}}}}{{{\mathrm{EC}}50_{{\mathrm{INT,BA}}}^{H_{{\mathrm{INT}},{\rm {BA}}}} + C_{\rm {A}}^{H_{{\mathrm{INT}},{\rm {BA}}}}}}} \right)} \right)^{H_{\mathrm{B}}} + C_{\mathrm{B}}^{H_{\mathrm{B}}}}},$$
(2)

INTAB represents the maximum fractional change of the EC50 of drug A (victim) caused by drug B (perpetrator), and vice versa for INTBA. INT=0 indicates no interaction, −1 < INT < 0 indicates a decrease of the EC50, and INT > 0 indicates an increase of the EC50. If both INT values are negative, synergy, and vice versa, antagonism is observed on the effect level. INT values of different polarities indicate an asymmetric interaction with concentration-dependent synergy and/or antagonism on the effect level. In addition, potentiation (inactive drug potentiates an active drug) or coalism (inactive drugs solely jointly active) can be modeled by the GPDI approach. Implementation of the GPDI model on EC50 leads to a competitive interaction behavior. An interaction of allosteric type is considered when the GPDI model is implemented on Emax. Note that the polarity of INT is opposite when implemented on Emax instead of EC50.

E A and E B are directly compatible with common additivity criteria to compute the combined effect including simple effect addition29 (E comb = E A + E B), Bliss Independence21 (E comb = E A + E BE A ·E B) or highest single agent2 (E comb = max(E A, E B)). The GPDI model is also compatible with Loewe Additivity, however solely for competitive-type interactions, as Loewe Additivity in its original definition20 requires a mutual maximum effect to exist:

$$\begin{array}{*{20}{c}} {1 = \frac{{C_{\rm {A}}}}{{{\mathrm{EC}}50_{\rm {A}} \times \left( {1 + \frac{{{\mathrm{INT}}_{{\mathrm{AB}}} \times C_{\mathrm{B}}^{H_{{\mathrm{INT}},{\mathrm{AB}}}}}}{{{\mathrm{EC}}50_{{\mathrm{INT}},{\mathrm{AB}}}^{H_{{\mathrm{INT}},{\mathrm{AB}}}} + C_{\mathrm{B}}^{H_{{\mathrm{INT,AB}}}}}}} \right) \times \left( {\frac{{E_{{\mathrm{comb}}}}}{{{\rm Emax}_{\rm {A}} - \it E_{{\mathrm{comb}}}}}} \right)^{1/H_{\mathrm{A}}}}}} \\ { + \frac{{C_{\mathrm{B}}}}{{{\mathrm{EC}}50_{\mathrm{B}} \times \left( {1 + \frac{{{\mathrm{INT}}_{{\mathrm{BA}}} \times C_{\rm {A}}^{H_{{\mathrm{INT,BA}}}}}}{{{\mathrm{EC}}50_{{\mathrm{INT,BA}}}^{H_{{\mathrm{INT,BA}}}} + C_{\rm {A}}^{H_{{\mathrm{INT,BA}}}}}}} \right) \times \left( {\frac{{E_{{\mathrm{comb}}}}}{{{\rm Emax}_{\mathrm{B}} - \it E_{{\mathrm{comb}}}}}} \right)^{1/H_{\mathrm{B}}}}}} \end{array},$$
(3)

Note that Loewe Additivity cannot be solved explicitly for E comb when EC50A≠EC50B and/or H AH B, but implicitly by root finding methods, as outlined in the Online methods.

Signature plots of the GPDI model using Bliss Independence and Loewe Additivity are presented in Fig. 1 displaying the flexibility of the GPDI approach as it can describe very different types of PD interactions. The GPDI approach enables to describe monodirectional interactions with a defined perpetrator drug (Fig. 1b, c, h, i, n–p), bidirectional interactions with both drugs being perpetrator on each other (Fig. 1d, e, f, j–l, q), interactions with itself inactive drugs leading to allosteric interactions (Fig. 1n, o), buffering (Fig. 1p) or coalism (Fig. 1q). We also confirmed the structural identifiability of the GPDI model in a conventional 8 by 8 checkerboard design with log2-diluations typically done in, e.g., anti-infective PD interaction screening. Anticipated median relative standard errors (10–90th percentile) were 8.2% (2.8–29.8%) for INT and 20.6% (9.6–53.4%) for EC50INT (Supplementary Fig. 1). A log2 dilution design is preferable over a linear design. While still being identifiable, the anticipated median relative standard errors were 30.0% (11.1–268%) for INT and 52.4% (23.2–339%) for EC50INT in the linear design.

GPDI models for more than two interacting drugs follow the same principle of quantifying the interaction on the level of the PD parameter and solely require one additional GPDI term per added drug to quantify a bidirectional interaction. If a third interaction partner alters the interaction between two drugs, as potentially observable in triple combinations, e.g., emergent synergies17, the interaction becomes tri-directional, and another interaction level (modulation) is added, i.e., a GPDI term on the INT parameter. Details on formulating the GPDI approach for more than two drugs are provided in the methods section.

In situations with less rich data, the full four-parameter GPDI model can be reduced to adapt to these situations: a joint interaction term, i.e., INT = INTAB = INTBA and/or interaction potency set to the drugs potency, i.e., EC50INT = EC50, lead to a reduced one-parameter GPDI interaction model. It should be noted that the reduced GPDI models retain the interpretability of the interaction parameter. The GPDI model is applicable to other single drug exposure response models, e.g., slope or power effect model. Details for reduced models and other single drug exposure response models are provided in the Methods.

### Application of GPDI and comparison to conventional methods

To evaluate the GPDI approach against conventional approaches, we used a pre-clinical study by Cokol et al.23, who recorded the 24 h time-courses of fungal growth under perturbation of 200 antifungal and non-antifungal drug combinations. We fitted the Loewe Additivity- (Eq. (3)) and Bliss Independence-based GPDI models (E comb = E A + E B-E A·E B with E A and E B given in Eq. (1) and Eq. (2)). Model building started with a reduced GPDI model with a single interaction parameter INT and was extended to the full four-parameter GPDI model, which was significant (α = 0.05, likelihood ratio test) in 152/200 scenarios (Loewe Additivity) or 167/200 (Bliss Independence). No interaction sigmoidicites (H INT) were estimated. For the conventional models, we evaluated the isobole analysis5,23 and the Greco model24 as approaches based on Loewe Additivity, and an empiric Bliss Independence model23. The two different GPDI models provided an excellent performance to describe the observed time-courses of the (combined) effects, and were highly superior to the alternative models which did not describe the observed data well (Fig. 2, see Supplementary Data 1 for all evaluated 200 combination scenarios). This could also be objectified by assessing the respective distributions of the Akaike information criterion (AIC) (lower value indicates better model fit): AIC was in median (10–90th percentile) −29901.71 (−36805.3; −23776.7) for the Loewe Additivity-based GPDI model and −30377.43 (−37751.6; −24823.2) for Bliss Independence-based GPDI model. Hence, the Loewe Additivity- and Bliss Independence-based GPDI models described the experimental data similarly well and were superior over the Greco model and the empiric Bliss Independence model which provided median AIC of −26989.4 (−35033.9; −17586.3) and −26152.5 (−33856.2; −18616.7), respectively. The modeled vs. observed time-courses of the PD interactions of all 200 scenarios for the GPDI and the conventional methods are provided in Supplementary Data 1. It should be noted that the conventional models solely have a single interaction parameter while the GPDI approach has up to four, but the high rate of statistical significance of the four parameter GPDI model in conjunction with the lower AIC values indicate that the additional parameters are highly supported. We did not evaluate allosteric-type interactions in the Cokol data set, as the “true” maximum antifungal effect may be fungicidal and hence beyond the turbidity threshold indicative merely for fungistasis.

For both Loewe Additivity and Bliss Independence-based GPDI models, in 199/200 scenarios, at least one statistically significant INT parameter was indicated by the likelihood ratio test. The full GPDI model was identified in ≥152/200 scenarios. As pure statistical significance can be misleading in rich-scale data, and to account for experimental variability in the data set, we used 25 sham combination experiments (drug A = drug B) in the Cokol data set to define an additivity margin for INT to conclude if significant antagonism or synergy was quantified: For the Loewe Additivity-based GPDI model, INT at the EC50 of the perpetrator was in median 0.025 (10–90th percentile: −0.47 to 0.5). Hence, the additivity margin was defined to lay within a 57–150% change of the victim EC50 at the EC50 of the perpetrator drug. For simplicity, we set the additivity margin to −0.5 to 0.5 for our analysis (cf. square in Fig. 3a–d). We used the same additivity margin in the Bliss Independence-based GPDI analysis due to the identical nature of the INT parameter, since there was a tendency to synergy of the INT values in the sham combinations with Bliss Independence (median: −0.378, 10–90th percentile: −0.639, 0.452). Self-synergy is an expected property of the Bliss Independence criterion as a drug’s action cannot be independent from itself10. For the conventional methods, the interaction parameter α of the Greco model for the sham combinations was in median 0.23 and the 10–90th percentile (−0.45, 0.82) was used as additivity margin. For the empiric Bliss model, the interaction parameter β of the sham combinations and hence the additivity margin ranged from −14,836 to 1.49 (10–90th percentile) and was −42.2 in median, hence as expected also displayed a tendency to self-synergy.

In the Cokol data set, 175 of the 200 scenarios comprised “true” combination experiments. For the Loewe Additivity-based GPDI analysis, the following scenarios were quantified: Additive interactions, i.e., both INT parameters within the additivity margin, were observed in 38/175 of the scenarios.

Two types of symmetric interactions were observed in 19/175 scenarios: (i) bidirectional synergy, where both INT parameters indicated synergy (< −0.5), i.e., both drugs were perpetrator and victim at the same time reducing each the others’ EC50 values were found in 6/175 scenarios, and (ii) bidirectional antagonism: Both INT parameters indicated antagonism (>0.5), i.e., both drugs are perpetrator and victim at the same time increasing each the others’ EC50 values were found in 13/175 scenarios.

Three types of asymmetric interactions were observed in 118/175 scenarios: (i) monodirectional synergy, where one INT parameter indicated synergy (< −0.5), i.e., there was one perpetrator reducing the EC50 of the victim, while the other INT parameter was within the additivity margin, was observed in 20/175 scenarios, (ii) monodirectional antagonism, where one INT parameter indicated antagonism (>0.5), i.e., there was one perpetrator increasing the EC50 of the victim, while the other parameter was within the additivity margin, was observed in 76/175 scenarios, (iii) bidirectional asymmetric interactions, where both INT parameters were outside the additivity margin, but of opposite polarity, i.e., both drugs were perpetrator and victim at the same time increasing or decreasing each other’s EC50 values leading to concentration-dependent antagonism or synergy, was observed in 22/175 scenarios.

While the overall conclusions on antagonism and synergy were in general agreement with the Loewe-based original isobole analysis of Cokol et al.23 (Fig. 3a) and the result of the Greco model (Fig. 3c), it is evident that the direction of the interaction, i.e., the perpetrator–victim properties and the bidirectional asymmetric type interaction (cf. Fig. 1f) could not be classified with the conventional methods. 6 of these bidirectional asymmetric interaction were (wrongly) classified as additive, 14 as synergistic and 2 as antagonistic. Agreement between the Greco model and the isobole analysis was high and the approaches resulted in the same classification in 82% of the scenarios.

For the Bliss Independence-based GPDI analysis, a substantially higher synergy rate was found (monodirectional synergy: 30/175, bidirectional synergy: 14/175). Also, a higher rate of additive interactions was observed (79/175), 31/175 displayed monodirectional antagonism and only 2/175 interactions displayed bidirectional antagonism. 19/175 scenarios displayed bidirectional asymmetric interactions. The tendency to estimate a higher synergy rate with Bliss Independence is also apparent in Supplementary Fig. 2 when the estimated interaction parameters of Loewe Additivity and Bliss Independence-based GPDI models were compared. The Bliss Independence-based GPDI model did not agree with the isobole analysis, due to the different underlying additivity criterion (Fig. 3b). It agreed with the empiric Bliss Independence model (Fig. 3d) only when INT terms were of same polarity, but the empiric Bliss model was much less sensitive to detect interactions as indicated by the large number of misclassified additive interactions. The parameter values of the GPDI models as well as for the alternative models are visualized and compared in Fig. 4. A re-analysis of the Cokol data set30 revealed 61 suppressive interaction, i.e., strong antagonistic interactions with responses below one of either or both single agents. While a screen for suppressive interactions on the effect level using the GPDI approach is similar to the approach chosen by Cokol30 (comparison of the combined effects with the single drug effects), the GPDI approach can enhance suppressive interactions with model-based estimates of perpetrator–victim information guided by the INT parameter. 66% of manually derived directions (assuming that the less potent drug antagonizes the more potent drug in these suppressive interactions30) were in agreement with the GPDI analysis, while in the remaining cases different and/or additional directions of the PD interactions were quantified (Supplementary Table 2). This indicates that the assumption that the less potent drug is the causative agent of suppression on the effect level is often, but not always true.

### Perpetrators and victims in a drug interaction network

In order not to bias ourselves towards a single additivity criterion, we exclusively joined the result of the Loewe-Additivity and Bliss-Independence-based GPDI models for the network analysis, i.e., included solely interactions that were significant under both Loewe-Additivity and Bliss-Independence, which is displayed in Fig. 5a. The unjoined networks are presented in Supplementary Fig. 3. In the joined data set, 90 interactions (edges of the network) were observed where 54 of the interactions were mono-directional with one combination partner being perpetrator and the other being victim drug. 36 interactions were bidirectional, in which both combination partners were perpetrator and victim drug at the same time, and 12 out of the bidirectional interactions displayed INT values of joint polarity. 10 of these 12 were bidirectional synergies, e.g., as observed with the drugs Fen and Cal. 2 of these 12 were bidirectional antagonistic interactions (Cyc-Rad) and 24 interactions were bidirectional asymmetric interactions, e.g., drug Ben was antagonistic on drug Tac, but Tac potentiated the effect of Ben and concentration-dependent antagonism or synergy is observed (Supplementary Fig. 4). Another example is the drug Ter, which is part of a larger number of synergies. It has been speculated that Ter mediates synergy through its cell-wall disrupting effect which in turn might enhance the uptake of other drugs23. When comparing the GPDI parameters of interactions where Ter was involved, diverse interactions were observed (Supplementary Table 3). Yet, in the majority of the scenarios (5/11), Ter decreased the EC50 or did not significantly affect the combination partners (4/11), which might corroborate the proposed mechanism, but also indicates that further yet unknown processes are affected which also alter the EC50 of Ter. Through its effect in the ergosterol pathway, Ter can also mediate monodirectional antagonism, e.g., as perpetrator on AmB, for which the INT value of 3.32 suggested an increase in EC50 to 432% ((1 + 3.32)*100%) at the EC50 of Ter, while the EC50 of Ter was not significantly altered. AmB binds ergosterol in the cell wall; it has been proposed that AmB might lose its target when ergosterol synthesis is inhibited31, which would be in agreement with the observed INT values and the identified perpetrator role of Ter from the GPDI analysis. Of the mono-directional interactions, drugs Bro, Cis, Hyg, Met and Qnn were sole perpetrators being all antagonistic on their combination partners, but never took the victim role. For Bro, there is evidence that the antagonistic interactions observed with Bro are mediated by its acidity unrelated to its precise mode of action30. This distinct pattern is also found in the GPDI parameters: Bro increased the EC50 of its combination partners in 9/10 cases as perpetrator, while it was never affected itself, i.e., Bro mediated solely monodirectional antagonistic interactions (Supplementary Table 4). This indicates that the effects mediated by Bro itself might not be affected by the combination partners. Drugs Qmy, Tun, Rap, Myr and C3P were sole victim drugs, but never took the perpetrator role. Drug Tac was the most prevalent perpetrator for potentiation in 11 interactions, but 5 of those were antagonistically “counteracted” by the victim. Drug Tac was also the most prevalent victim for antagonism in 9 interactions. For a large number of these interactions in the Cokol data set, the underlying mechanism of interaction remains to be elucidated. Further research is required to elucidate the molecular interaction mechanisms to which the GPDI model might contribute by adding quantitative measures of EC50 shifts and perpetrator–victim information in order to profile the behavior of the drugs in interaction networks (Fig. 5b–e).

## Discussion

Accurate characterization of PD interactions is of key importance for defining rational combination therapies. In this paper, we derive the novel GPDI approach for this purpose. When parameterizing the GPDI model parameters from the experimental data, the GPDI approach is complex enough to provide “spot-on” description of the observed time-courses of PD interactions in a data set of 200 combination experiments, including concentration-dependent interactions, but thereby still providing intuitive interaction parameters as fractional changes of the PD parameters and interaction potencies. For example, as illustrated in Fig. 2a, b, INTAB was determined to −0.02, i.e, the EC50 of drug A (Bro, bromopyruvate) was only marginally affected. Instead, INTBA was determined to 15.92, i.e., in combination the EC50 of drug B (Sta, staurosporine) was increased to 1692% ((1 + 15.92)*100%) at the EC50 of Bro. It is obvious, that the parameter α and β of the conventional models (Fig. 2c, d) cannot be quantitatively interpreted in a similar way.

As the inferences are drawn on the level of the model parameters and from all available scenarios of the checkerboard at the same time, no re-scaling on the effect level16,17,18 is required, which is yet a helpful technique to score and detect interactions in individual scenarios. The GPDI approach revealed that the majority of up to 67% of the interactions in this data set were of asymmetric nature where distinct perpetrator and victim information in the PD interactions was quantified, i.e., monodirectional synergism, monodirectional antagonism, and asymmetric bidirectional interactions where synergism or antagonism depends on the concentration ratio of the drugs. This could not at all be classified by the conventional approaches5,10,23 (Fig. 3). Concentration dependence in the PD interactions has also been a challenge in a recent study, that labeled these as “inconclusive”32. Moreover, the effect of itself inactive drugs on other active drugs could not be evaluated with conventional methods23, which is possible with the GPDI approach.

The GPDI approach elicits the roles of perpetrator and victim in PD interactions and hence provided directed interaction networks as seen in Fig. 5. Such a directed interaction network opens up pivotal opportunities for cluster analyses to detect similarities of the drug’s roles in large-scale interaction networks32,33. A recent study also addressed this important aspect of considering a direction in PD interactions34 employing a two-parameter model. Yet, the approach they used is less versatile than the GPDI approach, as (i) they do not quantify an interaction on the level of the PD parameters, (ii) no modulation can be considered (cf. Eq. 12), (iii) their interaction parameter is not as easily interpretable, (iv) their approach is implemented solely in Bliss Independence, and (v) there model is likely less flexible than the GPDI approach which can use from one to four GPDI model parameters depending on the richness of the data. Higher-order combinations with three or more interacting drugs are not part of this work, but have been successfully modeled by statistical models15. Emergent synergies, i.e., synergistic effect only being present in three drug combination, but not in either dual combination35, have been discovered recently. The GPDI model also can account for such “emergent interactions” through the modulator-term (Eqs. (11) and (12)). Recently, the presented GPDI model approach was applied in four drugs combinations in tuberculosis in vitro36 and in vivo studies37, where such interactions were also present and quantified by the GPDI model.

The GPDI approach advances receptor-based competitive or allosteric interaction models to the next evolutionary step by adding estimable interaction parameters for fractional change of the PD parameter and interaction potency, thereby being in accordance with the criteria for an ideal PD interaction model12. Moreover, the GPDI approach within Bliss Independence also covers scenarios which cannot be quantitatively modeled by conventional methodology such as pure potentiation or intertism, i.e., when solely one drug is active and its effect is or is not altered by an itself inactive drug, or coalism, i.e., when neither drug is active alone, but a combined effect is observed.

There is a controversy on which additivity criterion to use in PD interaction studies. Loewe Additivity10,20 assumes that two drugs act through a similar mode of action, leading to the conception of “dose substitution”, i.e., a fraction of drug A can be replaced by drug B leading to the same effect. Bliss Independence10,21, however, assumes that drugs act independently through distinct mechanisms. The GPDI approach solves this controversy by unifying the interpretation of deviation from all these additivity criteria in a model-based framework. Our analysis of 200 combination experiments displayed that using Loewe Additivity or Bliss Independence can lead to different conclusions regarding synergy or antagonism on the observed interaction, yet by providing similar descriptive performance. With the GPDI approach, the analyst can decide on the most suitable interaction criterion for the present data, or as in the present work exclusively join the result of the modeling activities to select “strong” interactions that stick out under both additivity criteria. Yet, it should be noted that both the Loewe- and Bliss-based GPDI models described the observed data equally well. Hence, both would be suitable for performance of computer simulations, e.g., for therapeutic profiling of the PD interactions38 from pre-clinical to clinical phase or for clinical trial simulations, irrespective of the “true” underlying system. We also demonstrated that the investigated conventional approaches were not suitable to describe the data well and hence may not provide unbiased simulations if these models were used in translational predictions or combined dose finding.

The GPDI approach considers that PD might not be as simple as only synergism or antagonism, but the fact that PD interactions are a function of concentration and might be multi-dimensional, i.e., that the interaction changes in the concentration space. Moreover, the GPDI approach comes with further numerous advantages over existing approaches, which comprise quantitatively interpretable interaction point estimates across Loewe Additivity and Bliss Independence, no requirement of prior knowledge on the precise mode of (inter-)action, flexibility to adapt to multi-drug combination data of various complexity, compatibility with established additivity criteria, provision of insight into perpetrators and victims in PD interaction networks, and the possibility to describe time-courses of the interaction. Future studies should also evaluate the utility of the GPDI approach at other EC levels or the stationary concentration39 as potency markers. Utilization of the GPDI approach in drug development opens up new perspectives for modeling, interpretation, quantitative decision marking and hypothesis generation in development of novel combination therapies.

## Methods

### The general pharmacodynamic interaction model

We used the sigmoidal maximum effect model25,26 for quantifying single drug effects. This model describes the drug effect E as function of its concentration C and the model parameters Emax (maximal drug effect), EC50 (drug concentration stimulating 50% of Emax, i.e., drug potency) and H (Hill factor for sigmoidicity):

$$E\left( C \right) = \frac{{{\rm Emax} \times C^H}}{{{\mathrm{EC}}50^H + C^H}}.$$
(4)

The GPDI approach evolved from receptor-based models such as the competitive inhibition model, as proposed by Ariëns28

$$E_{\rm {A}}\left( {C_{\rm {A}},C_{\mathrm{I}}} \right) = \frac{{{\rm Emax}_{\rm {A}} \times C_{\rm {A}}}}{{\left( {K_{\mathrm{d}} \times \left( {1 + \frac{{C_{\mathrm{I}}}}{{K_{\mathrm{I}}}}} \right)} \right) + C_{\rm {A}}}},$$
(5)

expressing the induced effect E A of drug A at a concentration C A with a drug–receptor dissociation constant K d and an inhibitor I at a concentration C I and the inhibitor-receptor dissociation constant K I. The GPDI model generalized the interaction term (1 + C I /K I) using a maximum effect model with estimable interaction parameters (the “GPDI term”) which allows both positive and negative shift of the PD parameter. The GPDI term is a function of the perpetrator drug concentration, which perturbs a PD parameter θ of the victim drug. The GPDI model is parameterized by INT representing the maximum possible fractional change of the PD parameter θ, EC50INT which quantifies the potency of the perpetrator and H INT, the sigmoidicity of the interaction effect.

$$\theta \times \left( {1 + \frac{{{\mathrm{INT}} \times C^{H_{{\mathrm{INT}}}}}}{{{\mathrm{EC}}50_{{\mathrm{INT}}}^{H_{{\mathrm{INT}}}} + C^{H_{{\mathrm{INT}}}}}}} \right).$$
(6)

The GPDI model considers that two drugs can potentially be both perpetrator and victim drug at the same time, hence quantifies bidirectional interactions. For two interaction partners with an interaction on the PD parameter EC50, the GPDI model is given by:

$$E_{\rm {A}} = \frac{{\rm Emax_{\rm {A}} \times C_{\rm {A}}^{H_{\rm {A}}}}}{{\left( {{\mathrm{EC}}50_{\rm {A}} \times \left( {1 + \frac{{{\mathrm{INT}}_{{\mathrm{AB}}} \times C_{\mathrm{B}}^{H_{{\mathrm{INT,AB}}}}}}{{{\mathrm{EC}}50_{{\mathrm{INT,AB}}}^{H_{{\mathrm{INT,AB}}}} + C_{\mathrm{B}}^{H_{{\mathrm{INT,AB}}}}}}} \right)} \right)^{H_{\rm {A}}} + C_{\rm {A}}^{H_{\rm {A}}}}},$$
(7)
$$E_{\mathrm{B}} = \frac{{{\rm Emax}_{\mathrm{B}} \times C_{\mathrm{B}}^{H_{\mathrm{B}}}}}{{\left( {{\mathrm{EC}}50_{\mathrm{B}} \times \left( {1 + \frac{{{\mathrm{INT}}_{{\mathrm{BA}}} \times C_{\rm {A}}^{H_{{\mathrm{INT,BA}}}}}}{{{\mathrm{EC}}50_{{\mathrm{INT,BA}}}^{H_{{\mathrm{INT,BA}}}} + C_{\rm {A}}^{H_{{\mathrm{INT,BA}}}}}}} \right)} \right)^{H_{\mathrm{B}}} + C_{\mathrm{B}}^{H_{\mathrm{B}}}}},$$
(8)

INT can take values between −1 and ∞ and guides the direction of the PD interaction: zero indicates no interaction, a negative value between −1 and 0 indicates potentiation and a positive value between 0 and ∞ indicates inhibitory behavior of the perpetrator. If both INT values are between −1 and 0, synergy is observed. Also potentiation (one drug active) or coalism (inactive drugs solely jointly active) can be modeled by the GPDI approach. If both INT values are positive, antagonism is observed. Implementation of the GPDI model on EC50 leads to a competitive interaction behavior. An interaction of allosteric type is considered when the GPDI model is implemented on Emax. Note that the polarity of INT is opposite when implemented on Emax instead of EC50.

The GPDI model is also applicable when the drug effect is described by a linear slope model (E = SLOPE·C) or power model (E = SLOPE·C H), which are identified if the highest studied concentration is well below the EC50. As SLOPE represents Emax/EC50, the GPDI term is both valid in numerator or denominator. Depending on this choice, the INT value will have the same interpretation as fractional change of EC50 (denominator) or Emax (numerator) for the slope model. For the power model, the implementation in the denominator will only approximate the fractional change of EC50, as in the power model the slope represents Emax/EC50H.

Given that the GPDI model quantifies PD interactions at the level of the PD parameters, it is compatible with commonly used additivity criteria, such as Loewe Additivity20, Bliss Independence21 or simple effect addition2. The equations for the GPDI terms in the different additivity criteria are provided below in the application study section.

### The GPDI model for multiple interaction partners

The GPDI model can be extended to quantify drug interactions between drugs A to n by additional GPDI model terms for each additional drug on each PD parameter θ A,,m (interaction sigmoidicities H INT not displayed to ease readability):

$$\theta _{{\rm {A}}, \ldots ,m} \times \mathop {\prod }\limits_{i = 1}^n \left( {1 + \frac{{{\mathrm{INT}}_{{\rm {A}},n} \times C_n}}{{{\mathrm{EC}}50_{{\mathrm{INT}},{\rm {A}},n} + C_n}}} \right).$$
(9)

Hence, for three drugs A, B and C, the bi-directional GPDI model for E A is formulated as follows:

$$E_{\rm {A}} = \frac{{{\rm Emax}_{\rm {A}} \times C_{\rm {A}}^{H_{\rm {A}}}}}{{\left( {{\mathrm{EC}}50_{\rm {A}} \times \left( {1 + \frac{{{\mathrm{INT}}_{{\mathrm{AB}}} \times C_{\mathrm{B}}}}{{{\mathrm{EC}}50_{{\mathrm{INT}},{\mathrm{AB}}} + C_{\mathrm{B}}}}} \right) \times \left( {1 + \frac{{{\mathrm{INT}}_{{\mathrm{AC}}} \times C_{\mathrm{C}}}}{{{\mathrm{EC}}50_{{\mathrm{INT,AC}}} + C_{\mathrm{C}}}}} \right)} \right)^{H_{\rm {A}}} + C_{\rm {A}}^{H_{\rm {A}}}}}.$$
(10)

If a drug modulates the interaction between two other drugs, another level of interaction (modulation) using the GPDI model can be implemented. If drug C modulates the interaction between A and B, the effect of drug A in presence of B and C can be formulated as follows:

$${E_{\rm {A}} = \frac{{{\rm Emax}_{\rm {A}} \times C_{\rm {A}}^{H_{\rm {A}}}}}{{\left( {{\mathrm{EC}}50_{\rm {A}} \times \left( {1 + \frac{{{\mathrm{INT}}_{{\mathrm{AB}}} \times \left( {1 + \frac{{{\mathrm{INT}}_{{\mathrm{AB}}|{\mathrm{C}}} \times C_{\mathrm{C}}}}{{{\mathop{\rm{EC}}\nolimits}50_{{\mathrm{INT}},{\mathrm{AB}}|{\mathrm{C}}} + C_{\mathrm{C}}}}} \right) \times C_{\mathrm{B}}}}{{{\mathrm{EC}}50_{{\mathrm{INT,AB}}} + C_{\mathrm{B}}}}} \right) \times \left( {1 + \frac{{{\mathrm{INT}}_{{\mathrm{AC}}} \times C_{\mathrm{C}}}}{{{\mathrm{EC}}50_{{\mathrm{INT,AC}}} + C_{\mathrm{C}}}}} \right)} \right)^{H_{\rm {A}}} + C_{\rm {A}}^{H_{\rm {A}}}}}.}$$
(11)

The quantitative interpretation of the modulation parameter INTAB|C is comparable to the interpretation of INTAB: a value of zero indicates no modulation, a negative value between −1 and 0 indicates a positive modulation, and a value between 0 and ∞ indicates and negative modulation of the interaction between A and B.

One modulation level can be added for each additional drug, e.g., in our example an additional GPDI model term of a fourth drug D on INTAB|C:

$${E_{\mathop{\rm A}\nolimits} = \frac{{{\rm Emax}_{\rm {A}} \times C_{\rm {A}}^{H_{\rm {A}}}}}{{\left( {{\mathrm{EC}}50_{\rm {A}} \times \left( {1 + \frac{{{\mathrm{INT}}_{{\mathrm{AB}}} \times \left( {1 + \frac{{{\mathrm{INT}}_{{\mathrm{AB}}|{\mathrm{C}}}\left( {1 + \frac{{{\mathrm{INT}}_{\left( {{\mathrm{AB}}|{\mathrm{C}}} \right)|{\mathrm{D}}} \times C_{\mathrm{D}}}}{{{\mathrm{EC}}50_{{\mathrm{INT}},\left( {{\mathrm{AB}}|{\mathrm{C}}} \right)|{\mathrm{D}}} + C_{\mathrm{D}}}}} \right) \times C_{\mathrm{C}}}}{{{\mathrm{EC}}50_{{\mathrm{INT}},{\mathrm{AB}}|{\mathrm{C}}} + C_{\mathrm{C}}}}} \right) \times C_{\mathrm{B}}}}{{{\mathrm{EC}}50_{{\mathrm{INT,AB}}} + C_{\mathrm{B}}}}} \right) \times \ldots } \right)^{H_{\rm {A}}} + C_{\rm {A}}^{H_{\rm {A}}}}}.}$$
(12)

### Parameterization of the GPDI model from experimental data

For estimation of the GPDI model parameters from PD drug interaction studies, we propose the following stepwise regression approach using, e.g., maximum likelihood estimation: in the first step, the combination data is excluded from the analysis and solely the single drug effects are characterized by Emax, EC50, and H.

In the second step, the single drug effect parameters are fixed and solely the duo combination data is analyzed. A reduced GPDI model with a single interaction parameter INT = INTAB = INTBA and EC50INT = EC50 is evaluated first. The evolution from the reduced to the full GPDI model with all interaction parameters is guided by goodness-of-fit evaluation and statistical significance. As reduced GPDI models are nested within the full GPDI model, in maximum likelihood estimation, the likelihood ratio test can guide if an additional GPDI parameter is significant; i.e., a 3.84 drop in the objective function value is required to support inclusion of an additional parameter at α = 0.05. For duo combination data, the final mathematical model is obtained at this stage.

In the third step, if trio combinations are available, the parameters of the single drug effects and the GPDI parameters from step two are fixed and modulator terms (e.g., INTAB|C) are tested on the trio data. Inclusion of modulator parameters is again guided by goodness-of-fit evaluation and statistical significance. Step three is repeated for each additional drug that to estimate further modulator terms. In each step, a reduced GPDI model, as outlined in step two, is tested first and expanded in a stepwise manner.

In the final step, the parameters of the mathematical model identified in the previous step are all unfixed and estimated to determine parameter precision.

### Identifiability analysis of the GPDI model

To assess the structural identifiability of the GPDI model parameters, we performed 1000 computer simulations in an 8 by 8 checkerboard design with concentration tiers ranging from 0 to 8 (arbitrary concentration unit) in base 2 logarithmic steps. Model parameters of the Bliss Independence-based GPDI model were randomly sampled from uniform distributions with Emax  {0.5, 1.0}, EC50  {0.5, 2.0}, H {1.0, 4.0}, INT  {−0.9, −0.5}  {0.5, 20}, and EC50INT {0.1, 1.0}. The standard deviation on effect level was set to 0.03 resembling a typical variability observed as, e.g., in in vitro PD interaction studies with antibiotics9. A linear dilution scheme was also assessed where the EC50 values where placed in the 40–60% range of the highest concentration studied, while all other parameters were as described above. Anticipated relative standard errors of the GPDI model parameters were calculated from the expected Fisher information matrix FIM:

$${\mathrm{FIM}} = \frac{1}{{\sigma ^2}}\left( {J \cdot J^T} \right),$$
(13)

where σ 2 is the residual variance and J is the Jacobian, i.e., the matrix of first-order derivatives with respect to the GPDI model parameters. Anticipated standard errors were calculated from the square root of the diagonal elements of the inverse FIM and normalized by the parameter value to obtain relative standard errors.

### Comparison to conventional methods

A published data set by Cokol et al.23 was used to evaluate the performance of the GPDI model and conventional methods. The different models were fitted to the data set, the performance was evaluated by goodness-of-fit (modeled vs. observed time-courses of the (combined) drug effects), and the conclusions from the GPDI and conventional approaches were compared.

The Cokol data set comprises 200 drug–drug combination scenarios evaluating the growth of Saccharomyces cerevisiae under (joint) drug exposure of various drugs in an 8 by 8 checkerboard fashion. A longitudinal growth model40 was formulated as ordinary differential equation system and used to describe fungal growth (measured by optical density (OD) at 600 nm, with OD=S 1 + S 2) over time with k lag, the delay rate constant to quantify lag of onset of fungal growth, k growth, the rate constant for fungal growth being limited by the carrying capacity B max and inhibited by the (joint) drug effect E:

$$\frac{{{\mathrm{d}}S_1}}{{{\mathrm{d}}t}} = - S_1 \times k_{{\mathrm{lag}}},$$
(14)
$$\frac{{{\mathrm{d}}S_2}}{{{\mathrm{d}}t}} = S_1 \times k_{{\mathrm{lag}}} + S_2 \times k_{{\mathrm{growth}}} \times \left( {1 - \frac{{S_2}}{{B_{{\mathrm{max}}}}}} \right) \times \left( {1 - E_{{\mathrm{comb}}}} \right).$$
(15)

The (joint) drug effect E was computed by the GPDI model implemented into either Bliss Independence (E comb = E A+E BE A·E B with E A and E B given in Eq. (1) and Eq. (2)) or Loewe Additivity (Eq. (4)). PD interactions between the drugs in the data set were captured using the competitive-type GPDI approach with interaction parameters on the level of EC50 (Eq. (9)). Given that the read-out for the antifungal effect was optical density, no alteration of the maximum effect was visible as it occurred beyond the turbidity threshold; hence Emax was set to 1 ( = full inhibition of growth) in the analysis of the Cokol data set and no allosteric interactions could be evaluated.

Conventional approaches derived from Loewe Additivity and Bliss Independence were also evaluated: The Greco model,24

$$\begin{array}{l}1 = \frac{{C_{\rm {A}}}}{{{\mathrm{EC50}}_{\rm {A}} \times \left( {\frac{E}{{{\rm Emax}_{\rm {A}} - E}}} \right)^{1/H_{\rm {A}}}}} + \frac{{C_{\mathrm{B}}}}{{{\mathrm{EC50}}_{\mathrm{B}} \times \left( {\frac{E}{{{\rm Emax}_{\mathrm{B}} - E}}} \right)^{1/H_{\mathrm{B}}}}},\\ \,\,\,\, + \frac{{ \propto \times C_{\rm {A}} \times C_{\mathrm{B}}}}{{{\mathrm{EC50}}_{\rm {A}} \times {\mathrm{EC50}}_{\mathrm{B}} \times \left( {\frac{E}{{{\rm Emax} - E}}} \right)^{\left( {\frac{1}{{2H_{\rm {A}}}} + \frac{1}{{2H_{\mathrm{B}}}}} \right)}}}\end{array}$$
(16)

in which PD interactions were quantified by an empirical factor α, in which α=0 indicated Loewe Additivity, α < 0 antagonism and α > 0 synergy, and

an empiric Bliss interaction model,23

$$E = E_{\rm {A}} + E_{\mathrm{B}} - \beta \times E_{\rm {A}} \times E_{\mathrm{B}},$$
(17)

in which β=1 indicated Bliss Independence and β > 1 antagonism and β < 1 synergy were utilized, and E A and E B represent ordinary sigmoidal maximum effect models.

Moreover, we compared the GPDI results against the Loewe Additivity-based isobole analysis method performed in the original study23. In an isobole analysis, the shape of an isobole, i.e., a line of the same effect, is analyzed. A linear isobole indicates Loewe Additivity, an isobole bent towards the origin indicates synergy, and vice versa antagonism. This curvature was quantified by a score parameter γ on the longest isophenotypic curve on the checkerboard that used the area under the time-kill curve, normalized by the area of the growth curve as effect metric, with

$$\gamma = \log \left( {\frac{x}{{1 - x}}} \right) - \log \left( {\frac{y}{{1 - y}}} \right),$$
(18)

where x and y are MIC-normalized drug concentration and γ described the bend of the isobole. γ=0 indicated linear isoboles, i.e., Loewe Additivity, and for γ < 0 or γ > 0, synergy or antagonism, respectively, was determined.

Parameter estimation and data processing was performed in “R” (version 3.2.4, R Foundation for Statistical Computing, Vienna, Austria). Differential equations were solved using the “deSolve” package41,42 (version 1.13). To increase performance, differential equations were encoded in C, compiled as dynamically linked library (.dll) and linked to the “deSolve” interface. Model parameters were estimated with “optim” from “stats” (version 3.2.4) using maximum likelihood estimation. The GNU scientific library for C43 was used to provide root finding functionality within the ODE system for the Loewe Additivity models.

The results of the GPDI models and conventional models were compared regarding their performance by comparing modeled vs. observed time-courses of the anti-fungal effects. The AIC was calculated as an objective measure of model fit. Moreover, the classification result of the GPDI models and conventional models, i.e., if an interaction was additive, antagonistic or synergistic was assessed. Therefore, the result of estimated interaction parameters INTAB and INTBA were plotted normalized to the EC50 of the perpetrator drug. Positive INT values indicated antagonism; negative INT values indicated synergy and INT parameters are of opposite polarity indicated asymmetric PD interactions where the apparent synergy or antagonism is a function of the concentration. The classification result of the conventional approaches was mapped to this INTAB–INTBA plot by color coding.

### Network analysis

For visualization of the interactions, we chose a network plot with vertices being the drugs and the directed edges representing the detected directed interactions in the data set. In order to focus on the important interactions, the INT values of the victim drug at EC50 of the perpetrator drug being outside the additivity margin from both the Loewe-Additivity- and Bliss-Independence-based GPDI analysis were exclusively joined, i.e., only the interaction sticking out from both additivity criteria were displayed. The “igraph”-package44 (version 1.0.1) in “R” was used for creating this network. The drugs were profiled for perpetrator and victim behavior.

### Code availability

The model code of the GPDI model in the “R” language is provided as Supplementary Software 1.

### Data availability

The utilized data set in the present work has been previously published by Cokol et al.23 and can be accessed in the supplement of their publication.

## References

1. 1.

Jia, J. et al. Mechanisms of drug combinations: interaction and network perspectives. Nat. Rev. Drug Discov. 8, 111–28 (2009).

2. 2.

Foucquier, J. & Guedj, M. Analysis of drug combinations: current methodological landscape. Pharmacol. Res. Perspect. 3, e00149 (2015).

3. 3.

Ashton, J. C. ANOVA and the analysis of drug combination experiments. Nat. Methods 12, 1108 (2015).

4. 4.

Blainey, P., Krzywinski, M. & Altman, N. Points of significance: replication. Nat. Methods 11, 879–880 (2014).

5. 5.

Tallarida, R. J. An overview of drug combination analysis with isobolograms. J. Pharmacol. Exp. Ther. 319, 1–7 (2006).

6. 6.

Odds, F. C. Synergy, antagonism, and what the chequerboard puts between them. J. Antimicrob. Chemother. 52, 1 (2003).

7. 7.

Chou, T. C. Drug combination studies and their synergy quantification using the chou-talalay method. Cancer Res. 70, 440–446 (2010).

8. 8.

Grabovsky, Y. & Tallarida, R. J. Isobolographic analysis for combinations of a full and partial agonist: curved isoboles. J. Pharmacol. Exp. Ther. 310, 981–986 (2004).

9. 9.

Wicha, S. G., Kees, M. G., Kuss, J. & Kloft, C. Pharmacodynamic and response surface analysis of linezolid or vancomycin combined with meropenem against Staphylococcus aureus. Pharm. Res. 32, 2410–2418 (2015).

10. 10.

Greco, W. R., Bravo, G. & Parsons, J. C. The search for synergy: a critical review from a response surface perspective. Pharmacol. Rev. 47, 331–85 (1995).

11. 11.

Lee, J. J., Kong, M., Ayers, G. D. & Lotan, R. Interaction index and different methods for determining drug interaction in combination therapy. J. Biopharm. Stat. 17, 461–480 (2007).

12. 12.

Minto, C. F. et al. Response surface model for anesthetic drug interactions. Anesthesiology 92, 1603–1616 (2000).

13. 13.

Twarog, N. R., Stewart, E., Hammill, C. V. & Shelat, A. BRAID: a unifying paradigm for the analysis of combined drug action. Sci. Rep. 6, 25523 (2016).

14. 14.

Jaynes, J., Ding, X., Xu, H., Wong, W. K. & Ho, C. M. Application of fractional factorial designs to study drug combinations. Stat. Med. 32, 307–318 (2013).

15. 15.

Wood, K., Nishida, S., Sontag, E. D. & Cluzel, P. Mechanism-independent method for predicting response to multidrug combinations in bacteria. Proc. Natl Acad. Sci. USA 109, 12254–12259 (2012).

16. 16.

Segrè, D., Deluna, A., Church, G. M. & Kishony, R. Modular epistasis in yeast metabolism. Nat. Genet. 37, 77–83 (2005).

17. 17.

Beppler, C. et al. Uncovering emergent interactions in three-way combinations of stressors. J. R. Soc. Interface 10.1098/rsif.2016.0800 (2016).

18. 18.

Tekin, E. et al. Enhanced identification of synergistic and antagonistic emergent interactions among three or more drugs. J. R. Soc. Interface 13, 18–20 (2016).

19. 19.

Chevereau, G. & Bollenbach, T. Systematic discovery of drug interaction mechanisms. Mol. Syst. Biol. 11, 807–807 (2015).

20. 20.

Loewe, S. The problem of synergism and antagonism of combined drugs. Arzneimittelforschung 3, 285–290 (1953).

21. 21.

Bliss, C. I. The toxicity of poisons applied jointly. Ann. Appl. Biol. 26, 585–615 (1939).

22. 22.

Hafner, M., Niepel, M., Chung, M. & Sorger, P. K. Growth rate inhibition metrics correct for confounders in measuring sensitivity to cancer drugs. Nat. Methods 13, 521–527 (2016).

23. 23.

Cokol, M. et al. Systematic exploration of synergistic drug pairs. Mol. Syst. Biol. 7, 544 (2011).

24. 24.

Greco, W. R., Park, H. S. & Rustum, Y. M. Application of a new approach for the quantitation of drug synergism to the combination of cis-diamminedichloroplatinum and 1-beta-D-arabinofuranosylcytosine. Cancer Res. 50, 5318–27 (1990).

25. 25.

Hill, A. V. The possible effects of the aggregations of the molecules of haemoglobin on its dissociation curves. J. Physiol. 40, 4–7 (1910).

26. 26.

Michaelis, L. & Menten, M. Die kinetik der invertinwirkung. Biochem. Z. 49, 333–369 (1913).

27. 27.

Prueksaritanont, T. et al. Drug–drug interaction studies: regulatory guidance and an industry perspective. AAPS J. 15, 629–645 (2013).

28. 28.

Ariëns, E. J., Van Rossum, J. M. & Simonis, A. M. Affinity, intrinsic activity and drug interactions. Pharmacol. Rev. 9, 218–36 (1957).

29. 29.

Tam, V. H., Schilling, A. N., Poole, K. & Nikolaou, M. Mathematical modelling response of Pseudomonas aeruginosa to meropenem. J. Antimicrob. Chemother. 60, 1302–1309 (2007).

30. 30.

Cokol, M. et al. Large-scale identification and analysis of suppressive drug interactions. Chem. Biol. 21, 541–551 (2014).

31. 31.

Johnson, M. D., Macdougall, C., Ostrosky-zeichner, L., Perfect, J. R. & Rex, J. H. Combination antifungal therapy. Antimicrob. Agents Chemother. 48, 693–715 (2004).

32. 32.

Nguyen, C., Zhou, A., Khan, A., Miller, J. H. & Yeh, P. Pairwise antibiotic interactions in Escherichia coli: triclosan, rifampicin and aztreonam with nine other classes of antibiotics. J. Antibiot. (Tokyo) 69, 791–797 (2016).

33. 33.

Yeh, P., Tschumi, A. I. & Kishony, R. Functional classification of drugs by properties of their pairwise interactions. Nat. Genet. 38, 489–94 (2006).

34. 34.

Zimmer, A., Katzir, I., Dekel, E., Mayo, A. E. & Alon, U. Prediction of multidimensional drug dose responses based on measurements of drug pairs. Proc. Natl Acad. Sci. USA 2016, 06301 (2016).

35. 35.

Beppler, C. et al. When more is less: emergent suppressive interactions in three-drug combinations. BMC Microbiol. 17, 107 (2017).

36. 36.

Clewe, O., Wicha, S. G., de Vogel, C., de Steenwinkel, J. E. M. & Simonsson, U. S. H. A model-informed pre-clinical approach for prediction of clinical pharmacodynamic interactions of anti-TB drug combinations. J. Antimicrob. Chemother. 10.1093/jac/dkx380 (2017).

37. 37.

Chen, C. et al. Assessing pharmacodynamic interactions in mice using the multistate tuberculosis pharmacometric and general pharmacodynamic interaction models. CPT Pharmacomet. Syst. Pharmacol. Preprint at https://www.ncbi.nlm.nih.gov/pubmed/28657202 (2017).

38. 38.

Nielsen, E. I. & Friberg, L. E. Pharmacokinetic-pharmacodynamic modeling of antibacterial drugs. Pharmacol. Rev. 65, 1053–90 (2013).

39. 39.

Mouton, J. W., Dudley, M. N., Cars, O., Derendorf, H. & Drusano, G. L. Standardization of pharmacokinetic/pharmacodynamic (PK/PD) terminology for anti-infective drugs: an update. J. Antimicrob. Chemother. 55, 601–7 (2005).

40. 40.

Jusko, W. J. Pharmacodynamics of chemotherapeutic effects: dose-time-response relationships for phase-nonspecific agents. J. Pharm. Sci. 60, 892–895 (1971).

41. 41.

Soetaert, K., Petzoldt, T. & Setzer, R. W. Solving differential equations in R. R J. 2, 5–15 (2010).

42. 42.

Soetaert, K., Petzoldt, T. & Setzer, R. W. R package deSolve, writing code in compiled languages. CRAN https://cran.r-project.org/web/packages/deSolve/vignettes/compiledCode.pdf. (2009)

43. 43.

Galassi, M. GNU Scientific Library Reference Manual. (GNU, 2016)

44. 44.

Cardi, G. & Nepusz, T. The igraph software package for complex network research. Int. J. Complex Syst. 1695, 1–9 (2006).

## Acknowledgements

The authors would like to acknowledge our colleagues Dr Elin Svensson and Dr Anders Kristofferson at the Dept. of Pharmaceutical Biosciences for helpful discussions on combination therapies and Rikard Nordgren for technical support. The research leading to these results has received funding from the Swedish Research Council (grant number 521-2011-3442) and the Innovative Medicines Initiative Joint Undertaking (www.imi.europe.eu) under grant agreement no. 115337, resources of which are composed of financial contribution from the European Union’s Seventh Framework Programme (FP7/2007–2013) and EFPIA companies’ in kind contribution.

## Author information

Authors

### Contributions

S.G.W. developed the GPDI approach and conducted the analysis. C.C., O.C. and U.S.H.S. contributed to the development of the GPDI approach and the analysis. All authors wrote and approved the manuscript.

### Corresponding author

Correspondence to Sebastian G. Wicha.

## Ethics declarations

### Competing interests

The authors declare no competing financial interests.

Publisher's note: Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

## Rights and permissions

Reprints and Permissions

Wicha, S.G., Chen, C., Clewe, O. et al. A general pharmacodynamic interaction model identifies perpetrators and victims in drug interactions. Nat Commun 8, 2129 (2017). https://doi.org/10.1038/s41467-017-01929-y

• Accepted:

• Published:

• ### Development of New Tuberculosis Drugs: Translation to Regimen Composition for Drug-Sensitive and Multidrug-Resistant Tuberculosis

• Jacqueline P. Ernest
• , Natasha Strydom
• , Qianwen Wang
• , Nan Zhang
• , Eric Nuermberger
• , Véronique Dartois
•  & Rada M. Savic

Annual Review of Pharmacology and Toxicology (2021)

• ### A Model-Based Pharmacokinetic/Pharmacodynamic Analysis of the Combination of Amoxicillin and Monophosphoryl Lipid A Against S. pneumoniae in Mice

• Sebastian Franck
• , Robin Michelet
• , Fiordiligie Casilag
• , Jean-Claude Sirard
• , Sebastian G. Wicha
•  & Charlotte Kloft

Pharmaceutics (2021)

• ### Constitutive Cell Proliferation Regulating Inhibitor of Protein Phosphatase 2A (CIP2A) Mediates Drug Resistance to Erlotinib in an EGFR Activating Mutated NSCLC Cell Line

• Hisham Saafan
• , Ahmad Alahdab
• , Robin Michelet
• , Linus Gohlke
• , Janine Ziemann
• , Stefan Holdenrieder
• , Katie-May McLaughlin
• , Mark N. Wass
• , Jindrich Cinatl
• , Martin Michaelis
• , Charlotte Kloft
•  & Christoph A Ritter

Cells (2021)

• ### Combination of polymyxin B and minocycline against multidrug-resistant Klebsiella pneumoniae: interaction quantified by pharmacokinetic/pharmacodynamic modelling from in vitro data

• Chenyan Zhao
• , Pikkei Wistrand-Yuen
• , Pernilla Lagerbäck
• , Thomas Tängdén
• , Elisabet I. Nielsen
•  & Lena E. Friberg

International Journal of Antimicrobial Agents (2020)

• ### A model-based analysis identifies differences in phenotypic resistance between in vitro and in vivo: implications for translational medicine within tuberculosis

• Oskar Clewe
• , Alan Faraj
• , Yanmin Hu
• , Anthony R. M. Coates
•  & Ulrika S. H. Simonsson

Journal of Pharmacokinetics and Pharmacodynamics (2020)


text:
# Problem from the Cormen appendix C 1.13

I am currently working on CLRS 1.13. The idea is to use Stirling's approximation to prove that

$${2n \choose n} = \frac{2^{2n}}{\sqrt{\pi n}} \left( 1 + O \left( \frac{1}{n} \right) \right)$$

Now directly replacing Stirling's approximation I arrive to something like:

$${2n \choose n} = \frac{2^{2n} \left( 1 + \Theta(\frac{1}{2n}) \right)}{ \sqrt{\pi n} \left(1 + \Theta( \frac{1}{n}) \right)^2 }$$

Now the quotient is a function that ends up being $$O(\frac{1}{n})$$ because we have terms in $$O(\frac{1}{n})$$ and $$O(\frac{1}{2n})$$. The problem is that even if there is a quotient of two functions that are $$O(\frac{1}{n})$$.

I don't know if the result is still $$O(\frac{1}{n})$$. In fact I haven't seen any general rule for the quotient of two big $$O$$ s.

Is there a general rule that I can apply here?

Just simply use the inequality $$1 + \Theta(1/n) \geq 1$$ in the denominator. You will get the required answer.
• @plop $f(n)$ is positive right? so the inequality should be correct for all $f \in \Theta(1/n)$. – Inuyasha Yagami Feb 1 at 16:59
• I was wrong. I was reading $\Theta$ and thinking $O$. For $n$ large, the elements of $\Theta$ do become positive. – plop Feb 1 at 17:02
• @plop I am not aware of the definition of $\Omega$ or $O$ for negative functions. :p – Inuyasha Yagami Feb 1 at 18:09
• @plop However, in Stirling's approximation, the function $f$ is indeed positive. – Inuyasha Yagami Feb 1 at 18:10
• It is the same definitions. They don't make any assumption about the sign of the function. In the case of $\Theta(1/n)$ it follows as a consequence of the definition, since $f\in\Theta(1/n)$ must satisfy $K_1/n\leq f(n)\leq K_2/n$ for some $K_1,K_2>0$ and sufficiently large $n$. – plop Feb 1 at 18:36

format: plain


text:
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Online ISSN : 1745-1337
Print ISSN : 0916-8508
Volume E102.A , Issue 2
Showing 1-25 articles out of 25 articles from the selected issue
Special Section on Mathematical Systems Science and its Applications
• Takafumi KANAZAWA
2019 Volume E102.A Issue 2 Pages 324
Published: February 01, 2019
Released: February 01, 2019
JOURNALS RESTRICTED ACCESS
• Yoshinao ISOBE, Hisabumi HATSUGAI, Akira TANAKA, Yutaka OIWA, Takanori ...
Type: PAPER
2019 Volume E102.A Issue 2 Pages 325-335
Published: February 01, 2019
Released: February 01, 2019
JOURNALS FREE ACCESS

This paper presents a formal approach for generating train timetables in a mesoscopic level that is more concrete than the macroscopic level, where each station is simply expressed in a black-box, and more abstract than the microscopic level, where the infrastructure in each station-area is expressed in detail. The accuracy of generated timetable and the computational effort for the generation is a trade-off. In this paper, we design a formal mesoscopic modeling language by analyzing real railways, for example Tazawako-line as the first step of this work. Then, we define the constraint formulae for generating train timetables with the help of SMT (Satisfiability Module Theories)-Solver, and explain our tool RW-Solver that is an implementation of the constraint formulae. Finally, we demonstrate how RW-Solver with the help of SMT-Solver can be used for generating timetables in a case study of Tazawako-line.

• Shingo YAMAGUCHI
Type: PAPER
2019 Volume E102.A Issue 2 Pages 336-342
Published: February 01, 2019
Released: February 01, 2019
JOURNALS RESTRICTED ACCESS

Workflow nets (WF-nets for short) are a subclass of Petri nets and are used for modeling and analysis of workflows. Soundness is a criterion of logical correctness defined for WF-nets. A WF-net is said to be sound if it satisfies three conditions: (i) option to complete, (ii) proper completion, and (iii) no dead tasks. In this paper, focusing our analysis on acyclic free choice WF-nets, we revealed that (1) Conditions (i) and (ii) of soundness are respectively equivalent to the liveness and the boundedness of its short-circuited net; (2) The decision problem for each condition of soundness is co-NP-complete; and (3) If the short-circuited net has no disjoint paths from a transition to a place (or no disjoint paths from a place to a transition), each condition can be checked in polynomial time.

• Yuichi KAJIYAMA, Naoki HAYASHI, Shigemasa TAKAI
Type: PAPER
2019 Volume E102.A Issue 2 Pages 343-350
Published: February 01, 2019
Released: February 01, 2019
JOURNALS RESTRICTED ACCESS

This paper proposes a consensus-based subgradient method under a common constraint set with switching undirected graphs. In the proposed method, each agent has a state and an auxiliary variable as the estimates of an optimal solution and accumulated information of past gradients of neighbor agents. We show that the states of all agents asymptotically converge to one of the optimal solutions of the convex optimization problem. The simulation results show that the proposed consensus-based algorithm with accumulated subgradient information achieves faster convergence than the standard subgradient algorithm.

• Naoki HAYASHI, Masaaki NAGAHARA
Type: PAPER
2019 Volume E102.A Issue 2 Pages 351-358
Published: February 01, 2019
Released: February 01, 2019
JOURNALS RESTRICTED ACCESS

This paper proposes a novel distributed proximal minimization algorithm for constrained optimization problems over fixed strongly connected networks. At each iteration, each agent updates its own state by evaluating a proximal operator of its objective function under a constraint set and compensating the unbalancing due to unidirectional communications. We show that the states of all agents asymptotically converge to one of the optimal solutions. Numerical results are shown to confirm the validity of the proposed method.

• Koichi KOBAYASHI
Type: PAPER
2019 Volume E102.A Issue 2 Pages 359-364
Published: February 01, 2019
Released: February 01, 2019
JOURNALS RESTRICTED ACCESS

In this paper, based on the policy of model predictive control, a new method of predictive pinning control is proposed for the consensus problem of multi-agent systems. Pinning control is a method that the external control input is added to some agents (pinning nodes), e.g., leaders. By the external control input, consensus to a certain target value (not the average of the initial states) and faster consensus are achieved. In the proposed method, the external control input is calculated by the controller node connected to only pinning nodes. Since the states of all agents are required in calculation of the external control input, communication delays must be considered. The proposed algorithm includes not only calculation of the external control input but also delay compensation. The effectiveness of the proposed method is presented by a numerical example.

• Takafumi GOTO, Koki TANAKA, Mitsuru NAKATA, Qi-Wei GE
Type: PAPER
2019 Volume E102.A Issue 2 Pages 365-371
Published: February 01, 2019
Released: February 01, 2019
JOURNALS RESTRICTED ACCESS

An automorphism of a graph G=(V, E) is such a one-to-one correspondence from vertex set V to itself that all the adjacencies of the vertices are maintained. Given a subset S of V whose one-to-one correspondence is decided, if the vertices of V-S possess unique correspondence in all the automorphisms that satisfy the decided correspondence for S, S is called determiner set of G. Further, S is called minimal determiner set if no proper subset of S is a determiner set and called kernel set if determiner set S with the smallest number of elements. Moreover, a problem to judge whether or not S is a determiner set is called determiner set decision problem. The purpose of this research is to deal with determiner set decision problem. In this paper, we firstly give the definitions and properties related to determiner sets and then propose an algorithm JDS that judges whether a given S is a determiner set of G in polynomial computation time. Finally, we evaluate the proposed algorithm JDS by applying it to possibly find minimal determiner sets for 100 randomly generated graphs. As the result, all the obtained determiner sets are minimal, which implies JDS is a reasonably effective algorithm for the judgement of determiner sets.

• Koichi KOBAYASHI, Mifuyu KIDO, Yuh YAMASHITA
Type: PAPER
2019 Volume E102.A Issue 2 Pages 372-378
Published: February 01, 2019
Released: February 01, 2019
JOURNALS RESTRICTED ACCESS

In this paper, a surveillance system by multiple agents, which is called a multi-agent surveillance system, is studied. A surveillance area is given by an undirected connected graph. Then, the optimal control problem for multi-agent surveillance systems (the optimal surveillance problem) is to find trajectories of multiple agents that travel each node as evenly as possible. In our previous work, this problem is reduced to a mixed integer linear programming problem. However, the computation time for solving it exponentially grows with the number of agents. To overcome this technical issue, a new model predictive control method for multi-agent surveillance systems is proposed. First, a procedure of individual optimization, which is a kind of approximate solution methods, is proposed. Next, a method to improve the control performance is proposed. In addition, an event-triggering condition is also proposed. The effectiveness of the proposed method is presented by a numerical example.

• Satoshi TAOKA, Toshimasa WATANABE
Type: PAPER
2019 Volume E102.A Issue 2 Pages 379-388
Published: February 01, 2019
Released: February 01, 2019
JOURNALS RESTRICTED ACCESS

The k-edge-connectivity augmentation problem for a specified set of vertices (kECA-SV for short) is defined by “Given a graph G=(V, E) and a subset Γ ⊆ V, find a minimum set E' of edges such that G'=(V, EE') has at least k edge-disjoint paths between any pair of vertices in Γ.” Let σ be the edge-connectivity of Γ (that is, G has at least σ edge-disjoint paths between any pair of vertices in Γ). We propose an algorithm for (σ+1)ECA-SV which is done in O(|Γ|) maximum flow operations. Then the time complexity is O(σ2|Γ||V|+|E|) if a given graph is sparse, or O(|Γ||V||BG|log(|V|2/|BG|)+|E|) if dense, where |BG| is the number of pairs of adjacent vertices in G. Also mentioned is an O(|V||E|+|V|2 log |V|) time algorithm for a special case where σ is equal to the edge-connectivity of G and an O(|V|+|E|) time one for σ ≤ 2.

• Morikazu NAKAMURA, Takeshi TENGAN, Takeo YOSHIDA
Type: PAPER
2019 Volume E102.A Issue 2 Pages 389-398
Published: February 01, 2019
Released: February 01, 2019
JOURNALS RESTRICTED ACCESS

This paper proposes a Petri net based mathematical programming approach to combinatorial optimization, in which we generate integer linear programming problems from Petri net models instead of the direct mathematical formulation. We treat two types of combinatorial optimization problems, ordinary problems and time-dependent problems. Firstly, we present autonomous Petri net modeling for ordinary optimization problems, where we obtain fundamental constraints derived from Petri net properties and additional problem-specific ones. Secondly, we propose a colored timed Petri net modeling approach to time-dependent problems, where we generate variables and constraints for time management and for resolving conflicts. Our Petri net approach can drastically reduce the difficulty of the mathematical formulation in a sense that (1) the Petri net modeling does not require deep knowledge of mathematical programming and technique of integer linear model formulations, (2) our automatic formulation allows us to generate large size of integer linear programming problems, and (3) the Petri net modeling approach is flexible for input parameter changes of the original problem.

• Jinglun LI, Shigemasa TAKAI
Type: LETTER
2019 Volume E102.A Issue 2 Pages 399-403
Published: February 01, 2019
Released: February 01, 2019
JOURNALS RESTRICTED ACCESS

We consider a similarity control problem for discrete event systems modeled as nondeterministic automata. A nonblocking supervisor was synthesized in the previous work under the assumption that the event occurrence and the current state of the plant are observable. In this letter, we prove that the synthesized supervisor is a maximally permissive nonblocking one.

Regular Section
• Zhe LI, Yili XIA, Qian WANG, Wenjiang PEI, Jinguang HAO
Type: PAPER
Subject area: Digital Signal Processing
2019 Volume E102.A Issue 2 Pages 404-414
Published: February 01, 2019
Released: February 01, 2019
JOURNALS RESTRICTED ACCESS

A novel time-series relationship among four consecutive real-valued single-tone sinusoid samples is proposed based on their linear prediction property. In order to achieve unbiased frequency estimates for a real sinusoid in white noise, based on the proposed four-point time-series relationship, a constrained least squares cost function is minimized based on the unit-norm principle. Closed-form expressions for the variance and the asymptotic expression for the variance of the proposed frequency estimator are derived, facilitating a theoretical performance comparison with the existing three-point counterpart, called as the reformed Pisarenko harmonic decomposer (RPHD). The region of performance advantage of the proposed four-point based constrained least squares frequency estimator over the RPHD is also discussed. Computer simulations are conducted to support our theoretical development and to compare the proposed estimator performance with the RPHD as well as the Cramer-Rao lower bound (CRLB).

• Shigeru NINAGAWA
Type: PAPER
Subject area: Nonlinear Problems
2019 Volume E102.A Issue 2 Pages 415-422
Published: February 01, 2019
Released: February 01, 2019
JOURNALS RESTRICTED ACCESS

The Game of Life, a two-dimensional computationally universal cellular automaton, is known to exhibits 1/f noise in the evolutions starting from random configurations. In this paper we perform the spectral analysis on the computation process by a Turing machine constructed on the array of the Game of Life. As a result, the power spectrum averaged over the whole array has almost flat line at low frequencies and a lot of sharp peaks at high frequencies although some regions in which complicated behavior such as frequent memory rewriting occurs exhibit 1/f noise. This singular power spectrum is, however, easily turned into 1/f by slightly deforming the initial configuration of the Turing machine. These results emphasize the peculiarity of the computation process on the Game of Life that is never shared with the evolutions from random configurations. The Lyapunov exponents have positive values in three out of six trials and zero or negative values in other three trails. That means the computation process is essentially chaotic but it has capable of recovering a slight error in the configuration of the Turing machine.

• Xuehou TAN, Bo JIANG
Type: PAPER
Subject area: Algorithms and Data Structures
2019 Volume E102.A Issue 2 Pages 423-429
Published: February 01, 2019
Released: February 01, 2019
JOURNALS RESTRICTED ACCESS

Two points x, y inside a simple polygon P are said to be mutually link-2 visible if there exists the third point zP such that z is visible from both x and y. The polygon P is link-2 LR-visible if there are two points s, t on the boundary of P such that every point on the clockwise boundary of P from s to t is link-2 visible from some point of the other boundary of P from t to s and vice versa. We give a characterization of link-2 LR-visibility polygons by generalizing the known result on LR-visibility polygons. A new idea is to extend the concepts of ray-shootings and components to those under notion of link-2 visibility. Then, we develop an O(n log n) time algorithm to determine whether a given polygon is link-2 LR-visible. Using the characterization of link-2 LR-visibility polygons, we further present an O(n log n) time algorithm for determining whether a polygonal region is searchable by a k-searcher, k ≥ 2. This improves upon the previous O(n2) time bound [9]. A polygonal region P is said to be searchable by a searcher if the searcher can detect (or see) an unpredictable intruder inside the region, no matter how fast the intruder moves. A k-searcher holds k flashlights and can see only along the rays of the flashlights emanating from his position.

• Song BIAN, Masayuki HIROMOTO, Takashi SATO
Type: PAPER
Subject area: Cryptography and Information Security
2019 Volume E102.A Issue 2 Pages 430-439
Published: February 01, 2019
Released: February 01, 2019
JOURNALS RESTRICTED ACCESS

In this work, we provide the first practical secure email filtering scheme based on homomorphic encryption. Specifically, we construct a secure naïve Bayesian filter (SNBF) using the Paillier scheme, a partially homomorphic encryption (PHE) scheme. We first show that SNBF can be implemented with only the additive homomorphism, thus eliminating the need to employ expensive fully homomorphic schemes. In addition, the design space for specialized hardware architecture realizing SNBF is explored. We utilize a recursive Karatsuba Montgomery structure to accelerate the homomorphic operations, where multiplication of 2048-bit integers are carried out. Through the experiment, both software and hardware versions of the SNBF are implemented. On software, 104-105x runtime and 103x storage reduction are achieved by SNBF, when compared to existing fully homomorphic approaches. By instantiating the designed hardware for SNBF, a further 33x runtime and 1919x power reduction are achieved. The proposed hardware implementation classifies an average-length email in under 0.5s, which is much more practical than existing solutions.

• Takahiro OTA, Hiroyoshi MORITA, Akiko MANADA
Type: PAPER
Subject area: Information Theory
2019 Volume E102.A Issue 2 Pages 440-449
Published: February 01, 2019
Released: February 01, 2019
JOURNALS FREE ACCESS

The technique of lossless compression via substring enumeration (CSE) is a kind of enumerative code and uses a probabilistic model built from the circular string of an input source for encoding a one-dimensional (1D) source. CSE is applicable to two-dimensional (2D) sources, such as images, by dealing with a line of pixels of a 2D source as a symbol of an extended alphabet. At the initial step of CSE encoding process, we need to output the number of occurrences of all symbols of the extended alphabet, so that the time complexity increases exponentially when the size of source becomes large. To reduce computational time, we can rearrange pixels of a 2D source into a 1D source string along a space-filling curve like a Hilbert curve. However, information on adjacent cells in a 2D source may be lost in the conversion. To reduce the time complexity and compress a 2D source without converting to a 1D source, we propose a new CSE which can encode a 2D source in a block-by-block fashion instead of in a line-by-line fashion. The proposed algorithm uses the flat torus of an input 2D source as a probabilistic model instead of the circular string of the source. Moreover, we prove the asymptotic optimality of the proposed algorithm for 2D general sources.

• Yongbo XIA, Shiyuan HE, Shaoping CHEN
Type: PAPER
Subject area: Information Theory
2019 Volume E102.A Issue 2 Pages 450-457
Published: February 01, 2019
Released: February 01, 2019
JOURNALS RESTRICTED ACCESS

Let d=2pm-1 be the Niho decimation over $\mathbb{F}_{p^{2m}}$ satisfying $\gcd(d,p^{2m}-1)=3$, where m is an odd positive integer and p is a prime with p ≡ 2(mod 3). The cross-correlation function between the p-ary m-sequence of period p2m-1 and its every d-decimation sequence with short period $\frac{p^{2m}-1}{3}$ is investigated. It is proved that for each d-decimation sequence, the cross-correlation function takes four values and the corresponding correlation distribution is completely determined. This extends the results of Niho and Helleseth for the case gcd(d, p2m-1)=1.

• Shinichi MOGAMI, Yoshiki MITSUI, Norihiro TAKAMUNE, Daichi KITAMURA, H ...
Type: LETTER
Subject area: Engineering Acoustics
2019 Volume E102.A Issue 2 Pages 458-463
Published: February 01, 2019
Released: February 01, 2019
JOURNALS FREE ACCESS

In this letter, we propose a new blind source separation method, independent low-rank matrix analysis based on generalized Kullback-Leibler divergence. This method assumes a time-frequency-varying complex Poisson distribution as the source generative model, which yields convex optimization in the spectrogram estimation. The experimental evaluation confirms the proposed method's efficacy.

• Qichun WANG, Yanjun LI
Type: LETTER
Subject area: Cryptography and Information Security
2019 Volume E102.A Issue 2 Pages 464-466
Published: February 01, 2019
Released: February 01, 2019
JOURNALS RESTRICTED ACCESS

It is known that correlation-immune (CI) Boolean functions used in the framework of side channel attacks need to have low Hamming weights. In this letter, we determine all unknown values of the minimum Hamming weights of d-CI Boolean functions in n variables, for d ≤ 5 and n ≤ 13.

• Xiuping PENG, Hongbin LIN, Yanmin LIU, Xiaoyu CHEN, Xiaoxia NIU, Yubo ...
Type: LETTER
Subject area: Coding Theory
2019 Volume E102.A Issue 2 Pages 467-470
Published: February 01, 2019
Released: February 01, 2019
JOURNALS RESTRICTED ACCESS

Two new families of balanced almost binary sequences with a single zero element of period L=2q are presented in this letter, where q=4d+1 is an odd prime number. These sequences have optimal autocorrelation value or optimal autocorrelation magnitude. Our constructions are based on cyclotomy and Chinese Remainder Theorem.

• Xiaoyu CHEN, Heru SU, Yubo LI, Xiuping PENG
Type: LETTER
Subject area: Coding Theory
2019 Volume E102.A Issue 2 Pages 471-475
Published: February 01, 2019
Released: February 01, 2019
JOURNALS RESTRICTED ACCESS

In this letter, a construction of asymmetric Gaussian integer zero correlation zone (ZCZ) sequence sets is presented based on interleaving and filtering. The proposed approach can provide optimal or almost optimal single Gaussian integer ZCZ sequence sets. In addition, arbitrary two sequences from different sets have inter-set zero cross-correlation zone (ZCCZ). The resultant sequence sets can be used in the multi-cell QS-CDMA system to reduce the inter-cell interference and increase the transmission data.

• Nan SHA, Mingxi GUO, Yuanyuan GAO, Lihua CHEN, Kui XU
Type: LETTER
Subject area: Communication Theory and Signals
2019 Volume E102.A Issue 2 Pages 476-479
Published: February 01, 2019
Released: February 01, 2019
JOURNALS RESTRICTED ACCESS

In this letter, a physical-layer network coding (PNC) scheme based on continuous phase modulation (CPM) signal using the titled-phase model, i.e., TIP-CPM-PNC, is presented, and the combined titled-phase state trellis for the superimposed CPM signal in TIP-CPM-PNC is discussed. Simulation results show that the proposed scheme with low decoding complexity can achieve the same error performance as CPM-PNC using the traditional-phase model.

• Zheng FANG, Tieyong CAO, Jibin YANG, Meng SUN
Type: LETTER
Subject area: Image
2019 Volume E102.A Issue 2 Pages 480-485
Published: February 01, 2019
Released: February 01, 2019
JOURNALS RESTRICTED ACCESS

Saliency detection is widely used in many vision tasks like image retrieval, compression and person re-identification. The deep-learning methods have got great results but most of them focused more on the performance ignored the efficiency of models, which were hard to transplant into other applications. So how to design a efficient model has became the main problem. In this letter, we propose parallel feature network, a saliency model which is built on convolution neural network (CNN) by a parallel method. Parallel dilation blocks are first used to extract features from different layers of CNN, then a parallel upsampling structure is adopted to upsample feature maps. Finally saliency maps are obtained by fusing summations and concatenations of feature maps. Our final model built on VGG-16 is much smaller and faster than existing saliency models and also achieves state-of-the-art performance.

• An-shui YU, Kenji HARA, Kohei INOUE, Kiichi URAHAMA
Type: LETTER
Subject area: Image
2019 Volume E102.A Issue 2 Pages 486-489
Published: February 01, 2019
Released: February 01, 2019
JOURNALS RESTRICTED ACCESS

In this paper, we propose a method for enhancing the visibility of omnidirectional spherical images by enlarging the foreground and compressing the background without provoking a sense of visual incompatibility by using a simplified spring model.


text:
95-168 Eyink, G. L., Lebowitz, J. L., Spohn, H.
Hydrodynamics and Fluctuations Outside of Local Equilibrium: Driven Diffusive Systems (224K, LaTex) Mar 28, 95
Abstract , Paper (src), View paper (auto. generated ps), Index of related papers

Abstract. We derive hydrodynamic equations for systems not in local thermodynamic equilibrium, that is, where the local stationary measures are non-Gibbsian'' and do not satisfy detailed balance with respect to the microscopic dynamics. As a main example we consider the {\em driven diffusive systems}(DDS), such as electrical conductors in an applied field with diffusion of charge carriers. In such systems, the hydrodynamical description is provided by a nonlinear drift-diffusion equation, which we derive by a microscopic method of {\em nonequilibrium distributions}. The formal derivation yields a Green-Kubo formula for the bulk diffusion matrix and microscopic prescriptions for the drift velocity and nonequilibrium entropy'' as functions of charge density. Properties of the hydrodynamical equations are established, including an H-theorem'' on increase of the thermodynamic potential, or entropy,'' describing approach to the homogeneous steady-state. The results are shown to be consistent with the derivation of the linearized hydrodynamics for DDS by the Kadanoff-Martin correlation-function method and with rigorous results for particular models. We discuss also the internal noise in such systems, which we show to be governed by a generalized {\em fluctuation-dissipation relation}(FDR), whose validity is not restricted to thermal equilibrium or to time-reversible systems. In the case of DDS, the FDR yields a version of a relation proposed some time ago by Price between the covariance matrix of electrical current noise and the bulk diffusion matrix of charge density. Our derivation of the hydrodynamical laws is in a form---the so-called Onsager force-flux form'' ---which allows us to exploit the FDR to construct the Langevin description of the fluctuations. In particular, we show that the probability of large fluctuations in the hydrodynamical histories is governed by a version of the Onsager principle of least dissipation,'' which estimates the probability of fluctuations in terms of the Ohmic dissipation required to produce them and provides a variational characterization of the most probable behavior as that associated to least (excess) dissipation. Finally, we consider the relation of long-range spatial correlations in the steady-state of the DDS and the validity of ordinary hydrodynamical laws. We discuss also briefly the application of the general methods of this paper to other cases, such as reaction-diffusion systems or magnetohydrodynamics of plasmas.

Files: 95-168.src( desc , 95-168.tex )