Search Algorithms :: SAS/Genetics(TM) 13.1 User's Guide

Incremental Search

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 $R_ h^2$ . 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.

Decremental Search

The decremental search operates in an opposite manner from the incremental search. Starting with all $M$ 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.

Iterative Maximization Search

The iterative maximization search (Gouesnard et al., 2001) is a fast algorithm for choosing an optimal $k$ -subset from $M$ accessions. The algorithm starts from a random selection of $k$ markers for which all the core collections of size $k-1$ are tested. The subset with the highest criterion measure is retained. Among the other $M-k$ markers, one that brings the greatest increase in the goodness criterion is selected and a new $k$ -locus set is obtained. Exclusion and inclusion of one marker in the new $k$ -locus set are repeated until convergence. Each iteration needs to evaluate the criterion measure $k$ times for $k-1$ markers and $M-k$ times for $k$ markers.

Simulated Annealing Search

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 $k$ 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

$\text {Pr}\{ \text {new point is accepted}\} = \left\{ \begin{array}{ll} 1, & \Delta \leq 0 \\ \exp (-\Delta /T), & \Delta > 0 \end{array} \right.$

where $\Delta$ is the change of energy function and $T$ is the annealing temperature.

Exhaustive Search

An exhaustive search of $k$ markers from $M$ involves traversal of all ${M \choose k}$ possible selections once and only once. The traversal is implemented in lexicographical order (Nijenhuis and Wilf, 1978). Let $S_ i=( s_1, s_2, \ldots , s_ k)$ denote a selection $i$ , where $1 \le s_{ij} \le M$ is the index of the $j$ th element in selection $i$ . Lexicographical traversal of all $k$ subsets then starts with $(1, 2, \ldots , k-1, k)$ , $(1, 2, \ldots , k-1, k+1)$ , and ends with $(M-k+1, M-k+2,\ldots , M-1, M)$ .

The HTSNP Procedure (Experimental)