Grant: Discovery Grants Program - Individual
Université de Montréal
$20,000.00
Algorithmic and combinatorial studies inspired by problems of comparative genomics
EF 2013-14
Résumé
My research interests are in developing algorithmic approaches and combinatorial tools to solve theoretical problems inspired by biological problems arising in the field of comparative genomics. One of the basic aim of comparative genomics is to extract information from the comparison of genomes of different species. This information concerns the genomic sequence themselves, the order of appearance of genes in different genomes, the structure of small molecules (like RNA), etc. The general problem of extracting meaningful information from the resulting mass of biological information gives rise to many important theoretical problems on the fine combinatorics of words, permutations, trees or graphs. A first portion of my research program concerns the study and comparison of special trees and graphs representing non-coding RNA (ncRNA) structures. This study is of particular importance for biology because important cellular functions of ncRNA depend on their structural and combinatorial properties. Moreover, the fast expansion of complex databases of ncRNA structures (from barely 3 known families in 2002, to over 1,400 today) warrants the development of faster algorithms for the comparison and the analysis of such structures. A second portion concerns the study of permutations or signed permutations representing the order of appearance of genes in different genomes. Here, the problem consists in finding the median of a set of permutations under a distance d and is inspired by the gene order problem of comparative genomics, where the difference in order of appearance of genes in the genome of different species is used to evaluate the evolutionary distances between them. Finally, the expected theoretical results that will arise from the development of more efficient comparison algorithms in the field of bioinformatics is bound to help to solve similar problems in other field of computer science. We have already shown how our results may be applied in the context of software engineering where the maintenance of system requires the search of recurrent motifs in a program code.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
262965-2011
Name nom
Hamel, Sylvie
Department département
Informatique et recherche opérationnelle
Organization id
63
Institution établissement
Université de Montréal
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2013
Competition year année de concours
2011
Award amount
20000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
2714
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Mathematics of computing
Research subject fr
Mathématiques de l'informatique
Partie
3
Nb partie
5
Application title
Algorithmic and combinatorial studies inspired by problems of comparative genomics
Keyword
NSERC
Application summary
My research interests are in developing algorithmic approaches and combinatorial tools to solve theoretical problems inspired by biological problems arising in the field of comparative genomics. One of the basic aim of comparative genomics is to extract information from the comparison of genomes of different species. This information concerns the genomic sequence themselves, the order of appearance of genes in different genomes, the structure of small molecules (like RNA), etc. The general problem of extracting meaningful information from the resulting mass of biological information gives rise to many important theoretical problems on the fine combinatorics of words, permutations, trees or graphs. A first portion of my research program concerns the study and comparison of special trees and graphs representing non-coding RNA (ncRNA) structures. This study is of particular importance for biology because important cellular functions of ncRNA depend on their structural and combinatorial properties. Moreover, the fast expansion of complex databases of ncRNA structures (from barely 3 known families in 2002, to over 1,400 today) warrants the development of faster algorithms for the comparison and the analysis of such structures. A second portion concerns the study of permutations or signed permutations representing the order of appearance of genes in different genomes. Here, the problem consists in finding the median of a set of permutations under a distance d and is inspired by the gene order problem of comparative genomics, where the difference in order of appearance of genes in the genome of different species is used to evaluate the evolutionary distances between them. Finally, the expected theoretical results that will arise from the development of more efficient comparison algorithms in the field of bioinformatics is bound to help to solve similar problems in other field of computer science. We have already shown how our results may be applied in the context of software engineering where the maintenance of system requires the search of recurrent motifs in a program code.