Speeding Up the Discovery of Optimal Feature Combinations for Omics Data Based on Pseudo-Kernel Function

Discovering meaningful feature (molecule) combinations to define simple, accurate, and easily interpretable decision rules for disease classification and prediction can improve the study of disease diagnosis and prognosis. However, the computational time complexity of constructing feature combinations for each feature pair in existing methods is often problematic or prohibitive, as the number of features is often in the order of tens of thousands. To significantly reduce the computational cost and maintain the classification performance, this paper proposed a novel acceleration algorithm and a new omics data analysis method based on pseudo kernel functions (PKF- $k$ -TSP). PKF- $k$ -TSP explores the linear and nonlinear combination of features by pseudo kernel function, evaluate feature interaction, and selects $k>0$ top-scoring pairs to build an ensemble classifier. PKF- $k$ -TSP maps feature pairs from a low-dimensional space to a high-dimensional feature space by a mapping function, as the same effect as kernel function, and ensure the classification performance. However, it significantly reduces the computational time costs. Experimental results demonstrate that PKF- $k$ -TSP achieves superior classification performance, while exhibiting significantly improved computational efficiency compared with KF- $k$ -TSP, with the running time reduced by 72.43%. Furthermore, the feature pairs identified by PKF- $k$ -TSP align with physiological and pathological changes, offering insights into disease mechanisms. The method also excels in cross-cancer pathway interaction analysis, capturing both conserved and tissue-specific signaling networks. Hence, PKF- $k$ -TSP enables rapid and efficient feature mining, which is especially suitable for large-scale disease omics data analysis.