NOTE:

The DFLearner software provided here is free for academic purpose. Please cite the following papers when using the DFLearner software in scientific publications.

Zheng Yun and Kwoh Chee Keong. Dynamic Algorithm for Inferring Qualitative Models of Gene Regulatory Networks. Proceedings of the 3rd Computer Society Bioinformatics conference, CSB 2004.pages: 353-364. IEEE Computer Society Press. 2004 [pdf] [slides]

Zheng Yun and Kwoh Chee Keong. Identifying simple discriminatory gene vectors with an information theory approach. In Proceedings of the 4th Computational Systems Bioinformatics Conference, CSB 2005, pages:12-23. IEEE Computer Society Press, 2005. [pdf] [slides] [supplements]

Include the software and the data files for some examples in the paper. Current version has been validated on Windows and HP Tru64 Unix platform.

online help

This software inputs the pre-miRNA sequences together with the secondary structure of them, then encode the sequences into 43 features.

In our experiments, we use the GUI version 3.4.2.

We use pre-miRNAs in the release 5.0 of the miRBase Sequence Database.

Rfam:miRBase

S1.1 The Selection of The Expected Cardinality K

We discuss the selection of K in this section. Generally, if a data set has a large number of features, like several thousands, then K can be assigned to a small constant, like 50, since the models with large number of features will be very difficult to understand. If the number of features is small, then the K can be directly specified to the number of features n.

Another usage of K is to control model complexity. If the number of features is more important than accuracy, then a predefined K can be set. Thus, the learned model will have less than or equal to K features.

The expected cardinality K can also be used to incorporate the prior knowledge about the number of relevant features. If we have the prior knowledge about the number of relevant features, then the K can be specified as the predetermined value.

S1.2 The Selection of The ε Value

For a given noisy data set, the missing part of H(Y), as demonstrated in Figure 1.4, is determined, i.e., there exists a specific minimum ε value, ε_m, with which the DFL algorithm can find the original model. If the ε value is smaller than the ε_m, the DFL algorithm will not find the original model. Here, we will introduce two methods to efficiently find the ε_m.

First, the ε_m can automatically be found by a restricted learning process. To efficiently find the minimum ε, we restrict the maximum number of the subsets to be checked to \sum_{i=0}^{K-1} (n - i) ~ Kn . In other words, we only let the DFL algorithm perform its first round searching,  as shown in Figure S1.3 of Introduction. The searching scope of ε is specified in prior. If the DFL algorithm can not find a model for a noisy data set with the specified minimum ε value, then the ε will be increased with a step of 0.01. The restricted learning will be performed, until the DFL algorithm finds a model with a threshold value of ε, i.e., the ε_m. Since only k * n subsets are checked in the restricted learning process, the time to find ε_m will be O(k * n).

The restricted learning process can also be used to find optimal model. To get optimal model, we change the ε value from 0 to the upper limit of the searching scope, like 0.8, with a step of 0.01. For each ε value, we train a model with the DFL algorithm, then validate its performance with the cross validation.

Second, the ε_m can also be found with a manual binary search method, as shown in Figure S1.6. Since ε \in [0,1), ε is specified to 0.5 in the first try. If the DFL algorithm finds a model with ε value of 0.5, then ε is specified to 0.25 in the second try. Otherwise, if the DFL algorithm can not find a model with a long time, like 10 minutes, then the DFL algorithm can be stopped and ε is specified to 0.75 in the second try. The selection process is carried out until the ε_m value is found so that the DFL algorithm can find a model with it but cannot when ε = ε_m - 0.01. This selection process is also efficient. Since ε \in [0,1), only 5 to 6 tries are needed to find the ε_m on the average.

We use the LED data sets with 10 percent noise to shown the procedure. For this example, in the first try, DFL algorithm finds a model with ε of 0.5. Then, the DFL algorithm cannot find a model with the ε of 0.25 in the second try. Similarly, in the 3rd to 6th tries, the DFL algorithm finds models with the specified ε values, 0.37, 0.31, 0.28 and 0.26. Since we have known in the second try that the DFL algorithm cannot find a model with ε of 0.25. Hence, 0.26 is the minimum ε value for this data set.

Figure S1. The manual binary search of minimum ε value. 

