Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Saskatchewan

$41,000.00

Algorithms and Inference of Grammars and Natural Computing Models

EF 2024-25

Résumé
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.
Programme
Discovery Grants Program - Individual
Emplacement
Saskatchewan, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

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
2024
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
2717
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Modelling and simulation studies
Research subject fr
Études de modélisation et de simulation
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Algorithms and Inference of Grammars and Natural Computing Models
Keywords
computational biology; formal grammar systems; lindenmayer systems; natural computing; computational models; theoretical computer science; formal language theory; inference; algorithms; computational complexity
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.