Technical Report 2010-006

Stochastically Guaranteed Global Optimums Achievable with a Divide-and-Conquer Approach to Multidimensional QTL Searches

Carl Nettelblad and Sverker Holmgren

March 2010


The problem of searching for multiple quantitative trait loci (QTL) in an experimental cross population of considerable size poses a significant challenge, if general interactions are to be considered. Different global optimization approaches have been suggested, but without an analysis of the mathematical properties of the objective function, it is hard to devise reasonable criteria for when the optimum found in a search is truly global.

We reformulate the standard residual sum of squares objective function for QTL analysis by a simple transformation, and show that the transformed function will be Lipschitz continuous in an infinite-size population, with a well-defined Lipschitz constant. We discuss the different deviations possible in an experimental finite-size population, suggesting a simple bound for the minimum value found in the vicinity of any point in the model space.

Using this bound, we modify the DIRECT optimization algorithm to exclude regions where the optimum cannot be found according to the bound. This makes the algorithm more attractive than previously realized, since optimality is now in practice guaranteed. The consequences are realized in permutation testing, used to determine the significance of QTL results. DIRECT previously failed in attaining the correct thresholds. In addition, the knowledge of a candidate QTL for which significance is tested allows spectacular increases in permutation test performance, as most searches can be abandoned at an early stage.

Available as PDF (206 kB, no cover)

Download BibTeX entry.