A parameter-free approach for solving combinatorial optimization problems through biased randomization of efficient heuristics

This paper discusses the use of probabilistic or randomized algorithms for solving combinatorial optimization problems. Our approach employs non-uniform probability distributions to add a biased random behavior to classical heuristics so a large set of alternative good solutions can be quickly obtained in a natural way and without complex conguration processes. This procedure is especially useful in problems where properties such as non-smoothness or non-convexity lead to a highly irregular solution space, for which the traditional optimization methods, both of exact and approximate nature, may fail to reach their full potential. The results obtained are promising enough to suggest that randomizing classical heuristics is a powerful method that can be successfully applied in a variety of cases.

Usefulness of Mendelian randomization in observational epidemiology.

Mendelian randomization refers to the random allocation of alleles at the time of gamete formation. In observational epidemiology, this refers to the use of genetic variants to estimate a causal effect between a modifiable risk factor and an outcome of interest. In this review, we recall the principles of a "Mendelian randomization" approach in observational epidemiology, which is based on the technique of instrumental variables; we provide simulations and an example based on real data to demonstrate its implications; we present the results of a systematic search on original articles having used this approach; and we discuss some limitations of this approach in view of what has been found so far.

Serum uric acid and adiposity: deciphering causality using a bidirectional Mendelian randomization approach.

Although the relationship between serum uric acid (SUA) and adiposity is well established, the direction of the causality is still unclear in the presence of conflicting evidences. We used a bidirectional Mendelian randomization approach to explore the nature and direction of causality between SUA and adiposity in a population-based study of Caucasians aged 35 to 75 years. We used, as instrumental variables, rs6855911 within the SUA gene SLC2A9 in one direction, and combinations of SNPs within the adiposity genes FTO, MC4R and TMEM18 in the other direction. Adiposity markers included weight, body mass index, waist circumference and fat mass. We applied a two-stage least squares regression: a regression of SUA/adiposity markers on our instruments in the first stage and a regression of the response of interest on the fitted values from the first stage regression in the second stage. SUA explained by the SLC2A9 instrument was not associated to fat mass (regression coefficient [95% confidence interval]: 0.05 [-0.10, 0.19] for fat mass) contrasting with the ordinary least square estimate (0.37 [0.34, 0.40]). By contrast, fat mass explained by genetic variants of the FTO, MC4R and TMEM18 genes was positively and significantly associated to SUA (0.31 [0.01, 0.62]), similar to the ordinary least square estimate (0.27 [0.25, 0.29]). Results were similar for the other adiposity markers. Using a bidirectional Mendelian randomization approach in adult Caucasians, our findings suggest that elevated SUA is a consequence rather than a cause of adiposity.

Causal relationship between obesity and vitamin D status: bi-directional Mendelian randomization analysis of multiple cohorts.

BACKGROUND: Obesity is associated with vitamin D deficiency, and both are areas of active public health concern. We explored the causality and direction of the relationship between body mass index (BMI) and 25-hydroxyvitamin D [25(OH)D] using genetic markers as instrumental variables (IVs) in bi-directional Mendelian randomization (MR) analysis. METHODS AND FINDINGS: We used information from 21 adult cohorts (up to 42,024 participants) with 12 BMI-related SNPs (combined in an allelic score) to produce an instrument for BMI and four SNPs associated with 25(OH)D (combined in two allelic scores, separately for genes encoding its synthesis or metabolism) as an instrument for vitamin D. Regression estimates for the IVs (allele scores) were generated within-study and pooled by meta-analysis to generate summary effects. Associations between vitamin D scores and BMI were confirmed in the Genetic Investigation of Anthropometric Traits (GIANT) consortium (n = 123,864). Each 1 kg/m(2) higher BMI was associated with 1.15% lower 25(OH)D (p = 6.52×10⁻²⁷). The BMI allele score was associated both with BMI (p = 6.30×10⁻⁶²) and 25(OH)D (-0.06% [95% CI -0.10 to -0.02], p = 0.004) in the cohorts that underwent meta-analysis. The two vitamin D allele scores were strongly associated with 25(OH)D (p≤8.07×10⁻⁵⁷ for both scores) but not with BMI (synthesis score, p = 0.88; metabolism score, p = 0.08) in the meta-analysis. A 10% higher genetically instrumented BMI was associated with 4.2% lower 25(OH)D concentrations (IV ratio: -4.2 [95% CI -7.1 to -1.3], p = 0.005). No association was seen for genetically instrumented 25(OH)D with BMI, a finding that was confirmed using data from the GIANT consortium (p≥0.57 for both vitamin D scores). CONCLUSIONS: On the basis of a bi-directional genetic approach that limits confounding, our study suggests that a higher BMI leads to lower 25(OH)D, while any effects of lower 25(OH)D increasing BMI are likely to be small. Population level interventions to reduce BMI are expected to decrease the prevalence of vitamin D deficiency.

