Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Saskatchewan

$41,000.00

Algorithms and Inference of Grammars and Natural Computing Models

FY 2023-24

Summary
When plant breeders create new varieties, they inspect thousands of plants looking for desirable or undesirable growth, and evidence of stress or disease. This has traditionally been done by manual inspection which forms a bottleneck that can be alleviated with automatic image analysis. Machine learning can be used to detect various components and their form; it is common to start with a large set of images with these properties already identified, and use them to train a model that maps inputs to outputs. Artificial neural networks are often used for this, but it is notoriously difficult to extract scientific knowledge from them. Formal grammars are a mathematical formalism with rules for rewriting strings that are repeatedly applied, starting from an initial symbol to create new strings. Lindenmayer systems (L systems) are a type of grammar system that were created to model multicellular structures present in many biological organisms with inherent self-similarity, such as plants. L systems have been widely used to create realistic visual simulations of developing plants. The first objective is to use L systems (and not e.g. neural networks) for predicting plant components and geometry from sequences of developing plant images. An existing L system created to capture a range of phenotypes (e.g. a species) will be used as a starting point. Image processing will be used as an initial prediction of plant components on each image. Then, software will be created to find the L system simulation that most closely matches the initial prediction. This simulation will form a new prediction that must be consistent with the developmental program of the plant (in contrast to predictions from images analyzed independently). This will detect some components even if they are completely hidden in an image. The accuracy will be compared to other predictive models. While this prediction does not require annotated data, it does require L systems which are also currently difficult to create, especially for each variety of interest. Hence, the second objective is to build algorithms and software to learn L systems automatically from data (images or descriptions of them). L systems can optionally have probabilities associated with rewriting rules which are used to calculate the probability of a simulation occurring. We will create software for their calculation using image data on top of the L system from the first objective. Next, software will be built to learn the rules themselves from data. The anticipated outcomes are the creation of new methods and software to use and learn L systems towards strengthening the pipeline for phenotyping and improving crops. Learned grammars and probabilities directly describe development and hence, scientific principles can be extracted and better understood. These are both critical towards increasing food security amidst a growing population and dramatic environmental changes within Canada and worldwide.
Program
Discovery Grants Program - Individual
Location
Saskatchewan, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2022-05092
Name nom
McQuillan, Ian
Department département
Computer Science - Computer Science
Organization id
16
Institution établissement
University of Saskatchewan
Province en
Saskatchewan
Province fr
Saskatchewan
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2023
Competition year année de concours
2022
Award amount
41000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
405
Area of application group en
Environment
Area of application group fr
Environnement
Area of application en
Modelling and mathematical simulation of natural processes
Area of application fr
Modélisation et simulation mathématique des processus naturels
Research subject code
2712
Research subject group en
Information technology
Research subject group fr
Theory of computation
Research subject en
Technologie de l'information
Research subject fr
Théorie de calcul
Application title
Algorithms and Inference of Grammars and Natural Computing Models
Keyword
Algorithms; Computational biology; Computational complexity; Computational models; Formal grammar systems; Formal language theory; Inference; Lindenmayer systems; Natural computing; Theoretical computer science
Application summary
When plant breeders create new varieties, they inspect thousands of plants looking for desirable or undesirable growth, and evidence of stress or disease. This has traditionally been done by manual inspection which forms a bottleneck that can be alleviated with automatic image analysis. Machine learning can be used to detect various components and their form; it is common to start with a large set of images with these properties already identified, and use them to train a model that maps inputs to outputs. Artificial neural networks are often used for this, but it is notoriously difficult to extract scientific knowledge from them. Formal grammars are a mathematical formalism with rules for rewriting strings that are repeatedly applied, starting from an initial symbol to create new strings. Lindenmayer systems (L systems) are a type of grammar system that were created to model multicellular structures present in many biological organisms with inherent self-similarity, such as plants. L systems have been widely used to create realistic visual simulations of developing plants. The first objective is to use L systems (and not e.g. neural networks) for predicting plant components and geometry from sequences of developing plant images. An existing L system created to capture a range of phenotypes (e.g. a species) will be used as a starting point. Image processing will be used as an initial prediction of plant components on each image. Then, software will be created to find the L system simulation that most closely matches the initial prediction. This simulation will form a new prediction that must be consistent with the developmental program of the plant (in contrast to predictions from images analyzed independently). This will detect some components even if they are completely hidden in an image. The accuracy will be compared to other predictive models. While this prediction does not require annotated data, it does require L systems which are also currently difficult to create, especially for each variety of interest. Hence, the second objective is to build algorithms and software to learn L systems automatically from data (images or descriptions of them). L systems can optionally have probabilities associated with rewriting rules which are used to calculate the probability of a simulation occurring. We will create software for their calculation using image data on top of the L system from the first objective. Next, software will be built to learn the rules themselves from data. The anticipated outcomes are the creation of new methods and software to use and learn L systems towards strengthening the pipeline for phenotyping and improving crops. Learned grammars and probabilities directly describe development and hence, scientific principles can be extracted and better understood. These are both critical towards increasing food security amidst a growing population and dramatic environmental changes within Canada and worldwide.
University of Saskatchewan - $41,000 Grant (2023-24) | Canada Spends