SNP variable selection by generalized graph domination.

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• High-throughput sequencing generates vast genetic variant datasets, posing challenges like noise, sparse information (p≫n), overfitting, and multicollinearity.
• Reliable variable selection is crucial for accurate predictive analysis, generalization, clustering robustness, and model interpretability in genetic studies.
• Complex correlation patterns among genetic variables necessitate advanced selection techniques.

Purpose of the Study:

• To introduce and evaluate the k-dominating set model for variable selection in high-throughput sequencing data.
• To demonstrate the efficacy of k-dominating set in identifying independent and representative single nucleotide polymorphism (SNP) variables.
• To showcase the application of this method in biological research, including pedigree reconstruction and species delineation.

Main Methods:

• Modeled single nucleotide polymorphism (SNP) data as a similarity network, representing each SNP as a vertex.
• Defined adjacency based on similarity measures (e.g., correlation, linkage disequilibrium) exceeding a threshold.
• Applied the minimum k-dominating set algorithm to identify a subset of representative SNPs.

Main Results:

• Demonstrated the strength of k-dominating set in selecting independent variables and culling highly correlated ones using a simulated dataset.
• Successfully applied k-dominating set variable selection in pedigree reconstruction for Douglas-fir trees (1,372 samples).
• Utilized k-dominating set for species delineation in grasshopper mice (226 samples).

Conclusions:

• The k-dominating set approach provides a robust method for variable selection in large genetic datasets.
• This technique enhances the reliability of predictive analysis, generalization, and interpretability of genetic models.
• SNP-SELECT, implementing k-dominating set with Gurobi optimization, is available as open-source C++ code.