MINT: Mutual Information based Transductive Feature Selection for Genetic Trait Prediction

Whole genome prediction of complex phenotypic traits using high-density genotyping arrays has attracted a great deal of attention, as it is relevant to the fields of plant and animal breeding and genetic epidemiology. As the number of genotypes is generally much bigger than the number of samples, predictive models suffer from the curse-of-dimensionality. The curse-of-dimensionality problem not only affects the computational efficiency of a particular genomic selection method, but can also lead to poor performance, mainly due to correlation among markers. In this work we proposed the first transductive feature selection method based on the MRMR (Max-Relevance and Min-Redundancy) criterion which we call MINT. We applied MINT on genetic trait prediction problems and showed that in general MINT is a better feature selection method than the state-of-the-art inductive method mRMR.


Introduction
Whole genome prediction of complex phenotypic traits using high-density genotyping arrays has recently attracted a lot of attention, as it is relevant for the fields of plant and animal breeding and genetic epidemiology. Given a set of biallelic molecular markers, such as SNPs, with genotype values encoded as 0, 1, 2 on a collection of plant, animal or human samples, the goal is to predict the values of certain traits, usually highly polygenic and quantitative, by modeling simultaneously all marker effects, unlike the traditional GWAS. rrBLUP [9,14] has been used widely for trait prediction where it builds a linear model by fitting all the genotypes and the coefficient computed for each marker can be considered as a measure of the importance of the marker. The underlying hypothesis of normal distribution of marker effects is well suited for highly polygenic traits, and as the computations are fast and robust, it is one of the most used models in whole genome prediction. Other popular predictive models are Elastic-Net, Lasso, Ridge Regression [13,2] , Bayes A, Bayes B [9], Bayes Cπ [7], and Bayesian Lasso [8,10], etc.
As the number of genotypes is generally much bigger than the number of samples, the predictive models suffer from the "curse of dimensionality". The "curse of dimensionality" problem not only affects the computational efficiency of the learning algorithms, but can also lead to poor performance, mainly because of the correlation among markers. Feature selection [15,4,6] has been considered as a successful solution for this problem, where a subset of important features are selected and the predictive models are trained only on these features. A popular criterion for feature selection is called Max-Relevance and Min-Redundancy (MRMR) [11] where the selected features are maximally relevant to the class value and simultaneously minimally dependent on each other. The method mRMR [11] has been proposed which greedily selects features that maximize the relevance while minimize the redundancy. mRMR has been applied successfully on various applications [5,1,16].
Transductive learning, first introduced by Vapnik [3], assumes test data for predictor variables (here markers) are available to the learning algorithms (the target variable values for test samples are of course unknown). Therefore the models are built on both the training and test data, and usually lead to better predictive performance on the test data. In this work, we proposed a transductive feature selection method MINT based on information theory. MINT applies the MRMR criterion and integrates the test data in a natural way in the feature selection process. A dynamic programming algorithm is developed to speed up the selection process. Our experiments on both simulated and real data show that MINT generally achieves similar or better results than mRMR does which relies on training data only. To our knowledge, this is the first transductive feature selection method based on the MRMR criterion.

