Plant Genome I Conference
Town & Country Conference Center, San Diego, CA, November, 1992.
PG-I: 93pg1
LOCUS ORDERING USING ISOLATED ANNEALING
Ben Hui Liu and Steve J. Knapp, Department of Crop and Soil
Science Oregon State University, Corvallis, OR 97331
Locus ordering is the most computationally intense phase of
genetic mapping. The computational burden increases
exponentially as the number of linked loci increases. For k
linked loci there are k!/2 testable locus orders. When k is big
it is impossible to evaluate the testable orders even with a
supercomputer. Simulated annealing algorithm (SA), which is an
analogy of thermodynamics, is a technique suitable for
optimization of large scale problems and has been used for
designing complex integrated circuits and for business
management. Here we report a simulation study on SA for locus
ordering using the sum of adjacent recombination frequencies
(SAR) as objective function. Factorial combinations of the
following were simulated for 1000 replications: population size
(n) of 50, 100, and 200; number of loci in a linkage group (k) (
8, 30, and 100); and locus spacing pattern (in cM) of 1,1,
1,...,5,5,5,...,I,5,1,5,...,20,20,20,..., and 5,20,5,20,....
For 8 locus linkage roups, all possible orders were evaluated
directly to find the most probable order (DIRECT) in order to
compare to the order found by SA. The simulation results between
DIRECT and SA were always the same or very close in terms of
percentages of correctly estimated locus orders (PCO) and mean
SARs. For locus spacing patterns 1,1,1,... and 1,5,1,5,... PCOs
were low for all combinations of n and k. For the other locus
spacing patterns, PCOs were generally higher than 90% when n =
100 and 200. We conclude that SA is efficient for locus
ordering. The size of the mapping population should be
sufficiently large in order to resolve locus order for dense
linkage. SA and resampling techniques can be combined to
estimate locus order. Locus ordering using SA was implemented in
GMENDEL, a program we developed for genetic mapping.
Return to Previous Page or Intl-PAG Homepage