PaperlayerView exact revision on arXiv

Source-linked AI summary

Gene Hunting with Knockoffs for Hidden Markov Models

Matteo Sesia, Chiara Sabatti, Emmanuel J. Candès

arXiv:1706.04677v1stat.MEmath.STstat.AP

TL;DR

High-dimensional genomic studies need variable-selection methods that handle complex, correlated covariates without imposing restrictive response models while controlling false discoveries. This paper develops exact and efficient HMM knockoff sampling, and its analyses report more discoveries than marginal testing while empirically supporting the approach. The method’s power can nevertheless depend on the chosen feature-importance measure.

  • Problem

    GWAS requires selecting relevant variables amid nonlinearities, interactions, and correlated SNPs, while existing knockoff construction is difficult beyond special covariate distributions.

  • Method

    The paper develops exact, computationally efficient knockoff-copy sampling for covariates modeled by hidden Markov models and combines it with the model-free knockoff framework.

  • Results

    The procedure identifies more potentially significant loci than marginal testing overall, with 2 relevant SNP clusters found on average for height and 22.8 discoveries reported for Crohn’s disease.

  • Takeaways & Limitations

    HMM knockoffs extend model-free variable selection beyond Gaussian designs while accommodating prior knowledge about genetic variation and retaining principled FDR control.

  • Takeaways & Limitations

    Power may be reduced when the true likelihood is far from linear because the paper uses cross-validated logistic-Lasso importance measures.

Abstract

from arXiv · show

Modern scientific studies often require the identification of a subset of relevant explanatory variables, in the attempt to understand an interesting phenomenon. Several statistical methods have been developed to automate this task, but only recently has the framework of model-free knockoffs proposed a general solution that can perform variable selection under rigorous type-I error control, without relying on strong modeling assumptions. In this paper, we extend the methodology of model-free knockoffs to a rich family of problems where the distribution of the covariates can be described by a hidden Markov model (HMM). We develop an exact and efficient algorithm to sample knockoff copies of an HMM. We then argue that combined with the knockoffs selective framework, they provide a natural and powerful tool for performing principled inference in genome-wide association studies with guaranteed FDR control. Finally, we apply our methodology to several datasets aimed at studying the Crohn's disease and several continuous phenotypes, e.g. levels of cholesterol.

1 Introduction

High-dimensional variable selection must balance discovering relevant variables with avoiding spurious findings, especially in GWAS with complex dependencies and millions of correlated genetic variants. The paper extends model-free knockoffs to HMM-distributed covariates, enabling principled selection with rigorous error control while modeling SNP correlations.

  • The need for controlled variable selection: GWAS must select relevant variants from hundreds of thousands to millions of SNPs while balancing discovery power against replicability.The motivation emphasizes targeted follow-up investigation and caution against spurious correlations.
  • The need for controlled variable selection: FWER control can be overly conservative, motivating FDR-based procedures when many true discoveries are expected.The paper notes that FWER-based variants often explain only a small portion of genetic variance and that FDR can improve GWAS power.
  • The need for controlled variable selection: GWAS methods face unknown nonlinear mechanisms, interactions among variants, and correlations among neighboring SNPs.Marginal testing misses interactions, while multivariate approaches may rely on strong linearity assumptions.
  • Model-free knockoffs: Model-free knockoffs provide rigorous FDR control without modeling assumptions on the conditional distribution of the response given covariates.Their framework instead presumes knowledge of the covariate distribution, shifting assumptions away from the response model.
  • Contributions: The paper extends model-free knockoffs beyond Gaussian covariates by introducing an algorithm for HMM-distributed variables.HMMs are widely used for sequential data and biological sequences, making this extension relevant to genomic analyses.
  • Contributions: The HMM knockoff framework models SNP correlations, permits agnostic response modeling, and supports flexible machine-learning importance measures while retaining FDR control.The full procedure is described as computationally efficient, with overall complexity O(np).

2 Model-free controlled variable selection via knockoffs