A Mendelian randomization approach to assess the causal relationship of gamma-glutamyl transferase with blood pressure and insulin

Background: Elevated levels of g-glutamyl transferase (GGT) have been associated with subsequent risk of elevated blood pressure (BP), hypertension and diabetes. However, the causality of these relationships has not been addressed. Mendelian randomization refers to the random allocation of alleles at the time of gamete formation. Such allocation is expected to be independent of any behavioural and environmental factors (known or unknown), allowing the analysis of largely unconfounded risk associations that are not due to reverse causation. Methods: We performed a cross-sectional analysis among 4361 participants to the population based CoLaus study. Associations of sex-specific GGT quartiles with systolic BP, diastolic BP and insulin levels were assessed using multivariable linear regression analyses. The rs2017869 GGT1 variant, which explained 1.6% of the variance in GGT levels, was used as an instrument to perform a Mendelian randomization analysis. Results: Median age of the study population was 53 years. After age and sex adjustment, GGT quartiles were strongly associated with systolic and diastolic BP (all p for linear trend <0.0001). After multivariable adjustment, these relationships were significantly attenuated, but remained significant for systolic (b(95%CI)¼1.30 (0.32;2.03), p¼0.007) and diastolic BP (b (95%CI)¼0.57 (0.02;1.13), p¼0.04). Using Mendelian randomization, we observed no positive association of GGT with either systolic BP (b (95%CI)¼-5.68 (-11.51-0.16), p¼0.06) or diastolic BP (b (95%CI)¼ -2.24 (-5.98;1.49) p¼0.24). The association of GGT with insulin was also attenuated after multivariable adjustment. Nevertheless, a strong linear trend persisted in the fully adjusted model (b (95%CI)¼0.07 (0.04;0.09), p<0.0001). Using Mendelian randomization, we observed a similar positive association of GGT with insulin (b (95%CI)¼0.19 (0.01-0.37), p¼0.04). Conclusion: In this study, we found evidence for a direct causal relationship between GGT and insulin, suggesting that oxidative stress may be causally implicated in the pathogenesis of type 2 diabetes mellitus.

A comparison of three methods of Mendelian randomization when the genetic instrument, the risk factor and the outcome are all binary.

The method of instrumental variable (referred to as Mendelian randomization when the instrument is a genetic variant) has been initially developed to infer on a causal effect of a risk factor on some outcome of interest in a linear model. Adapting this method to nonlinear models, however, is known to be problematic. In this paper, we consider the simple case when the genetic instrument, the risk factor, and the outcome are all binary. We compare via simulations the usual two-stages estimate of a causal odds-ratio and its adjusted version with a recently proposed estimate in the context of a clinical trial with noncompliance. In contrast to the former two, we confirm that the latter is (under some conditions) a valid estimate of a causal odds-ratio defined in the subpopulation of compliers, and we propose its use in the context of Mendelian randomization. By analogy with a clinical trial with noncompliance, compliers are those individuals for whom the presence/absence of the risk factor X is determined by the presence/absence of the genetic variant Z (i.e., for whom we would observe X = Z whatever the alleles randomly received at conception). We also recall and illustrate the huge variability of instrumental variable estimates when the instrument is weak (i.e., with a low percentage of compliers, as is typically the case with genetic instruments for which this proportion is frequently smaller than 10%) where the inter-quartile range of our simulated estimates was up to 18 times higher compared to a conventional (e.g., intention-to-treat) approach. We thus conclude that the need to find stronger instruments is probably as important as the need to develop a methodology allowing to consistently estimate a causal odds-ratio.