To find the best subset of EAs for the data sets, we first set the expected cardinality of the EAs K as 10. Next, we use the DFL algorithm to perform leave-one-out cross validation (LOOCV) on the training set (TR-C) with different ε values, from 0 to 0.8 with a step of 0.01. Then, we find that the DFL algorithm reaches its best prediction performance in the LOOCV when ε within [0.12, 0.13]. When using all samples in training data set, the distributions of attributes are slightly different from those in LOOCV. Thus, we try the DFL classifiers obtained from a wider region of ε within [0.1, 0.15]. Finally, we choose the DFL classifier obtained when ε = 0.11 because it shows overall better prediction accuracies for data set 1 to 4. In this way, a subset of 4 features, {A(((, G·((, length basepair ratio, energy per nucleotide}, is chosen as EAs for the human data sets, D1 to D4. For other data sets, we try the subsets of these 4 EAs and choose those subsets on which the 1NN algorithm introduced in Section 3.5 produces the best prediction performances. The selected EAs are shown in Figure 3 (a).

As shown in Figure S2, there is another region of ε around 0.5 within which the DFL algorithm achieves high prediction accuracy in cross validation. But the DFL models use more features when  ε decreases. Thus, we prefer the features chosen by the DFL algorithm when  ε is in the region of [0.1,0.15].

In this research, we use the data sets in literature (Xue et al. 2005) to validate our approach, since it is valuable to compare the published results. These data sets are summarized in Table S1. Data set 0 to 4 is from human, and data set 5 to 15 is from other species, as indicated by their names. Data set 0 is used as the training data set, and data set 1 to 15 are used as testing data sets. There are totally 4094 samples used as testing data sets, with 3444 background sequences and 650 pre-miRNAs.

The sequences of human pre-miRNAs are obtained from miRNA registry database (release 5.0) (Griffith-Jones, 2004). The secondary structures of these 207 pre-miRNA sequences are predicted with the RNAfold (Hofacker, 2003). Then, 193 sequences with only 1 loop are chosen. Next, 163 of them are randomly selected to be positive samples of the training data set, i.e., TR-C in Table S1. The rest 30 samples are used as TE-C1 testing data set.

The background sequences in data set 2 are collected from protein coding regions (CDSs) according to the UCSC refGene annotation tables (Xue et al. 2005). The length of these sequences has the same distribution of human pre-miRNAs. The RNAfold is also used to predict the secondary structure of them. Then, the sequences with multiple loops, the sequences with less than 18 base pairs and the sequences with larger than -15kcal/mol free energy are removed. Finally, there are 8494 sequences in this data sets. Among them, 168 are randomly selected as the negative samples of the TR-C data set, and 1000, different from the 168 used, are randomly chosen as the TE-C2 testing data set.

The data set 3 also consists of background sequences, which are retrieved from the genome region from position 56,000,001 to 57,000,000 on the human chromosome 19 with the UCSC database (Karolchik et al. 2003). A window of 100 nucleotide is used to scan the region and those sequences with a predicted hairpin secondary structure by the RNAfold (Hofacker, 2003) are selected. This produces 2444 background sequences in data set 3. Unlike data set 2, some sequences on data set 3 are likely to be the true pre-miRNAs. Actually, there are 3 known miRNAs (hsa-mir-99b, hsa-let-7e and hsa-mir-125a) in data set 3 (Xue et al. 2005).

Bentwich et al. (2005) reported 89 new pre-miRNAs, of which 1 has multiple loops and is removed. To further remove the similar sequences, BLASTCLUST with S = 80, L = 0.5 and W = 16 is applied to the remaining 88 sequences. Only one representative sequence in each cluster is selected to remove the closely related sequences. This produces 40 non-redundant sequences, which are further checked with respect to the training data set. One of the 40 sequences that has high similarity to the training data set is removed. Finally, only 39 sequences are chosen as the data set 4.

^$ For the local data sets, the prediction accuracies of the SVM algorithm in our study are slightly better than those in literature (Xue et al. 2005). We contribute this to the encoding region in our research. We encode the triplet local features for the whole pre-miRNAs, except the first and last nucleotide. However, only the paired regions of the pre-miRNAs are encoded into triplet features in (Xue et al. 2005). * The Tri-SVM column shows the results from literature (Xue et al. 2005).

References:

1. I. Bentwich, A. Avniel, Y. Karov, R. Aharonov, S. Gilad, O. Barad, A. Barzilai, P. Einat, U. Einav, E. Meiri, E. Sharon, Y. Spector, and Z. Bentwich. Identification of hundreds of conserved and nonconserved human micrornas. Nature Genetics, 37(7):766–70, 2005.

2. S. Griffiths-Jones. The microRNA Registry. Nucl. Acids Res., 32(90001):D109–111, 2004.

3. I.L. Hofacker. Vienna RNA secondary structure server. Nucl. Acids Res., 31(13):3429–3431, 2003.

4. D. Karolchik, R. Baertsch, M. Diekhans, T.S. Furey, A. Hinrichs, Y.T. Lu, K.M. Roskin, M. Schwartz, C.W. Sugnet, D.J. Thomas, R.J. Weber, D. Haussler, and W.J. Kent. The UCSC Genome Browser Database. Nucl. Acids Res., 31(1):51–54, 2003.

5. C. Xue, F. Li, T. He, G.-P. Liu, Y. Li, and X. Zhang. Classification of real and pseudo microRNA precursors using local structure-sequence features and support vector machine. BMC Bioinformatics, 6(1):310, 2005.