Model-free knockoffs create artificial covariates that mirror the original covariate structure while remaining null for the response, enabling variable selection with FDR estimation. The paper explains the exchangeability and nullity requirements, feature-importance comparison, and new exact procedures that make knockoff construction practical for Markov and hidden Markov models.

  • Problem formulation: The goal is to estimate which covariates are associated with a response while controlling the false discovery ratio.A variable is null when it is conditionally independent of the response given all other covariates.
  • Knockoff variables: Knockoff copies are artificial covariates with the original variables’ structure that serve as null negative controls for variable selection.They must be constructed without using the response so that the knockoffs remain null.
  • Knockoff variables: Pairwise exchangeability requires the joint distribution of originals and knockoffs to remain invariant when corresponding variables are swapped.This property, together with nullity, supports the knockoff filter’s sign-flip logic.
  • Feature importance measures: Feature-importance statistics compare the predictive importance of each original covariate with its knockoff using methods such as Lasso, boosting, random forests, or neural networks.The original and knockoff variables must be treated fairly under swaps.
  • The knockoff filter: The knockoff filter forms anti-symmetric statistics from original and knockoff importance measures, favoring variables whose originals are more predictive.Null statistics satisfy the flip-sign condition required by the filter.
  • Constructing knockoffs: The SCIP construction is generally impractical because each conditional distribution depends on previously generated knockoffs and may be difficult to compute.The paper addresses this obstacle with exact, computationally efficient procedures for Markov chains and HMMs.

3 Knockoffs for Markov chains

The SCIP algorithm exploits the Markov property to generate knockoff variables sequentially using tractable conditional laws and recursively computed normalization functions. For a discrete chain with state space X, the procedure requires O(p|X|^2) computation time.

  • Algorithm: SCIP generates each knockoff variable sequentially using previously sampled knockoffs, neighboring original variables, and recursively evaluated normalization functions.The procedure starts at X̃1 and proceeds through X̃p, evaluating a normalization function at each stage.
  • Algorithm: The Markov property makes each conditional law p(Xj|X−j, X̃1:(j−1)) tractable in closed form for any number of variables.This simplification enables practical implementation of the SCIP construction.
  • Validity: SCIP applied to a discrete Markov chain generates valid knockoff variables using recursively defined normalization functions.The result is stated formally in Proposition 1 and summarized as Algorithm 2.
  • Computational cost: O(p|X|^2) is the total computation time, with O(|X|^2) required to sample each knockoff variable over a finite state space.The computation is sequential, and each normalization update sums over all possible states.

4 Knockoffs for hidden Markov models

The paper extends knockoff sampling to HMMs by operating through their latent Markov chain, avoiding the exponential cost of conditioning directly on observed variables. Algorithm 3 samples a latent path, generates its knockoff, and emits observed knockoffs with overall complexity O(p(K^2 ∨ |X|)).

  • HMM structure: HMMs combine an unobserved Markov chain with conditionally independent observations generated from state-specific emission distributions.The observed variables do not themselves satisfy the Markov property.
  • Computational challenge: Directly computing the conditional distributions needed by SCIP for observed HMM variables requires summing over all latent-state configurations, causing exponential complexity in p.This makes the naïve approach infeasible for moderately large datasets.
  • Algorithm: Algorithm 3 samples Z from P[Z|X] with forward-backward sampling, generates a knockoff Z̃ using the Markov-chain procedure, then samples X̃ conditionally on Z̃.The final emission step is straightforward because observations are conditionally independent given the latent chain.
  • Computational cost: O(p(K^2 ∨ |X|)) is the overall runtime, combining O(pK^2) latent-path sampling and knockoff generation with O(p|X|) emission sampling.The latent-state computation and Markov-chain knockoff stage each require O(pK^2).
  • Validity: Algorithm 3 produces a knockoff copy of the HMM, so X̃ is a valid knockoff copy of X under the required swap-exchangeability property.Theorem 1 establishes the joint result for (X̃,Z̃) and (X,Z), and the observed-variable guarantee follows as a special case.
  • Latent-path sampling: Forward-backward sampling computes forward probabilities and then samples a complete latent path by a backward pass in O(pK^2) time.This provides an efficient way to sample from the latent conditional distribution given the observations.

5 Hidden Markov models in genome-wide association studies

The section models genotype vectors through two independent HMM haplotypes and derives the resulting genotype HMM for knockoff construction. Its parameters describe haplotype motifs, recombination-related transitions, allele emissions, and can be estimated efficiently from data.

  • Haplotype model: Genotype vectors are modeled as component-wise sums of two unobserved, i.i.d. HMM haplotypes.Each haplotype contains binary alleles, while a latent Markov chain assigns positions to haplotype motifs.
  • Haplotype model: The latent states represent groups of related haplotypes, producing mosaic sequences whose motifs have marker-specific allele frequencies.The model captures local correlation patterns associated with genetic recombination, but is phenomenological rather than a literal mutation-recombination history.
  • HMM parameters: Transition parameters α and r describe motif succession and are intuitively related to genetic recombination rates.The emission parameters θ represent allele-one frequencies within each ancestral haplotype motif.
  • Genotype distribution: Under random mating and Hardy–Weinberg equilibrium, the unphased genotype distribution is obtained by pairing the two haplotypes and summing their alleles marker by marker.The resulting genotype HMM has derived initial-state, transition, and emission probabilities for genotype values 0, 1, and 2.
  • Parameter estimation: HMM parameters can be estimated with standard EM methods in O(npK^2) time, using software such as fastPHASE to obtain knockoff-sampling inputs.The method estimates r, α, and θ from available genotype data because the exact covariate distribution is generally unknown.

