Finding minimum gene subsets with heuristic breadth-first search algorithm for robust tumor classification.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Gene selection is crucial for accurate tumor classification from gene expression profiles.
• Identifying tumor-related genes is vital for molecular diagnosis and drug development, serving as potential biomarkers.

Purpose of the Study:

• To propose a novel, biomedically meaningful gene selection method using the Heuristic Breadth-first Search Algorithm (HBSA).
• To address overfitting and selection bias in gene selection through an ensemble classifier and a gene ranking approach.
• To identify important tumor-related genes with high accuracy.

Main Methods:

• Developed a Heuristic Breadth-first Search Algorithm (HBSA) for optimal gene subset selection.
• Constructed an HBSA-based ensemble classifier using a majority voting strategy to mitigate overfitting.
• Designed an HBSA-based gene ranking method based on gene occurrence frequencies in selected subsets.

Main Results:

• The proposed method demonstrated superior generalization performance across nine tumor datasets, including cross-platform comparisons.
• Identified numerous important tumor-related genes with high predictive accuracy.
• Experimental results showed improved prediction accuracy with fewer genes compared to existing methods.

Conclusions:

• Gene frequencies in selected subsets follow a power-law distribution, highlighting a few top-ranked genes as potential diagnostic biomarkers.
• Top-ranked genes are linked to specific tumor subtypes and act as hub genes.
• The identified genes' relevance was further validated through functional, pathway, and network analyses.