  We present a new computational scheme that enables efficient and reliable
Quantitative Trait Loci (QTL) scans for experimental populations. Using a
standard brute-force exhaustive search effectively prohibits accurate QTL scans
involving more than two loci to be performed in practice, at least if
permutation testing is used to determine significance. Some more elaborate
global optimization approaches, e.g. DIRECT, have earlier been adopted to QTL
search problems. Dramatic speedups have been reported for high-dimensional
scans. However, since a heuristic termination criterion must be used in these
types of algorithms the accuracy of the optimization process cannot be
guaranteed. Indeed, earlier results show that a small bias in the significance
thresholds is sometimes introduced.
  Our new optimization scheme, PruneDIRECT, is based on an analysis leading to
a computable (Lipschitz) bound on the slope of a transformed objective
function. The bound is derived for both infinite size and finite size
populations. Introducing a Lipschitz bound in DIRECT leads to an algorithm
related to classical Lipschitz optimization. Regions in the search space can be
permanently excluded (pruned) during the optimization process. Heuristic
termination criteria can thus be avoided. Hence, PruneDIRECT has a well-defined
error bound and can in practice be guaranteed to be equivalent to a
corresponding exhaustive search. We present simulation results that show that
for simultaneous mapping of three QTL using permutation testing, PruneDIRECT is
typically more than 50 times faster than exhaustive search. The speedup is
higher for stronger QTL. This could be used to quickly detect strong candidate
eQTL networks.