Use of a Mendelian randomization approach to assess the causal relation of gamma-Glutamyltransferase with blood pressure and serum insulin levels.

Elevated levels of γ-glutamyltransferase (GGT) have been associated with elevated blood pressure (BP) and diabetes. However, the causality of these relations has not been addressed. The authors performed a cross-sectional analysis (2003-2006) among 4,360 participants from the population-based Cohorte Lausannoise (CoLaus) Study (Lausanne, Switzerland). The rs2017869 variant of the γ-glutamyltransferase 1 (GGT1) gene, which explained 1.6% of the variance in GGT levels, was used as an instrument for Mendelian randomization (MR). Sex-specific GGT quartiles were strongly associated with both systolic and diastolic BP (all P's < 0.0001). After multivariable adjustment, these relations were attenuated but remained significant. Using MR, the authors observed no positive association of GGT with BP (systolic: β -5.68, 95% confidence interval (CI): -11.51, 0.16 (P = 0.06); diastolic: β = -2.24, 95% CI: -5.98, 1.49 (P = 0.24)). The association of GGT with insulin was also attenuated after multivariable adjustment but persisted in the fully adjusted model (β = 0.07, 95% CI: 0.04, 0.09; P < 0.0001). Using MR, the authors also observed a positive association of GGT with insulin (β = 0.19, 95% CI: 0.01, 0.37; P = 0.04). In conclusion, the authors found evidence for a direct causal relation of GGT with fasting insulin but not with BP.

Data-division-specific robustness and power of randomization tests for ABAB designs

This study deals with the statistical properties of a randomization test applied to an ABAB design in cases where the desirable random assignment of the points of change in phase is not possible. In order to obtain information about each possible data division we carried out a conditional Monte Carlo simulation with 100,000 samples for each systematically chosen triplet. Robustness and power are studied under several experimental conditions: different autocorrelation levels and different effect sizes, as well as different phase lengths determined by the points of change. Type I error rates were distorted by the presence of autocorrelation for the majority of data divisions. Satisfactory Type II error rates were obtained only for large treatment effects. The relationship between the lengths of the four phases appeared to be an important factor for the robustness and the power of the randomization test.

Problems of the randomization test for AB designs

N = 1 designs imply repeated registrations of the behaviour of the same experimental unit and the measurements obtained are often few due to time limitations, while they are also likely to be sequentially dependent. The analytical techniques needed to enhance statistical and clinical decision making have to deal with these problems. Different procedures for analysing data from single-case AB designs are discussed, presenting their main features and revising the results reported by previous studies. Randomization tests represent one of the statistical methods that seemed to perform well in terms of controlling false alarm rates. In the experimental part of the study a new simulation approach is used to test the performance of randomization tests and the results suggest that the technique is not always robust against the violation of the independence assumption. Moreover, sensitivity proved to be generally unacceptably low for series lengths equal to 30 and 40. Considering the evidence available, there does not seem to be an optimal technique for single-case data analysis

Randomization tests for ABAB designs: Comparing-data-division-specific and common distributions

Monte Carlo simulations were used to generate data for ABAB designs of different lengths. The points of change in phase are randomly determined before gathering behaviour measurements, which allows the use of a randomization test as an analytic technique. Data simulation and analysis can be based either on data-division-specific or on common distributions. Following one method or another affects the results obtained after the randomization test has been applied. Therefore, the goal of the study was to examine these effects in more detail. The discrepancies in these approaches are obvious when data with zero treatment effect are considered and such approaches have implications for statistical power studies. Data-division-specific distributions provide more detailed information about the performance of the statistical technique.