6 Numerical Simulations

Simulations evaluate knockoff selection for Markov-chain and HMM covariates under exact and estimated covariate distributions. Across these settings, the reported procedure maintains FDR control and remains robust to fitted parameters and small independent unsupervised samples.

  • Markov-chain simulations: The Markov-chain experiment uses p = 1000 covariates, n = 1000 observations, and 60 nonzero coefficients in a logistic generalized linear model.Knockoffs are first generated from the true model parameters, with signal amplitude varied across experiments.
  • Exact parameters: The procedure empirically controls FDR for all signal amplitudes, while FDP remains concentrated around its mean across 100 replications.Variable importance uses penalized logistic coefficients for each original variable and its knockoff, followed by the knockoff+ threshold.
  • Estimated parameters: Estimating Markov-chain parameters from the same dataset produces results similar to using exact parameters, with FDR still controlled.This experiment suggests robustness to fitting the feature distribution.
  • Unsupervised estimation: Using independent unsupervised samples, empirical FDR stays below the nominal value even when ν ≤ 50, while larger ν gives clear FDR validity.The experiment fixes signal amplitude at a = 10 and varies the size of the unlabeled dataset.
  • HMM simulations: For HMM covariates, the authors test exact parameters, Baum–Welch estimates, and estimates from independent unsupervised data, with FDR consistently controlled.The independent-data experiment reports FDR control even when the unsupervised sample size is as small as 10.
  • Real genetic covariates: In simulations using real genetic covariates, FDR is consistently controlled and FDP is reasonably concentrated, supporting application to GWAS data.The evaluation uses 29,258 SNPs from chromosome one genotyped in 14,708 individuals and repeats the experiment 10 times.

7 Applications to GWAS data

The procedure is applied to NFBC and WTCCC GWAS data after preprocessing, SNP clustering, HMM-based knockoff construction, and knockoff-filter selection. Across phenotypes, it generally identifies more loci than marginal-testing analyses, with some findings supported by meta-analyses.

  • Datasets: The analysis covers NFBC metabolic phenotypes and WTCCC Crohn’s disease data, with dataset-specific sample sizes and SNP counts summarized after clustering.NFBC includes cholesterol, triglyceride, and height phenotypes; WTCCC includes control and Crohn’s disease samples.
  • Preprocessing: SNPs are clustered before selection because high correlations make individual-marker resolution difficult and naïve post hoc aggregation can inflate FDR.The analysis therefore targets representatives of prespecified groups rather than treating every highly correlated SNP as independently distinguishable.
  • Knockoff construction: Knockoffs are generated by estimating HMM parameters with fastPHASE separately across chromosomes, using 12 latent haplotype clusters.The covariate distribution is estimated without using the response, and the same framework is applied to NFBC and WTCCC data.
  • Selection: Variable importance is computed with cross-validated Lasso on the knockoff-augmented covariates, using logistic Lasso for binary Crohn’s disease outcomes.Selections are based on the resulting knockoff statistics and filter.
  • Lipids: 8 HDL and 9.8 LDL discoveries are found on average, compared with 5 and 6, respectively, in the standard analysis.Some additional lipid findings are confirmed by meta-analysis, although the authors avoid exhaustive literature searching to limit selection bias.
  • Other phenotypes: 2.8 triglyceride-associated SNPs are discovered on average, below the 4 variants identified by the standard analysis, while height yields 2 relevant SNP clusters on average.For height, 3 of 4 sites selected at least 10% of the time are validated by meta-analysis.
  • Crohn’s disease: The Crohn’s disease analysis includes comparisons with prior WTCCC, meta-analysis, and knockoff-based results, with several additional findings confirmed in external studies.The cited results include confirmations of rs11627513, rs4263839, and rs7807268 in related analyses.
  • Overall results: Overall, the procedure consistently selects more variables than traditional marginal testing, although statistical power and FDR cannot be computed without ground truth.The authors report that the method is intrinsically random across knockoff realizations and summarize selections over repeated runs.

8 Discussion

