Computational Strategies for Configuration Search

Why Configuration Search Becomes a Computational Problem

Fine-mapping compares possible configurations: subsets of candidate variants that are treated as causal under the model. The number of such subsets can grow rapidly, even when the number of variants is only in the hundreds. The computational question is therefore not just how to score a configuration, but how to search the space of configurations without mistaking a convenient subset for the full posterior.

The introductory material on comparing evidence across causal models supplies the basic target: each configuration has a prior probability and a likelihood, and its posterior probability is proportional to their product. Search strategies differ in whether they evaluate every allowed configuration, explore selected configurations by a deterministic rule, or draw configurations probabilistically. These approaches do not automatically give equivalent results.

Definition: Let \(p\) be the number of candidate variants and let \(C\subseteq\{1,\ldots,p\}\) denote a configuration. For observed data \(D\), define its unnormalized posterior weight as \(w(C)=P(D\mid C)P(C)\). Over an allowed configuration space \(\mathcal{C}\), its posterior probability is \(P(C\mid D)=w(C)/\sum_{C'\in\mathcal{C}}w(C')\), provided the denominator is finite and positive. A search is exhaustive if it evaluates every configuration in \(\mathcal{C}\); a restricted search evaluates only a subset.

This definition presumes that the model, likelihood, prior, candidate variants, and allowed configuration space have already been specified. Computational search changes how the posterior is calculated or approximated; it does not repair an inappropriate model or prior. If the model allows at most \(K\) causal variants, its configuration space contains \(\sum_{k=0}^{K}\binom{p}{k}\) configurations. The empty configuration is included when \(k=0\).

Worked Example: Counting Configurations Before Computing

Suppose a hypothetical fine-mapping analysis has \(p=8\) candidate variants and allows at most two causal variants. The number of configurations is

|\mathcal{C}|=\binom{8}{0}+\binom{8}{1}+\binom{8}{2} =1+8+28=37.

Evaluating 37 configurations is modest, so exhaustive calculation is a natural choice if each likelihood evaluation is manageable. By contrast, with \(p=1000\) and \(K=5\), the number is

\sum_{k=0}^{5}\binom{1000}{k} =1+1000+499{,}500+166{,}167{,}000 +41{,}417{,}124{,}750+8{,}250{,}291{,}250{,}200 \approx 8.29\times 10^{12}.

The leading term alone is about 8.25 trillion configurations. Even a very fast per-configuration calculation would not make a straightforward exhaustive search practical at that scale. This count is a first feasibility check, not a runtime guarantee: the cost of scoring each configuration also matters.

Three Ways to Search

Exhaustive enumeration evaluates all configurations in the specified space, sums their weights, and normalizes. If the calculations are exact up to numerical precision, the resulting posterior probabilities and summaries are exact for that model. Its main limitation is the cost of exploring the entire space.

Iterative search begins from one or more configurations and repeatedly changes them according to a rule. For example, a local search might propose adding or removing one variant, or swapping one included variant for one excluded variant. A greedy rule accepts a change only if it improves the objective, such as the log posterior score. Such a procedure can quickly find high-scoring configurations, but a local optimum need not be a global optimum. More importantly, locating a high-scoring configuration is not the same as summing posterior weight over the whole space.

Stochastic search uses random proposals or random draws to explore configurations. If a Markov chain is constructed with the target posterior as its stationary distribution, and it is run long enough with suitable exploration, its draws can be used to estimate posterior quantities. The construction must permit movement throughout the relevant configuration space; a chain trapped in one region will not represent the target posterior. Randomness by itself does not guarantee good exploration.

A further option is branch-and-bound search. It organizes configurations into groups, or branches, and uses bounds on the best possible score or total possible weight within a branch to decide whether that branch can be safely skipped for a stated goal. A valid bound can certify that a branch cannot change a target result beyond a specified tolerance. Without such a bound, pruning is a heuristic restriction, not a proof that discarded configurations are unimportant.

