Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Ottawa

$14,000.00

Combinatorial algorithms for pattern discovery in RNA sequences

EF 2006-07

Résumé
In recent years, we have seen a rapid growth of the number of known RNA families.  For a significant fraction of them, the mechanisms of action remain unclear. Their signature combines structure and sequence information. In most cases, they are difficult to identify from sequence alone.  Traditional approaches to identify RNA motifs seek to find conserved structures with minimum free energy in an ensemble of aligned sequences.  Often, an alignment is not readily available because of the difficulty to build a reliable alignment without prior information about the structure. Accordingly, comparative analyses are mostly done by hand, iteratively, starting with the most conserved sequences. We recently developed two prototype software systems for the simultaneous alignment and structure prediction of three RNA sequences (eXtended Dynalign), as well as for the inference of RNA secondary structure/sequence motifs (Seed).  Our research suggests that using several input sequences allows to circumvent limitations of the nearest neighbour free energy model --- as the number of input sequences increases it becomes less likely that all of them simultaneously fold into a bad free-energy minimum.  We showed that the use of three input sequences greatly improves the accuracy compared to predictions made from one or two input sequences.  We have also shown that support and exclusion constraints are sufficiently powerful to allow for our combinatorial algorithm to enumerate exhaustively the search space of all conserved motifs. We propose several extensions to the software systems eXtended Dynalign and Seed. Our primary research objective is to develop and compare new objective functions for ranking RNA secondary structure motifs.  Our work on eXtended Dynalign suggests that the accuracy of the nearest neighbour model improves as the number of input sequences increases.  Accordingly, we will explore schemes that are based on this model. In parallel to this work, we will also develop objective functions inspired from models that have been successful for the discovery of sequence patterns. In particular, we will develop objective functions based on the minimum description length encoding principle.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
250909-2006
Name nom
Turcotte, Marcel
Department département
Information Technology and Engineering, School of
Organization id
28
Institution établissement
University of Ottawa
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2006
Competition year année de concours
2006
Award amount
14000
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
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
Area of application code
1201
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Life sciences (including biotechnology)
Area of application fr
Sciences de la vie (y compris biotechnologie)
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
Combinatorial algorithms for pattern discovery in RNA sequences
Keyword
NA
Application summary
In recent years, we have seen a rapid growth of the number of known RNA families.  For a significant fraction of them, the mechanisms of action remain unclear. Their signature combines structure and sequence information. In most cases, they are difficult to identify from sequence alone.  Traditional approaches to identify RNA motifs seek to find conserved structures with minimum free energy in an ensemble of aligned sequences.  Often, an alignment is not readily available because of the difficulty to build a reliable alignment without prior information about the structure. Accordingly, comparative analyses are mostly done by hand, iteratively, starting with the most conserved sequences. We recently developed two prototype software systems for the simultaneous alignment and structure prediction of three RNA sequences (eXtended Dynalign), as well as for the inference of RNA secondary structure/sequence motifs (Seed).  Our research suggests that using several input sequences allows to circumvent limitations of the nearest neighbour free energy model --- as the number of input sequences increases it becomes less likely that all of them simultaneously fold into a bad free-energy minimum.  We showed that the use of three input sequences greatly improves the accuracy compared to predictions made from one or two input sequences.  We have also shown that support and exclusion constraints are sufficiently powerful to allow for our combinatorial algorithm to enumerate exhaustively the search space of all conserved motifs. We propose several extensions to the software systems eXtended Dynalign and Seed. Our primary research objective is to develop and compare new objective functions for ranking RNA secondary structure motifs.  Our work on eXtended Dynalign suggests that the accuracy of the nearest neighbour model improves as the number of input sequences increases.  Accordingly, we will explore schemes that are based on this model. In parallel to this work, we will also develop objective functions inspired from models that have been successful for the discovery of sequence patterns. In particular, we will develop objective functions based on the minimum description length encoding principle.