Gene array data have been widely used for cancer diagnosis in recent years. However, high dimensionality has been a major problem for gene array-based classification. Gene selection is critical for accurate classification and for identifying the marker genes to discriminate different tumor types. This paper created a framework of gene selection methods based on previous studies. We focused on optimal search-based gene subset selection methods that evaluate the group performance of genes and help to pinpoint global optimal set of marker genes. Notably, this study is the first to introduce tabu search to gene selection from high dimensional gene array data. Experimental studies on several gene array datasets demonstrated the effectiveness of optimal search-based gene subset selection to identify marker genes.