Strategy	What it can provide	Main risk or cost
Exhaustive enumeration	Posterior summaries over the entire specified space	Cost grows with the number and scoring cost of configurations
Iterative optimization	One or more high-scoring configurations	Can stop at a local optimum and does not, by itself, estimate total posterior mass
Stochastic sampling	Monte Carlo estimates of posterior summaries if sampling explores the target distribution	Finite-sample error, autocorrelation, and incomplete exploration
Branch-and-bound	Potentially reduced search with guarantees when valid bounds apply	Useful bounds may be difficult to obtain or too loose to prune much

What a Restricted Search Leaves Out

Suppose a restricted search evaluates a subset \(\mathcal{R}\subseteq\mathcal{C}\). Normalizing weights only within \(\mathcal{R}\) gives a conditional posterior: it describes uncertainty given that the configuration is in \(\mathcal{R}\). It is not automatically the posterior over all allowed configurations. The distinction can be quantified if the total weight over the full space is known or bounded.

Key result: Let \(r=P(C\in\mathcal{R}\mid D)\) be the posterior mass retained by the search. For a variant \(j\), let \(q_j=P(j\in C\mid D,\ C\in\mathcal{R})\) and \(u_j=P(j\in C\mid D,\ C\notin\mathcal{R})\), when the omitted mass is positive. Then \(P(j\in C\mid D)=r q_j+(1-r)u_j\). Consequently, \(\left|P(j\in C\mid D)-q_j\right|\leq 1-r\).

The result follows by dividing configurations into those retained and omitted. The event that variant \(j\) is included has conditional probability \(q_j\) in the retained part and \(u_j\) in the omitted part. The law of total probability therefore gives the mixture expression. Subtracting \(q_j\) yields \((1-r)(u_j-q_j)\). Since both \(u_j\) and \(q_j\) lie between zero and one, their difference has absolute value at most one, proving the bound. The bound can be conservative, but it shows why an unknown or small retained mass undermines confidence in restricted-search posterior summaries.

Worked Example: Normalization Within a Search Can Mislead

Consider a hypothetical space of five variants \(A\) through \(E\), allowing at most two causal variants. Suppose the unnormalized weights are as follows: the empty configuration has weight 1; the singleton configurations \(A,B,C,D,E\) have weights \(4,3,2,1,1\); and the pair configurations \(AB,AC,AD,AE,BC,BD,BE,CD,CE,DE\) have weights \(6,4,2,1,3,1,1,1,1,1\), respectively. All 16 configurations are included, and their weights sum to

$$ 1+(4+3+2+1+1)+(6+4+2+1+3+1+1+1+1+1)=33. $$

Thus the exact posterior inclusion probability for \(A\) is the sum of weights of configurations containing \(A\), divided by 33:

P(A\in C\mid D)=\frac{4+6+4+2+1}{33} =\frac{17}{33}\approx 0.5152.

Now suppose an iterative search evaluates only the empty configuration, \(A\), \(B\), and \(AB\). Their total weight is \(1+4+3+6=14\), so the retained posterior mass is \(r=14/33\approx0.4242\). Normalizing within those four configurations gives a conditional inclusion probability for \(A\) of

q_A=\frac{4+6}{14}=\frac{10}{14}\approx0.7143.

The restricted result is higher than the full-space value by approximately \(0.7143-0.5152=0.1991\). This does not mean that the restricted calculation is arithmetically wrong: it answers a conditional question. The omitted posterior mass is \(1-r=19/33\approx0.5758\), so the general bound allows a difference as large as 0.5758. In this example the exact omitted weights let us recover the full answer; in a genuinely incomplete search, those weights are precisely what may be unknown.

Worked Comparisons and Search Diagnostics

Worked Example: Interpreting Iterative Search Results

Suppose a hypothetical greedy algorithm starts with the empty configuration and repeatedly adds the variant that most improves its score, stopping when no single addition improves that score. It ends at configuration \(AB\), which has the largest score among all one-step additions and removals from \(AB\). What has been established?

The algorithm has found a local optimum under its specified moves: no considered one-step move improves the objective. It has not established that \(AB\) is the global maximum, because a configuration requiring several coordinated changes may have a higher score even if intermediate one-step moves do not. Nor has it estimated the total posterior weight of configurations, because an optimizer compares scores rather than summing the weights of all configurations.

