Parsing Expression Grammars and Their Induction Algorithm
Source abstract
Abstract
Grammatical inference (GI), i.e., the task of finding a rule that lies behind given words, can be used in the analyses of amyloidogenic sequence fragments, which are essential in studies of neurodegenerative diseases. In this paper, we developed a new method that generates non-circular parsing expression grammars (PEGs) and compares it with other GI algorithms on the sequences from a real dataset. The main contribution of this paper is a genetic programming-based algorithm for the induction of parsing expression grammars from a finite sample. The induction method has been tested on a real bioinformatics dataset and its classification performance has been compared to the achievements of existing grammatical inference methods. The evaluation of the generated PEG on an amyloidogenic dataset revealed its accuracy when predicting amyloid segments. We show that the new grammatical inference algorithm achieves the best ACC (Accuracy), AUC (Area under ROC curve), and MCC (Mathew’s correlation coefficient) scores in comparison to five other automata or grammar learning methods.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Machine Learning and Algorithms · Algorithms and Data Compression · Machine Learning in Bioinformatics
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Department of Computer Science and Automatics, University of Bielsko-Biala, Willowa 2, 43-309 Bielsko-Biala, Poland
Department of Computer Engineering, Wroclaw University of Science and Technology, Wyb. Wyspianskiego 27, 50-370 Wroclaw, Poland
Faculty of Science and Technology, University of Silesia in Katowice, Bankowa 14, 40-007 Katowice, Poland
Funding
Polish National Science Center
References (25)
Show source-provided references
1. De la Higuera, C. (2010). Grammatical Inference: Learning Automata and Grammars, Cambridge University Press.10.1017/CBO9781139194655 ↗
2. Wieczorek, W. (2017). Grammatical Inference—Algorithms, Routines and Applications, Springer. Studies in Computational Intelligence.10.1007/978-3-319-46801-3 ↗
3. Language Identification in the Limit10.1016/S0019-9958(67)91165-5 ↗
4. Coste, F., and Fredouille, D. (2003, January 22–26). Unambiguous Automata Inference by Means of State-Merging Methods. Proceedings of the Machine Learning: ECML 2003, 14th European Conference on Machine Learning, Cavtat-Dubrovnik, Croatia.10.1007/978-3-540-39857-8_8 ↗
5. Grammatical Inference
6. Carrasco, R.C., and Oncina, J. (1994). Regular grammatical inference from positive and negative samples by genetic search: The GIG method. Grammatical Inference and Applications, Springer.10.1007/3-540-58473-0 ↗
7. Learning context-free grammars using tabular representations10.1016/j.patcog.2004.03.021 ↗
8. Unsupervised learning of natural languages10.1073/pnas.0409746102 ↗
9. Devijver, P.A., and Kittler, J. (1987). Modelling (Sub)String Length Based Constraints through a Grammatical Inference Method. Proceedings of the NATO Advanced Study Institute on Pattern Recognition Theory and Applications, Springer.10.1007/978-3-642-83069-3 ↗
10. van Zaanen, M. (August, January 31). ABL: Alignment-based Learning. Proceedings of the 18th Conference on Computational Linguistics—Volume 2, Jcken, Germany. COLING ’00.10.3115/992730.992785 ↗
11. LARS: A learning algorithm for rewriting systems10.1007/s10994-006-9593-8 ↗
12. XML schema validation using parsing expression grammars
13. A text pattern-matching tool based on Parsing Expression Grammars10.1002/spe.892 ↗
14. Leporati, A., Martín-Vide, C., Shapira, D., and Zandron, C. (2020). Simplified Parsing Expression Derivatives. Language and Automata Theory and Applications, Springer International Publishing.10.1007/978-3-030-40608-0 ↗
15. Hopcroft, J.E., Motwani, R., and Ullman, J.D. (2001). Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Longman Publishing Co., Inc.. [2nd ed.].10.1145/568438.568455 ↗
16. Ford, B. (2004, January 14–16). Parsing expression grammars: A recognition-based syntactic foundation. Proceedings of the 31st ACM SIGACT/SIGPLAN Symposium on Principles of Programming Languages, Venice, Italy.10.1145/964001.964011 ↗
17. Grune, D., and Jacobs, C. (2008). Parsing Techniques: A Practical Guide, Springer.10.1007/978-0-387-68954-8 ↗
18. Banzhaf, W., Francone, F.D., Keller, R.E., and Nordin, P. (1998). Genetic Programming: An Introduction: On the Automatic Evolution of Computer Programs and Its Applications, Morgan Kaufmann Publishers Inc.
19. Tomita, M. (1982). Learning of Construction of Finite Automata from Examples Using Hill-Climbing: RR: Regular Set Recognizer, Department of Computer Science, Carnegie-Mellon University.10.21236/ADA120123 ↗
20. AmyLoad: Website dedicated to amyloidogenic protein fragments10.1093/bioinformatics/btv375 ↗
21. Lang, K., Pearlmutter, B., and Price, R. (1998). Results of the Abbadingo one DFA Learning Competition and a New Evidence-Driven State Merging Algorithm, Springer. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics).10.1007/BFb0054059 ↗
22. Lang, K.J. (1992, January 27–29). Random DFA’s can be approximately learned from sparse uniform examples. Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory, Pittsburgh, PA, USA.10.1145/130385.130390 ↗
23. Trakhtenbrot, B., and Barzdin, Y. (1973). Finite Automata: Behavior and Synthesis, North-Holland Publishing Company. Fundamental Studies in Computer Science.
24. Continuous Distributed Representation of Biological Sequences for Deep Proteomics and Genomics10.1371/journal.pone.0141287 ↗
25. Probability Estimates for Multi-class Classification by Pairwise Coupling