the number of individuals genotyped and number of SNPs in databases growing, tag SNP selection takes too much time to compute. In order to improve the efficiency of the tag SNP selection method, the algorithm first ignores the SNPs being biallelic, and then compresses the length (SNP number) of the haplotype matrix by grouping the SNP sites with the same information. The SNP sites that partition the haplotypes into the same group are called redundant sites. The SNP sites which contain distinct information within a block are called non-redundant sites (NRS). In order to further compress the haplotype matrix, the algorithm needs to find the tag SNPs such that all haplotypes of the matrix can be distinguished. By using the idea of joint partition, an efficient tag SNPs selection algorithm is provided. Validation of the accuracy of the algorithm Depending on how the tag SNPs are selected, different prediction methods have been used during the cross-validation process. Machine learning method was employed to predict the left-out haplotype. Another approach predicted the alleles of a non-tagging SNP n from the tag SNPs that had the highestcorrelation coefficient with n. If a single highly correlated tag SNP t is found, the alleles are assigned so their frequencies agree with the allele frequencies of t. When multiple tagging SNPs have the same (high) correlation coefficient with n, the common allele of n has advantage. It is easy to see that in this case the prediction method agrees well with the selection method, which uses PCA on the matrix of correlation coefficients between SNPs. There are other ways to assess the accuracy of a tag SNP selection method. The accuracy can be evaluated by the quality measure R2, which is the measure of association between the true numbers of haplotype copies defined over the full set of SNPs and the predicted number of haplotype copies where the prediction is based on the subset of tagging SNPs. This measure assumes diploid data and explicit inference of haplotypes from genotypes. Another assessment method due to Clayton is based on a measure of the diversity of haplotypes. The diversity is defined as the total number of differences in all pairwise comparison between haplotypes. The difference between a pair of haplotypes is the sum of differences over all the SNPs. The Clayton's diversity measure can be used to define how well a set of tag SNPs differentiate different