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

BMC Bioinformatics

Research Article

Jianwen Fang¹  Shu-Lin Wang²  Xue-Ling Li³ 

[1] Applied Bioinformatics Laboratory, the University of Kansas, 2034 Becker Drive, 66047, Lawrence, KS, USA;College of Information Science and Engineering, Hunan University, 410082, Changsha, Hunan, China;Intelligent Computing Laboratory, Hefei Institute of Intelligent Machines, Chinese Academy of Sciences, 230031, Hefei, Anhui, China;Applied Bioinformatics Laboratory, the University of Kansas, 2034 Becker Drive, 66047, Lawrence, KS, USA;Intelligent Computing Laboratory, Hefei Institute of Intelligent Machines, Chinese Academy of Sciences, 230031, Hefei, Anhui, China;

关键词: Gene expression profiles;    Gene selection;    Tumor classification;    Heuristic breadth-first search;    Power-law distribution;   

DOI  :  10.1186/1471-2105-13-178

 received in 2011-12-22, accepted in 2012-05-18,  发布年份 2012

来源: Springer

【 摘 要 】

BackgroundPrevious studies on tumor classification based on gene expression profiles suggest that gene selection plays a key role in improving the classification performance. Moreover, finding important tumor-related genes with the highest accuracy is a very important task because these genes might serve as tumor biomarkers, which is of great benefit to not only tumor molecular diagnosis but also drug development.ResultsThis paper proposes a novel gene selection method with rich biomedical meaning based on Heuristic Breadth-first Search Algorithm (HBSA) to find as many optimal gene subsets as possible. Due to the curse of dimensionality, this type of method could suffer from over-fitting and selection bias problems. To address these potential problems, a HBSA-based ensemble classifier is constructed using majority voting strategy from individual classifiers constructed by the selected gene subsets, and a novel HBSA-based gene ranking method is designed to find important tumor-related genes by measuring the significance of genes using their occurrence frequencies in the selected gene subsets. The experimental results on nine tumor datasets including three pairs of cross-platform datasets indicate that the proposed method can not only obtain better generalization performance but also find many important tumor-related genes.ConclusionsIt is found that the frequencies of the selected genes follow a power-law distribution, indicating that only a few top-ranked genes can be used as potential diagnosis biomarkers. Moreover, the top-ranked genes leading to very high prediction accuracy are closely related to specific tumor subtype and even hub genes. Compared with other related methods, the proposed method can achieve higher prediction accuracy with fewer genes. Moreover, they are further justified by analyzing the top-ranked genes in the context of individual gene function, biological pathway, and protein-protein interaction network.

【 授权许可】

Unknown   
© Wang et al.; licensee BioMed Central Ltd. 2012. This article is published under license to BioMed Central Ltd. This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.