Parsing Expression Grammars and Their Induction Algorithm
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 expre...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-12-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/10/23/8747 |
| _version_ | 1797545519440986112 |
|---|---|
| author | Wojciech Wieczorek Olgierd Unold Łukasz Strąk |
| author_facet | Wojciech Wieczorek Olgierd Unold Łukasz Strąk |
| author_sort | Wojciech Wieczorek |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-10T14:16:37Z |
| format | Article |
| id | doaj.art-79989ce4ee7241fb924ca0a6e4bab5b1 |
| institution | Directory Open Access Journal |
| issn | 2076-3417 |
| language | English |
| last_indexed | 2024-03-10T14:16:37Z |
| publishDate | 2020-12-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj.art-79989ce4ee7241fb924ca0a6e4bab5b12023-11-20T23:44:42ZengMDPI AGApplied Sciences2076-34172020-12-011023874710.3390/app10238747Parsing Expression Grammars and Their Induction AlgorithmWojciech Wieczorek0Olgierd Unold1Łukasz Strąk2Department of Computer Science and Automatics, University of Bielsko-Biala, Willowa 2, 43-309 Bielsko-Biala, PolandDepartment of Computer Engineering, Wroclaw University of Science and Technology, Wyb. Wyspianskiego 27, 50-370 Wroclaw, PolandFaculty of Science and Technology, University of Silesia in Katowice, Bankowa 14, 40-007 Katowice, PolandGrammatical 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.https://www.mdpi.com/2076-3417/10/23/8747classificationgenetic programminggrammatical inferenceparsing expression grammar |
| spellingShingle | Wojciech Wieczorek Olgierd Unold Łukasz Strąk Parsing Expression Grammars and Their Induction Algorithm Applied Sciences classification genetic programming grammatical inference parsing expression grammar |
| title | Parsing Expression Grammars and Their Induction Algorithm |
| title_full | Parsing Expression Grammars and Their Induction Algorithm |
| title_fullStr | Parsing Expression Grammars and Their Induction Algorithm |
| title_full_unstemmed | Parsing Expression Grammars and Their Induction Algorithm |
| title_short | Parsing Expression Grammars and Their Induction Algorithm |
| title_sort | parsing expression grammars and their induction algorithm |
| topic | classification genetic programming grammatical inference parsing expression grammar |
| url | https://www.mdpi.com/2076-3417/10/23/8747 |
| work_keys_str_mv | AT wojciechwieczorek parsingexpressiongrammarsandtheirinductionalgorithm AT olgierdunold parsingexpressiongrammarsandtheirinductionalgorithm AT łukaszstrak parsingexpressiongrammarsandtheirinductionalgorithm |