Combining Functional and Linkage Disequilibrium Information in the Selection of Tag SNPs

 Sham P.C.^1,2,3,*, Ao, S.I.⁴, Kwan J.S.H.², Kao P.², Cheung F.², Fong P.Y.², Ng, M.K.⁵

(1) Department of Psychiatry, University of Hong Kong
(2) Genome Research Centre, University of Hong Kong
(3) SGDP Centre, Institute of Psychiatry, King's College London
(4) Department of Mathematics, University of Hong Kong
(5) Department of Mathematics, Hong Kong Baptist University

A method for tag-SNP selection is described that allows the user to specify variable weights for different genomic regions or SNPs. Tag-SNPs are selected such that a SNP with specified weight C will have a minimum R^2 of C with at least one tag-SNP. This flexible feature is useful for researchers who wish to prioritize genomic regions in an association study, and to optimize study design under budgetary constraints.

• How does the tag SNP selection work
• WCLUSTAG formulation
• Experimental results
• Download the program
• How to use it
• Acknowledgements
• References
• Supplementary information

How does the tag SNP selection work

There are two main approaches to selecting genetic markers in association studies of complex diseases. The first is a direct, functional, or gene-based approach, in which polymorphisms are selected if they cause a change in the amino acid sequence or expression of candidate genes. The second is an indirect approach in which markers in a region or the whole genome are systematically screened, on the basis that they may be in linkage disequilibrium (LD) with disease-related functional variants. For the second approach, efficiency can be improved by recognizing the redundancy between near-by markers through the presence of LD, and the selection of a subset of informative SNPs, called tag SNPs, for analysis (Johnson et al, 2001). A large number of methods for selecting tag-SNPs have been proposed (Halldόrsson et al, 2005).

In this report, we propose a modification of tag SNP selection algorithms that takes account of functional as well as LD information. More importance is attached to some SNPs than others, based on their positions within the coding or regulatory regions or splice sites. We also describe further modifications to address other practical issues: some SNPs may be more readily assayed than others under the proposed genotyping platform, and some SNPs may have been already genotyped in the sample. We have modified our recently described tag-SNP selection method (Ao et al, 2005) to incorporate functional and other information.

Minimax clustering

Our method for tag-SNP selection is based on agglomerative hierarchical clustering, which starts with a square matrix of pair-wise distances between the objects to be clustered. The two clusters with the smallest inter-cluster distance are successively merged until all the objects have been merged into a single cluster. For two SNPs, an appropriate measure of distance is 1-R^2, where R^2 is the squared correlation between the SNPs. Different forms of agglomerative clustering differ in the definition of the distance between two clusters, each of which may contain more than one object. We previously proposed the following definition for inter-cluster distance:
For each SNP belonging to either cluster, find the maximum distance (i.e. 1-R^2) from it to all the other SNPs in the two clusters
The smallest of these maximum distances is defined as the distance between the two clusters.
The corresponding SNP is defined as the tag-SNP of the newly merged cluster

In this method, called minimax clustering, setting a cutoff merging distance of C for terminating the algorithm would ensure that no SNP is further than C away from the tag-SNP in its cluster. This method was implemented in the CLUSTAG program. Also implemented in this program are two other tag SNP selection procedures, a complete linkage clustering method (Byng et al, 2003) and a set-cover algorithm similar to the method described in Carlson et al (2004). Our previous results show that complete linkage clustering results in a greater number of clusters and is therefore less efficient, while the set-cover method is similar to minima clustering in terms of the number of tag SNPs but produces less compact clusters (as measured by the average of the distances,1-R^2 between all SNPs and their assigned tag SNPs).

WCLUSTAG formulation

We have now extended this method to take into account other factors in the selection of tag SNPs. The basic idea is to allow of the cut-off distance C to be variable among markers, as specified by the user to reflect factors concerning the SNP; these might include positional and functional considerations, as well as more practical issues such as assay quality and whether include the SNP has been genotyped previously. For instance, C might be set at a high value (e.g. 0.8) for SNPs within the coding or regulatory regions of genes expressed in a certain tissue, and a low value (e.g. 0.4) for other SNPs. In a sense, more weight is given to some SNPs than others.

