Finding alphabet indexing for decision trees over regular patterns: an approach to bioinformatical knowledge acquisition

Considers a transformation from an alphabet to a smaller alphabet which does not lose any positive and negative information of the original examples. Such a transformation is called indexing. A method which exploits indexing by a local search technique for learning decision trees over regular patterns is proposed. From positive and negative examples, the system produces, as a hypothesis, an indexing-decision tree pair. The authors also report some experimental results obtained by this machine learning system on the following identification problems: transmembrane domains, and signal peptides. For transmembrane domains, the system discovered an indexing by two symbols and a decision tree with just three nodes that achieves 92% accuracy. The indexing was almost the same as that biased on the hydropathy index of Kyte and Doolittle (1982). For signal peptides, the system also found sufficiently good hypotheses.