The incremental search algorithm starts with finding a first marker that has maximum locus richness and then goes through
the remaining markers to find the next one that brings the greatest increase in the criterion measure, PDE or . The selected markers are kept and the search process is continued using the remaining ones, one marker being added at a
time, until a convergence criterion is met.
The decremental search operates in an opposite manner from the incremental search. Starting with all markers, one marker that causes the smallest loss in the criterion measure is excluded each time and the rest of the markers
are kept. The exclusion process is continued until the criterion measure falls below a predefined criterion; the last set
with the measure above the criterion is reported.
The iterative maximization search (Gouesnard et al., 2001) is a fast algorithm for choosing an optimal -subset from
accessions. The algorithm starts from a random selection of
markers for which all the core collections of size
are tested. The subset with the highest criterion measure is retained. Among the other
markers, one that brings the greatest increase in the goodness criterion is selected and a new
-locus set is obtained. Exclusion and inclusion of one marker in the new
-locus set are repeated until convergence. Each iteration needs to evaluate the criterion measure
times for
markers and
times for
markers.
Simulation annealing (Kirkpatrick, Gelatt, and Vecchi, 1983) has been adopted in many combinatorial optimization problems. The global optimum could be approximated with simulated annealing
by using a proper annealing schedule. Starting from a selection of markers (the selection could be random or obtained from a previously mentioned algorithm), one marker is randomly swapped
with another from the unselected markers. The change of haplotype goodness is evaluated using an energy function for the marker
exchange. Acceptance of the exchange is judged with the Metropolis criterion (Metropolis et al., 1953), and
where is the change of energy function and
is the annealing temperature.
An exhaustive search of markers from
involves traversal of all
possible selections once and only once. The traversal is implemented in lexicographical order (Nijenhuis and Wilf, 1978). Let
denote a selection
, where
is the index of the
th element in selection
. Lexicographical traversal of all
subsets then starts with
,
, and ends with
.