Grant: Discovery Grants Program - Individual
University of Waterloo
$34,000.00
Theory and applications of sequence analysis
FY 2013-14
Summary
Discrete sequences arrive in scientific analysis in a variety of contexts, from biological sequences such as DNA or RNA sequences, to musical sequences such as the notes found in a score, to text sequences, such as the words of a document. For naturally-occuring sequences, what is the information that evolution or other processes has embedded in them? For man-made sequences, what patterns are imposed into the sequence, deliberately or not? Common tools are used to analyze such sequences. One tool is hidden Markov models (HMMs), invented to decode speech recordings into phonemes, but whose use has spread to detecting genes in DNA sequences, identifying similarities in musical performances or scores, or classifying seismic events.We will advance our theoretical understanding of probabilistic systems like HMMs. Recent work on HMM decoding identifies properties of the most likely path, discovered by the Viterbi algorithm, but it is highly technical mathematics. Can it be simplified or expanded for HMMs important in bioinformatics? Second, we study new methods for learning and inferring in HMMs and other probabilistic structures. Robust decoding in HMMs lets us focus on finding annotations likely to be ""close"" to the true one, rather than just identifying the most probable state path in an HMM for a sequence . We will draw out these decoding algorithms, and use them in a variety of applications. Robust HMM decoding is a key need in domains from bioinformatics to acoustics.Finally, we will focus on applications both new and classical. One focus remains DNA and protein alignment, but we will spread our applications to music information retrieval, detection of recombination points in DNA and RNA sequences (with applications to finding evolutionary hotspots and recombinations in HIV sequences), and predicting the structure of biologically important molecules.Our work trains graduate students for careers in industry and academia at the intersection of some of the most interesting areas of the new information age.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
238973-2010
Name nom
Brown, Daniel
Department département
Computer Science, David R. Cheriton School of
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2013
Competition year année de concours
2010
Award amount
34000
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
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
4
Nb partie
5
Application title
Theory and applications of sequence analysis
Keyword
NSERC
Application summary
Discrete sequences arrive in scientific analysis in a variety of contexts, from biological sequences such as DNA or RNA sequences, to musical sequences such as the notes found in a score, to text sequences, such as the words of a document. For naturally-occuring sequences, what is the information that evolution or other processes has embedded in them? For man-made sequences, what patterns are imposed into the sequence, deliberately or not? Common tools are used to analyze such sequences. One tool is hidden Markov models (HMMs), invented to decode speech recordings into phonemes, but whose use has spread to detecting genes in DNA sequences, identifying similarities in musical performances or scores, or classifying seismic events.We will advance our theoretical understanding of probabilistic systems like HMMs. Recent work on HMM decoding identifies properties of the most likely path, discovered by the Viterbi algorithm, but it is highly technical mathematics. Can it be simplified or expanded for HMMs important in bioinformatics? Second, we study new methods for learning and inferring in HMMs and other probabilistic structures. Robust decoding in HMMs lets us focus on finding annotations likely to be ""close"" to the true one, rather than just identifying the most probable state path in an HMM for a sequence . We will draw out these decoding algorithms, and use them in a variety of applications. Robust HMM decoding is a key need in domains from bioinformatics to acoustics.Finally, we will focus on applications both new and classical. One focus remains DNA and protein alignment, but we will spread our applications to music information retrieval, detection of recombination points in DNA and RNA sequences (with applications to finding evolutionary hotspots and recombinations in HIV sequences), and predicting the structure of biologically important molecules.Our work trains graduate students for careers in industry and academia at the intersection of some of the most interesting areas of the new information age.