Fast and high precision algorithms for optimization in large-scale genomic problems

There are several very difficult problems related to genetic or genomic analysis that belong to the field of discrete optimization in a set of all possible orders. With n elements (points, markers, clones, sequences, etc.), the number of all possible orders is n!/2 and only one of these is considered to be the true order. A classical formulation of a similar mathematical problem is the well-known traveling salesperson problem model (TSP). Genetic analogues of this problem include: ordering in multilocus genetic mapping, evolutionary tree reconstruction, building physical maps (contig assembling for overlapping clones and radiation hybrid mapping), and others. A novel, fast and reliable hybrid algorithm based on evolution strategy and guided local search discrete optimization was developed for TSP formulation of the multilocus mapping problems. High performance and high precision of the employed algorithm named guided evolution strategy (GES) allows verification of the obtained multilocus orders based on different computing-intensive approaches (e.g., bootstrap or jackknife) for detection and removing unreliable marker loci, hence, stabilizing the resulting paths. The efficiency of the proposed algorithm is demonstrated on standard TSP problems and on simulated data of multilocus genetic maps up to 1000 points per linkage group. (C) 2004 Elsevier Ltd. All rights reserved.