Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

Université de Montréal

$25,000.00

Algorithms for the inference of gene family evolution

EF 2008-09

Résumé
This is a computational biology project based on algorithmic, mathematical and combinatorial optimization methods. We focus on different problematics related to the evolutionary study of multigene families. We will consider different optimization problems, study the theoretical complexity of such problems, develop appropriate algorithmic solutions and test them on simulated and real data. Genes are the major building blocks of genomic sequences containing the information necessary to produce all the proteins and non-coding RNAs necessary for the cell machinery. The natural and systematic approach used for identifying genes in a set of different genomes is by sequence comparison using classical bioinformatics tools such as BLAST. Genes sharing homologous sequences are grouped in a multigene family. Understanding the evolution of such gene families is a fundamental problem that has several applications. For example, it can help to distinguish between orthologs and paralogs: orthologs are copies that are directly related through speciation, while paralogs are copies that have evolved by duplication. This is an important question for functional annotation of genes, as it is believed that pairs of orthologs are more likely to have similar functions. A natural way of distinguishing between paralogs and orthologs is to infer the duplication and speciation events from the phylogenetic tree of a gene family. This question has been widely considered in the case of a well established species tree. In this proposal, we will consider the more general case of an unknown species tree. We will also focus on a particular class of gene families: tandemly arrayed genes. They constitute a large fraction of most genomes and play important roles. We will consider different questions related to a Duplication/Speciation/Loss/inversion model of evolution for TAGs. We will apply our algorithms to the olfactory receptor genes in different mammalian species.
Programme
Discovery Grants Program - Individual
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
217222-2008
Name nom
ElMabrouk, Nadia
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
2008
Competition year année de concours
2008
Award amount
25000
Program id
RGPIN
Program nane 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
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
Area of application code
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
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
Partie
1
Nb partie
5
Application title
Algorithms for the inference of gene family evolution
Keyword
NA
Application summary
This is a computational biology project based on algorithmic, mathematical and combinatorial optimization methods. We focus on different problematics related to the evolutionary study of multigene families. We will consider different optimization problems, study the theoretical complexity of such problems, develop appropriate algorithmic solutions and test them on simulated and real data. Genes are the major building blocks of genomic sequences containing the information necessary to produce all the proteins and non-coding RNAs necessary for the cell machinery. The natural and systematic approach used for identifying genes in a set of different genomes is by sequence comparison using classical bioinformatics tools such as BLAST. Genes sharing homologous sequences are grouped in a multigene family. Understanding the evolution of such gene families is a fundamental problem that has several applications. For example, it can help to distinguish between orthologs and paralogs: orthologs are copies that are directly related through speciation, while paralogs are copies that have evolved by duplication. This is an important question for functional annotation of genes, as it is believed that pairs of orthologs are more likely to have similar functions. A natural way of distinguishing between paralogs and orthologs is to infer the duplication and speciation events from the phylogenetic tree of a gene family. This question has been widely considered in the case of a well established species tree. In this proposal, we will consider the more general case of an unknown species tree. We will also focus on a particular class of gene families: tandemly arrayed genes. They constitute a large fraction of most genomes and play important roles. We will consider different questions related to a Duplication/Speciation/Loss/inversion model of evolution for TAGs. We will apply our algorithms to the olfactory receptor genes in different mammalian species.