Informative SNPs Selection Based on Two-Locus and Multilocus Linkage Disequilibrium: Criteria of Max-Correlation and Min-Redundancy

Currently, there are lots of methods to select informative SNPs for haplotype reconstruction. However, there are still some challenges that render them ineffective for large data sets. First, some traditional methods belong to wrappers which are of high computational complexity. Second, some methods ignore linkage disequilibrium that it is hard to interpret selection results. In this study, we innovatively derive optimization criteria by combining two-locus and multilocus LD measure to obtain the criteria of MaxCorrelation and Min-Redundancy (MCMR). Then, we use a greedy algorithm to select the candidate set of informative SNPs constrained by the criteria. Finally, we use backward scheme to refine the candidate subset. We separately use small and middle (>1,000 SNPs) data sets to evaluate MCMR in terms of the reconstruction accuracy, the time complexity, and the compactness. Additionally, to demonstrate that MCMR is practical for large data sets, we design a parameter w to adapt to various platforms and introduce another replacement scheme for larger data sets, which sharply narrow down the computational complexity of evaluating the reconstruct ratio. Then, we first apply our method based on haplotype reconstruction for large size (>5,000 SNPs) data sets. The results confirm that MCMR leads to promising improvement in informative SNPs selection and prediction accuracy.