A CART-based approach to discover emerging patterns in microarray data.
BACKGROUND
Cancer diagnosis using gene expression profiles requires supervised learning and gene selection methods. Of the many suggested approaches, the method of emerging patterns (EPs) has the particular advantage of explicitly modeling interactions among genes, which improves classification accuracy. However, finding useful (i.e. short and statistically significant) EP is typically very hard.


METHODS
Here we introduce a CART-based approach to discover EPs in microarray data. The method is based on growing decision trees from which the EPs are extracted. This approach combines pattern search with a statistical procedure based on Fisher's exact test to assess the significance of each EP. Subsequently, sample classification based on the inferred EPs is performed using maximum-likelihood linear discriminant analysis.


RESULTS
Using simulated data as well as gene expression data from colon and leukemia cancer experiments we assessed the performance of our pattern search algorithm and classification procedure. In the simulations, our method recovers a large proportion of known EPs while for real data it is comparable in classification accuracy with three top-performing alternative classification algorithms. In addition, it assigns statistical significance to the inferred EPs and allows to rank the patterns while simultaneously avoiding overfit of the data. The new approach therefore provides a versatile and computationally fast tool for elucidating local gene interactions as well as for classification.


BACKGROUND
A computer program written in the statistical language R implementing the new approach is freely available from the web page http://www.stat.uni-muenchen.de/~socher/
Boulesteix
Anne-Laure
AL
Seminar for Applied Stochastics, Department of Statistics, University of Munich, Akademiestrasse 1, D-80799 Munich, Germany. boulesteix@stat.uni-muenchen.de
Tutz
Gerhard
G
Strimmer
Korbinian
K
D000465:Algorithms; D001185:Artificial Intelligence; D003110:Colonic Neoplasms / Q000145:classification / Q000175:diagnosis / Q000235:genetics*; D020869:Gene Expression Profiling / Q000379:methods*; D005820:Genetic Testing / Q000379:methods; D006801:Humans; D007938:Leukemia / Q000145:classification / Q000175:diagnosis / Q000235:genetics*; D020411:Oligonucleotide Array Sequence Analysis / Q000379:methods*; D010363:Pattern Recognition, Automated; D015203:Reproducibility of Results; D012680:Sensitivity and Specificity