Grant: Discovery Grants Program - Individual
Université de Montréal
$22,000.00
Algorithmic and combinatorial problems inspired by comparative genomics.
EF 2020-21
Résumé
Abstract: Sitting at the interface of theoretical computer science and mathematics, my area of research concerns the development of algorithmic approaches and combinatorial tools for theoretical problems inspired by biological problems, coming mostly from comparative genomics. Roughly speaking, comparative genomics aims at extracting information from the comparison of genomes of different species. This information may concern genomic sequences 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 very large mass of biological data gives rise to many important problems on combinatorial objects such as words, permutations, trees or graphs. For instance, permutations partially encode the structure of genomes. The development of efficient algorithms for the manipulation of these discrete structures is also crucial in this context. One finds that, in any one of these specific contexts, many different notions of distances have been suggested to compare the relevant objects, with the consequence that we now have to clearly characterize the ``best'' distances among these. For sure, this quality measurement of distances is closely tied to the construction of efficient algorithms fulfilling the desired goal.
My research program consists in studying how one should compare and analyze such distances with respect to their principal properties, and to quantify their relevance to a given context. Concrete results of this study lead to the construction of new efficient algorithms to help solve several problems related to distances optimization. Among important uses of distances in applied contexts one looks for a way to aggregate a set of solutions of a given problem into a consensus solution which highlights common desired features, while minimizing disagreements. One original aspect of my program rests on the study of how to efficiently (algorithmically) reach these consensus solutions in various context.
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
RGPIN-2016-04576
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
2020
Competition year année de concours
2016
Award amount
22000
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
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Installment
inst:5-6
Partie
2
Nb partie
6
Application title
Algorithmic and combinatorial problems inspired by comparative genomics.
Keyword
NSERC
Application summary
Abstract: Sitting at the interface of theoretical computer science and mathematics, my area of research concerns the development of algorithmic approaches and combinatorial tools for theoretical problems inspired by biological problems, coming mostly from comparative genomics. Roughly speaking, comparative genomics aims at extracting information from the comparison of genomes of different species. This information may concern genomic sequences 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 very large mass of biological data gives rise to many important problems on combinatorial objects such as words, permutations, trees or graphs. For instance, permutations partially encode the structure of genomes. The development of efficient algorithms for the manipulation of these discrete structures is also crucial in this context. One finds that, in any one of these specific contexts, many different notions of distances have been suggested to compare the relevant objects, with the consequence that we now have to clearly characterize the ``best'' distances among these. For sure, this quality measurement of distances is closely tied to the construction of efficient algorithms fulfilling the desired goal.
My research program consists in studying how one should compare and analyze such distances with respect to their principal properties, and to quantify their relevance to a given context. Concrete results of this study lead to the construction of new efficient algorithms to help solve several problems related to distances optimization. Among important uses of distances in applied contexts one looks for a way to aggregate a set of solutions of a given problem into a consensus solution which highlights common desired features, while minimizing disagreements. One original aspect of my program rests on the study of how to efficiently (algorithmically) reach these consensus solutions in various context.