Che et al. BMC Genomics 2010, 11(Suppl 2):S1 http://www.biomedcentral.com/1471-2164/11/S2/S1 The analyses of the contribution of single features by using signal-to-noise analysis and leave-one-feature-out analysis, suggests that feature interaction is quite com- plicated in this domain. While the single feature analysis sheds new lights on the utility of each feature, it does not tell us that it will be informative or redundant when multiple feature models are integrated. Methods GI and non-GI Datasets We obtained the datasets of GIs (positives) and non-GIs (negatives) of genus Salmonella, Staphylococcus, and Streptococcus processed by Vernikos and Parkhill [18]. The detection of GIs was based on the fact that a geno- mic region limited in one lineage was more likely to have been horizontally acquired than to have been deleted independently from multiple lineages [23]. On the other hand, if a genomic region that is present in one lineage and most of strains of another lineage, we consider the genomic region that is missing in some strain of another lineage is involved in the deletion, rather than horizontally acquired. Based on these stu- dies, putative GIs could be derived by combining com- parative analysis and the maximum parsimony models [24]. The numbers of GIs selected from the genus Sal- monella, Staphylococcus and Streptococcus were 211, 54 and 66, respectively, with the total positives of 331. For each detected GI of a genome, a corresponding non-GI with the same genomic region size was ran- domly sampled within the inter-GI regions. The redun- dant non-GIs that sampled from the different strains of the same genus were removed, and the sampling results of non-GIs for genus Salmonella Staphylococcus and Streptococcus were 210, 53 and 74, respectively, with the total negatives of 337. For each instance (either GI or non-GI) of these data- sets, eight feature values, i.e., IVOM, Insert point, Size, Density, Repeats, Integrase, Phage and RNA, were obtained. The Interpolated Variable Order Motif (IVOM) score measures the composition bias of a geno- mic region relative to the background genomic region by using the relative entropy of both low and high order motifs in a genomic region over the background genome [15]. Repeats were detected by the REPuter [25] pro- gram which starts with finding exact repeats, and then significantly degenerated repeats to allow mismatch, insertion, or deletion. The protein domains associated with integrases and phages were retrieved from the Pfam protein families database [26]. Finally, RNA regions was detected by tRNAscan-SE [27]. Problem formulation The goal of this study is to construct classifiers that can accurately classify the gnomic islands and non-genomic E(S) = –pGIlog2pGI – pNGlog2pNG where pGI is the probability that the selected dataset is of GI (i.e., the percentage of GIs in S), and conversely, pNG is for non-GI. Value(A) is the set of all possible values for the feature A, one of eight features in this study. Sv is the subset of S for which feature A has the value of v (i.e., Sv = {s Î S|A(s) = v}). The ID3 algorithm splits the set based on the possible values of the selected best feature. If the all instances in a subset have the same output value (i.e., either GI or non-GI), then the process stops for that branch, and that node is a terminal node. If the subset does contain instances from two classes (both GI and non-GI), this islands from the genomic data in prokaryotic organisms. The classifiers can then be used as the basis for classify- ing any genomic segment in a whole genome. This is a classical supervised learning problem that applies a learning algorithm on the training data and performs prediction on the test data. The training examples are a set of tuples <x, c>, where c is the class label (i.e., either genomic island (GI) or non-genomic island), and x is the set of attributes for the instances. In this study, eight attributes (IVOM, Insert point, Size, Density, Repeats, Integrase, Phage and RNA) are included. The learning algorithm is trained on the positive E+ (i.e., GIs) and negative E- (i.e., non-GIs) examples to con- struct a classifier C(x) that distinguishes between these examples. Decision tree and decision tree based ensemble algorithms Decision tree In this study, we use J48 in WEKA, the Java implemen- tation of C4.8 algorithm. C4.8 is the latest research ver- sion for the C4.5 algorithm, which is one of the best- known and most widely-used decision tree algorithms. C4.5 extends the ID3 algorithm by addressing several important issues. The C4.5 algorithm handles numerical attributes and missing values, it also incorporates post- pruning process to handle the over-fitting problem. The ID3 algorithm [28] implements a top-down greedy search schema to search through all possible tree spaces. It starts with all training set (S) and chooses the best feature as the root node. The best feature should have the highest calculated value of information gain (IG), which is defined as IG(S, A) = E(S) − ∑ v∈Value(A) | Sv |E(Sv ) S where E(S) is the entropy of S, which in turn is defined as Page 7 of 9 (2) (3)