2448 Nucleic Acids Research, 2008, Vol. 36, No. 7 samples and is normalized to the number of genotype calls available for both samples. In order to deﬁne and rank a list of suitable SNPs, we applied the following procedure: (i) we randomly divided 1 X DðCL1,CL2Þ ¼ vNSNPs i¼1...NSNPs dðcl1i; cl2iÞ; where dðcl1i; cl2iÞ ¼ 1 if cl1i 6¼ cl2i 0 if cl1i ¼ cl2i or cli ¼ NoCall: Given a set of NSNPs individual SNPs, let CL1 and CL2 be the ordered sets of genotype calls of two samples and vNSNPs = Card (T), where T ¼ i : cl1i 6¼ NoCall \cl2i 6¼ NoCallg. For vNSNPs > 0, D is deﬁned as: Every mismatch counts 1, every match counts 0. The distance is normalized over the number of available calls. Due to technical limitations of the genotyping assay, the genotype calls of some SNPs may not be available for one or the other DNA sample, therefore vNSNPs NSNPs. In addition to the distance D and to the number of available calls vNSNPs, the algorithm implementing the genotype distance provides summary information on the type of matches and mismatches. It evaluates: (i) the count of mismatches where the two samples are homozygous for diﬀerent alleles (AA versus BB or vice-versa—like double mutation), (ii) the count of mismatches where one is homozygous and the other is heterozygous (and vice- versa—gain or loss of heterozygosity), (iii) the count of homozygous matches (AA versus AA and BB versus BB) and the count of heterozygous matches (AB versus AB). For each mismatch the algorithm reports the identiﬁer of the sample with largest number of heterozygous calls. The allelic imbalance information (loss of heterozygosity) may be important when handling presumed matched (from the same individual) normal-tumor tissue samples, for exam- ple upstream to sequencing. The algorithm would check the consistency of the match and verify which is the tumor sample and which is the normal sample. For speciﬁc purposes, the implementation of the distance D can be modiﬁed to weight diﬀerent types of mismatch (see Supplementary Material ‘Genotype Distance with error weighting’). SNP panel selection procedure We know that extensive genotype proﬁles of DNA samples can work as a unique identiﬁer of samples. We hypothesized that by using a small number of SNPs we would still be able to accurately distinguish samples, providing researchers with a convenient way to check the identity of their samples during the course of their use in the laboratory. Before applying the computational search of the most suitable SNPs, we ﬁltered the 50 K SNPs represented on the Xba Aﬀymetrix SNP Array, using the following rules: (i) SNPs have assigned rs identiﬁer (Reference SNP records); (ii) SNPs are not located in intronic regions and (iii) SNPs are also represented on the 10 K Aﬀymetrix oligonucleotide array ( 8 K). The second rule allows for eventual application of the test on RNA samples and the third rule ensures that the panel will be useful for ﬁngerprint comparison experiments with samples run on the 10 K array. the cell line dataset into training and testing sets using two-thirds and one-third of the samples, respectively, (ii) on the training set, we evaluated the minor allele frequency, the heterozygosity rate and the call rate for each SNP across all samples; (iii) we then identiﬁed the SNPs satisfying the Hardy Weinberg equilibrium applying elastic boundaries (PAA > 0.22, PBB > 0.22, PAB > 0.44) and having SNP call rates greater than 80%, and (iv) on the test set, we evaluated the heterozygosity rate of the identiﬁed SNPs. We iteratively ran this procedure 1000 times (repeated hold-out approach). The procedure did not predeﬁne the number of SNPs to select; therefore, at each iteration we obtained a variable number of SNPs. We then ranked the SNPs based on the selection rate on the training set and on the mean value of the heterozygosity rates on the test sets, evaluated on the 1000 iterations. The mean number of SNPs identiﬁed at each iteration was 30.15 with a standard deviation of 6.23 (min = 14 and max = 54). The mean value of the heterozygosity on the test set was 0.3636 with a standard deviation of 0.0775 (min = 0.0526 and max = 0.7420). The corresponding distributions are shown in Supplementary Figure 1. The top ranked SNPs represent the best choices. SPIA probabilistic test on cell line genotype distance In order to discern when two cell lines are close enough to be called similar and when they are not, we implemented a double probabilistic test to apply on the genotype distance. The test score depends on the number of matches and on the total number of SNPs evaluated for the two cell lines, given a required conﬁdence. The test output reads: ‘similar’, ‘diﬀerent’ or ‘uncertain’ and relies on the probability of the evaluated distance belonging to the population of real matched pairs or to the population of real non-pairs. If the output test is not clear (depending on the required conﬁdence), the score will be ‘uncertain’ and a second panel of SNPs would need to be investigated. If we assume the SNPs being independent (call at locus i does not depend on call at locus j 6¼ i) and the genotype call probability being the same at each SNP, then the probability of having k matches (successes) out of N SNPs (trials) follows the binomial distribution: Pk ¼ Nk PkQN k ¼ k!ðNN! kÞ! PkQN k, where P and Q are the probability of match and mismatch, respectively, and N is the number of available SNPs (vNSNPs). We can draw the distributions of real matched pair and of real non-pair, by knowing the probability of match at a single SNP for a real matched pair (PM) and for a non-matched pair (Pnon-M). For a given vNSNPs, we can then deﬁne areas corresponding to ‘diﬀerent’, ‘uncertain’ or ‘similar’.