Methods
A popular criterion for feature selection is Max-Relevance and Min-Redundancy (MRMR) [11]. Max-Relevance searches for features satisfying the Equation 1, which measures the mean value of all mutual information values between individual feature x i and class variable c.
where S are the selected features, and I(x i ; c) is the mutual information between x i and c. However, feature selection just based on max-relevance tends to select features that have high redundancy, namely the correlations of the selected features tend to be big. If we remove some of the features that are highly correlated with other features, the respective class-discriminative power would not change much. Therefore, Min-Redundancy is proposed to select mutually exclusive features: An operator Φ(D, R) is defined to combine D and R from the above two equations where D and R are optimized at the same time: In this work, based on the MRMR criterion, we proposed a novel method MINT (Mutual INformation based Transductive feature selection), which targets feature selection with both the training data and the unlabeled test data. We developed a dynamic programming based greedy algorithm to efficiently select features.
We observe that the MRMR criterion has two components, one for maximum relevance and one for minimum redundancy and that the two components are independent. Maximum relevance requires calculation of the mutual information between the selected features and the target variable. As in transductive learning, the target variable values of the test samples are not available, this component remains untouched. Minimum redundancy, on the other hand, calculates the mutual information among all the selected features and the target variable values are not involved. Therefore we can make the method transductive by including all the test samples in this component to help improve the estimation of mutual information.
We applied the same incremental search strategy used in [11] to effectively find the near-optimal features defined by Φ() in equation 3. The incremental algorithm works as the following: Assume feature set S m−1 is already generated and contains m − 1 features. The m-th feature needs to be selected from the set X − S m−1 , which maximizes the following objective function: where x training j denotes the j-th feature vector including only the training data, x training+test j denotes the j-th feature vector including both the training and test data, c training denotes the class value vector including only the training data, I(x i , x j ) is the mutual information between x i and x j . We next propose an efficient greedy algorithm to incrementally select the features based on a dynamic programming strategy. Our motivation is that the operation xi∈Sm−1 I(x j ; x i ) (for simplicity, we ignore the superscripts of "training" and "test") need not be re-conducted for every x j . Since the features are added in an incremental manner, the differences between S m−1 and S m−2 is just the (m − 1)-th feature. Therefore, we do not need to re-compute the sum of the mutual information between x j and x i where 1 ≤ i ≤ m − 2. The two sums xi∈Sm−2 I(x j ; x i ) and xi∈Sm−1 I(x j ; x i ) are just different by I(x j ; x m−1 ). Therefore, we can save this sum xi∈Sm−1 I(x j ; x i ) at every step and reuse them in the next step. The complexity of this dynamic programming algorithm is O(N M ), where N is the number of selected features and M is the number of total features.

Experimental Results
We compare the predictive performance of rrBLUP [9,14] on the full set of variables versus its performance on the subsets of variables of different size selected by mRMR [11] and MINT, referred to as "mRMR + rrBLUP" and "MINT + rrBLUP", respectively. Similar results, not included due to space restrictions, were obtained when applying some other predictive methods to features selected by mRMR and MINT. In all experiments, we perform 10-fold cross-validations and measure the average coefficient of determination r 2 (computed as the square of Pearson's correlation coefficient) between the true and predicted outputs; higher r 2 indicates better performance.
Simulated Data. As our method is based on the MRMR criterion, we experiment with different levels of relevance and redundancy, and show that the performance of MINT relies on both components. We randomly simulate 10 different data sets for each parameter settings, and report average results. First, we simulate a 200-dimensional target variable vector Y following multivariate uniform distribution Y ∼ U (0, 1), and then we simulate the features as F = Y + e, where e ∼ N (0, δ 2 ) is a 200-dimensional noise vector following a multivariate normal distribution. Thus, the large-δ features are noisy ("bad"), while lower-δ features are less noisy ("good"). We simulate 100 "good" features with e ∼ N (0, 100) and 1900 "bad" features with e ′ ∼ N (0, 1000). The results are shown in Table 1, Case one. In this case the feature selection methods work well, but as the good features are randomly simulated and they have low redundancy, the performances of mRMR+rrBLUP and MINT+rrBLUP are almost identical.
Next, we again simulate a target variable vector Y ∼ U (0, 1). For the design matrix X, we simulate 50 "seed" features F = Y + e with e ∼ N (0, 500). Then for each seed feature, we simulate 9 "duplicate" features as F ′ = F + e ′ where e ′ ∼ N (0, 100). We consider all these 500 features as "good" features. We also simulate 4500 "bad" features F ′′ = Y + e ′′ with e ′′ ∼ N (0, 1000). Therefore the good and bad features are still relatively easy to be distinguished and there are large redundancies among the good features. The results are shown in Table 1, Case two. MINT+rrBLUP consistently outperforms mRMR+rrBLUP, due to the redundancy we introduced in the good feature set; both methods outperform rrBLUP. Table 1. Performance (average r 2 over 10-fold CV) of rrBLUP on the full set of features vs. MINT+rrBLUP and mRMR+rrBLUP, on simulated data for two different cases.

Conclusions
In this work, we proposed a transductive feature selection method MINT based on information theory where the test data is integrated in a natural way into a greedy feature selection process. A dynamic programming algorithm is developed to speed up the greedy selection. Our experiments on both simulated and real data show that MINT is generally a better method than the inductive feature selection method mRMR. What's more, MINT is not restricted to genetic trait prediction problems but is a generic feature selection model.