Technical Report 2005-035

Efficient Algorithms for Multi-Dimensional Global Optimization in Genetic Mapping of Complex Traits

Kajsa Ljungberg, Kateryna Mishchenko, and Sverker Holmgren

November 2005

We present a two-phase strategy for optimizing a multi-dimensional, non-convex function arising during genetic mapping of quantitative traits. Such traits are believed to be affected by multiple so called QTL, and searching for d QTL results in a d-dimensional optimization problem with a large number of local optima. We combine the global algorithm DIRECT of Jones et al. with a number of local optimization methods that accelerate the final convergence, and adapt the algorithms to problem-specific features. We also improve the evaluation of the QTL mapping objective function to enable exploitation of the smoothness properties of the optimization landscape. Our best two-phase method is demonstrated to be accurate in at least six dimensions and up to ten times faster than currently used QTL mapping algorithms.

Available as PDF (555 kB, no cover)

Download BibTeX entry.