The discussion presents exact HMM knockoff generation as an extension of model-free knockoffs and reports empirical support for controlled variable selection. It also identifies unresolved issues involving randomness, grouping, HMM specification, feature importance, and extensions beyond HMMs.

  • Contributions: The paper shows that exact knockoff copies can be efficiently generated for HMMs, extending model-free knockoffs beyond multivariate-normal covariates.Experiments on simulated and real data provide empirical confirmation of the overall approach to controlling relevant-variable selection.
  • Randomness: Repeated knockoff realizations produce reasonably consistent but different selections, and the best way to aggregate them remains unclear.The selection set depends on the realized knockoff variables even after conditioning on the observed data.
  • Group selections: Highly correlated covariates are handled by clustering and selecting representatives, while adapting group-knockoffs is proposed as an alternative.The grouping question concerns whether a response depends on a group rather than on an individual variable.
  • HMM parametrization: Alternative HMM parameterizations and known haplotypes could be incorporated into the covariate model used to generate knockoffs.The discussion points to genotype-imputation models as a source of compatible alternatives.
  • Feature importance measures: Cross-validated logistic Lasso importance measures preserve FDR control without linearity assumptions but may reduce power when the true likelihood is far from linear.The authors suggest exploring nonlinear feature-importance measures.
  • Beyond HMMs: Controlled selection is currently established for HMM and multivariate-normal covariates, leaving extensions to broader graphical models open.The discussion specifically raises models with higher-dimensional structure as a future direction.
  • Conclusion: The authors conclude that the procedure offers finite-sample type-I error control under mild assumptions and advantages over marginal testing in GWAS.They expect these advantages to increase as available dataset sample sizes grow.

Appendices

The appendix proves the SCIP sampling result by induction, showing that each successive knockoff variable has the target conditional distribution. The base case and conditional-independence steps complete the argument.

  • Induction: The proof assumes SCIP samples knockoff variables through index j according to the target joint distribution and establishes the claim for j+1.The induction ranges over j from 1 to p−1.
  • Conditional factorization: The first term in the conditional sampling expression is simplified by retaining only its dependence on the next knockoff variable.This isolates the factors needed to characterize the distribution of ˜Xj+1.
  • Induction step: The induction hypothesis makes the preceding knockoff variables’ contribution constant with respect to ˜Xj+1 because their distributions depend only on local neighboring variables and earlier knockoffs.Consequently, their conditional distribution depends on X1:j rather than the next knockoff value.
  • Independence: The remaining factor is handled using the fact that SCIP samples ˜Xj independently of Xj according to the target conditional rule.This establishes the required expression for the next knockoff variable.
  • Base case: The induction closes for j+1, while the j=1 base case follows directly from the initial sampling rule and the HMM conditional probability relation.The displayed relation expresses the conditional distribution through q1 and Q2.

B Results of data analysis

The appendix reports data-analysis findings for five phenotypes, marking confirmed nearby associations and listing marginal p-values for selected clusters. These p-values are not identical to those in the original studies because preprocessing choices differ.

  • Results of data analysis: Five phenotypes are analyzed with confirmation markers and the smallest standard univariate p-value reported for each selected SNP cluster.An asterisk denotes a confirmed association within 0.5 Mb of a discovered cluster.

B.1 HDL cholesterol

Table 5 reports SNP clusters associated with HDL cholesterol across 100 repetitions, using Human Genome Build 37 positions and marginal p-values from univariate linear regression.

  • Table 5 reports SNP clusters associated with HDL cholesterol.
  • The procedure was repeated 100 times.
  • Positions use Human Genome Build 37, and marginal p-values come from standard univariate linear regression.

B.2 LDL cholesterol

Table 6 reports SNP clusters associated with LDL cholesterol, with other methodological details given in the Table 5 caption.

  • Table 6 reports SNP clusters associated with LDL cholesterol.
  • The table refers to the Table 5 caption for additional details.
  • The reported associations concern SNP clusters rather than individual SNPs.

B.3 Triglycerides

The tables report SNP-cluster associations for triglycerides, height, and Crohn’s disease, with Crohn’s disease analyzed over 100 repetitions using specified genome-build and testing conventions.

  • B.3 Triglycerides: Table 7 reports SNP clusters associated with triglycerides.
  • B.3 Triglycerides: Table 8 reports SNP clusters associated with height.
  • B.3 Triglycerides: Table 9 reports Crohn’s disease-associated SNP clusters over 100 repetitions.
  • B.3 Triglycerides: Crohn’s disease positions follow Human Genome Build 35, and marginal p-values use the Cochran–Armitage test for trend.
Loading 1706.04677v1…