One complication of this modification is the asymmetry between two SNPs with different values of C. For example, if one SNP is coding and therefore given a C of 0.8, and the other is non-coding and therefore given a C of 0.4, and the R2 between the two SNPs is 0.6, then the first SNP is able to serve as tag-SNP for the second SNP, but not the reverse. The modification of the algorithm necessary to deal with this complication is simplified by the ability of the clustering program to handle an asymmetric distance matrix, in which the distance from object i to object j can differ from the distance from object j to object i. Because of this, the desired extension can be achieved by the following modifications to the clustering algorithm:
For each marker, a user-defined value of C is provided in an input file
The distance from marker i to marker j is defined as C[j]-R[ij] where C[j] is the value of C specified for marker j. If C[j]-R[ij]<0, then marker i can serve as a tag SNP for marker j.
This asymmetric distance matrix is subjected to the minimax clustering method with the cut-off merging distance set at 0. In order words, a cluster is formed if there is a tag SNP which has distance 0 or less with every member of the cluster.

Other modifications of this algorithm can be used to ensure the inclusion of SNPs that have been genotyped, and the exclusion of those that cannot be assayed. These modifications involve changing the values of the certain elements of the correlation matrix [R[ij]]. Thus, if marker t has been already genotyped, then all elements of column t of the matrix can be set to 0, except the diagonal element which remains 1. This setting ensures that marker t cannot be tagged by any marker except itself, so that it must be included as a tag SNP in the clustering algorithm. Similarly, if marker t is problematic for assay design, then all the elements of row t of the matrix can be set to 0. This setting ensures that marker t can never serve as a tag SNP. As the clustering proceeds, some of these SNPs will be merged into clusters, but others may remain untagged when the algorithm is terminated. At this stage it is necessary to check each of the remaining markers whether they have a potential tag SNP, and to include these in the list of tag SNPs.

And the details of how to handle the cases of some already-genotyped SNPs and some non-desirable SNPs are available here with MS Word format or here with pdf format.

The same principles of weighting can be applied also to the set-cover algorithm �V marker i can serve can tag SNP for marker j  if the condition C[j]-R[ij]<0 is fulfilled. The algorithm would initially select all SNPs that have been already genotyped, and remove the markers tagged by these SNPs. Then the greedy algorithm proceeds as usual, except the exclusion of SNPs that have problems with assay design from the set of possible tag SNPs. As with the clustering algorithm, some "non-designable" SNPs may be left untagged at the end, and these are checked to see if they have potential tag SNPs.

Experimental results

We have made the necessary modifications to implement the weighting in all two tag-SNP selection algorithms in the WCLUSTAG program. To illustrate the performance of the new algorithms, they were applied to the CEPH sample genotype data from the International Haplotype Map Project. The ENCODE regions were selected because genotyping were undertaken for all known SNPs in these regions. Intragenic regions were identified from the start and end points of the coding sequences for the 33K Ensembl genes in NCBI build 34. Intragenic SNPs are given a C weighting of 0.8, and other SNPs 0.4. The compression ratios (the number of tag-SNPs over the total number of SNPs) of the various ENCODE regions are compared with the original procedure which used a uniform C value of 0.8. Our results show that there can be a further 35.2% saving with our weighted minimax algorithm, and 35.9% with the set cover method (Table 1). We also explored the impact of using different weighting schemes. Some additional saving can be obtaining by lowering the weights for either intragenic or other SNPs, although the compression ratios remain in the region of 0.2 (Table 2).

The method and program described here allow the user to prioritize different SNPs and genomic regions in a systematic association screen, depending on prior genomic and disease data available either through public databases or recent experiments. Any weight values below 1 can be specified for any SNP or region, allowing the user to explore different designs under a fixed budget. The utility of the program will be greatly enhanced when detailed SNP maps are available from the International Haplotype Map Project, and progressively more detailed functional information becomes available in public genome databases.

Table 1.  Properties of the tag SNP selection algorithms, weighted with 0.8 for gene regions and 0.4 for other regions.

Table 2.  Effect of weighting scheme (intragenic versus other SNPs) on the comparison ratios for tag-SNP selection algorithms in the Chromosome 9 Encode data.

Table 3. The number of SNPs in the intragenic regions and the other regions. The average ratio of the SNPs in the intragenic regions to the overall SNPs is 32.3%.

Download the program

The program WCLUSTAG is available for free download. . 

*To whom correspondence should be addressed.