A Learning Algorithm for Elementary Formal Systems and its Experiments on Identification of Transmembrane Domains

Proc. 25th Int.Conf. Hawaii International Conference on Information Systems, 675-684, 1992We propose a method for algorithmic learning of transmembrane domains based 0n elementary formal systems. An elementary formal system (EFS, for short) is a kind of a logic program consisting of ifthen rules. With this framework, we have implemented the algorithm for identifying transmembrane domains in amino acid sequences. Because of the limitations on computational resources, we restrict candidate hypotheses to EFSs defined by collections of regular patterns. From 70 transmembrane sequences and a similar amount of negative examples which are not transmembrane sequences, our algorithm has produced several reasonable hypotheses of small size. Experiments with the database PIR show that one of them recognizes 95% of 689 transmembrane sequences and 95% of 19256 negative examples which consist of nontransmembrane sequences of length around 30 randomly chosen from PIR