A practical response is to run the search from multiple starting configurations, use more than one move type, and record whether the same high-scoring solutions recur. These checks can reveal dependence on initialization, but agreement across runs is not a proof that no better configuration exists. If the objective is posterior inclusion probabilities rather than merely finding a high-scoring configuration, an optimization result alone is insufficient.

Worked Example: Monte Carlo Error in a Stochastic Search

In a hypothetical analysis, suppose an algorithm produces 100 independent draws from the target posterior over four configurations: empty, \(\{A\}\), \(\{B\}\), and \(\{A,B\}\). Their respective draw counts are 8, 43, 29, and 20. The estimated posterior inclusion probability for \(A\) is the fraction of draws containing it:

\widehat{P}(A\in C\mid D)=\frac{43+20}{100}=0.63.

Treating these independent draws as Bernoulli observations for inclusion of \(A\), the estimated Monte Carlo standard error is

SE\approx\sqrt{\frac{0.63(1-0.63)}{100}} =\sqrt{0.002331}\approx0.0483.

This standard error describes simulation variability in the estimated inclusion probability under the stated independent-draw assumption; it is not a measure of biological uncertainty or a standard error for an effect estimate. If draws come from a correlated Markov chain, this independent-draw calculation is generally too optimistic. One must account for dependence, and assess whether the chain explores different regions rather than repeatedly visiting a narrow part of the configuration space.

Diagnostics should match the search method. For exhaustive enumeration, verify the number of evaluated configurations against the intended space and check that the normalizing sum includes all permitted configurations. For iterative search, compare starts, move sets, stopping rules, and attained scores; report whether the objective was maximized or posterior mass estimated. For stochastic search, inspect trace behavior and mixing across chains or regions, quantify Monte Carlo error with methods appropriate to dependent draws, and check that different initializations produce compatible summaries. None of these checks can establish that a misspecified model is correct.

A common mistake is to say, “The algorithm found the highest-scoring configuration, so it has captured the posterior.” This confuses maximization with integration. A single configuration can have the largest individual weight while many other configurations collectively carry substantial weight. The correction is to state the computational target precisely: a maximum-score configuration, a posterior probability over the full configuration space, or a Monte Carlo estimate of a posterior summary. Then use a search method and diagnostics suited to that target.

Exhaustive enumeration is preferable when the configuration space is small enough and exact posterior summaries are needed. Iterative search is useful for locating strong candidates or initializing other procedures, but should not be presented as a complete posterior calculation unless supplemented by a justified method. Stochastic search can scale to larger spaces and target posterior summaries, but its accuracy depends on exploration and finite simulation. Restricted searches can be useful when computational limits demand them, but their conclusions should be qualified unless omitted mass is bounded or otherwise assessed. The next methodological issue is how to ensure the weights and sums used in these calculations are computed reliably.

Check Your Understanding

Answer each question, then compare your reasoning with the solutions below.

With \(p=10\) variants and at most one causal variant, how many configurations are allowed, including the empty configuration?
A restricted search retains posterior mass \(r=0.90\). What general upper bound does this give on the absolute difference between a full posterior inclusion probability and its conditional value within the retained set?
Why does a greedy algorithm stopping at a configuration with no improving one-step move not prove that the configuration is the global maximum?
A stochastic search produces an estimated inclusion probability of 0.50 from 400 independent posterior draws. Calculate its approximate Monte Carlo standard error using the Bernoulli formula.

Solutions. (1) There is one empty configuration and ten singleton configurations, giving \(\binom{10}{0}+\binom{10}{1}=1+10=11\). (2) The omitted mass is \(1-r=0.10\), so the absolute difference is at most 0.10 by the mixture bound. (3) The stopping rule checks only the moves the algorithm considers from its current configuration. A better configuration might require a sequence of moves whose intermediate steps do not improve the score. (4) The estimated standard error is \(\sqrt{0.50(1-0.50)/400}=\sqrt{0.000625}=0.025\). This calculation relies on independent draws; correlated draws require an adjustment for dependence.