require explicit class labeling and should not assume the use of a specific classifier because classification is not the goal of tagging SNP selection; allow the user to select different numbers of tag SNPs for different amounts of tolerated information loss; have comparable performance with other methods satisfying the three first conditions. Selection algorithms Several algorithms have been proposed for selecting tag SNPs. The first approach was based on the measure of goodness of SNP sets and searched for SNP subsets that are small but attain high value of the defined measure. Examining every SNP subset to find good ones is computationally feasible only for small data sets. Another approach uses principal component analysis (PCA) to find subsets of SNPs capturing majority of the data variance. A sliding windows method is employed to repeatedly apply PCA to short chromosomal regions. This reduces the data produced and also does not require exponential search time. Yet it is not feasible to apply the PCA method to large chromosomal data sets as it is computationally complex. The most commonly used approach, block-based method, exploits the principle of linkage disequilibrium observed within haplotype blocks. Several algorithms have been devised to partition chromosomal regions into haplotype blocks which are based on haplotype diversity, LD, four-gamete test and information complexity and tag SNPs are selected from all SNPs that belong to that block. The main presumption in this algorithm is that the SNPs are biallelic. The main drawback is that the definition of blocks is not always straightforward. Even though there is a list of criteria for forming the haplotype blocks, there is no consensus on the same. Also, local correlations based selection of tag SNPs ignores inter-block correlations. Unlike the block-based approach, a block-free approach does not rely on the block structure. The SNP frequency and recombination rates are known to vary across the genome and some studies have reported LD distances much longer than the reported maximum block sizes. Setting a strict border for the neighborhood is not desired and the block-free approach looks for tag SNPs globally. There are several algorithms to perform this. In one algorithm, the non-tagging SNPs are represented as boolean functions of tag SNPs and set theory techniques are used to reduce search space. Another algorithm searches for subsets of markers that can come from non-consecutive blocks. Due to the marker neighborhood, the search space is reduced. Optimizations With