Grant: Discovery Grants Program - Individual
University of New Brunswick
$15,000.00
Algorithms for comparing biological graph structures
FY 2008-09
Summary
Finding meaning in biological data typically requires a search for common patterns. Finding features that are common to or distinguish sets of biological patterns helps us to determine the function of features, classify the structures, and make hypotheses for future experimentation. However, we must find these features by analyzing large amounts of complex data, so we need innovative computational techniques for comparing this data to extract relevant features.
Biological structure data includes both the 2-dimensional and 3-dimensional structures of molecules and the network structures formed by the various types of molecular interactions in the cell. Both have important functional properties that can be found by using information about similarities between structures, and linking preserved features to other common characteristics. Since the information about molecular structures and interaction networks is very complex and difficult to compute with, advanced techniques for their comparison need to be developed. This research will find new computational methods for finding these similarities, and also define appropriate models for measuring similarity. These models will be developed using knowledge about what types of similarity are relevant for the underlying biological data. Since these comparison problems are intractable in general, specific restrictions need to be determined that will make efficient algorithms possible; which of these restrictions are both needed and relevant will also be investigated. Being able to find these patterns will help decipher the underlying structures and networks, make good hypotheses about biological function, and enable inferences to be transferred between organisms. This research will also discover limitations on computational techniques for these problems.
Program
Discovery Grants Program - Individual
Recipient
Location
New Brunswick, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
204923-2008
Name nom
Evans, Patricia
Department département
Computer Science, Faculty of
Organization id
75
Institution établissement
University of New Brunswick
Province en
New Brunswick
Province fr
Nouveau-Brunswick
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2008
Competition year année de concours
2008
Award amount
15000
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
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
Algorithms for comparing biological graph structures
Keyword
NA
Application summary
Finding meaning in biological data typically requires a search for common patterns. Finding features that are common to or distinguish sets of biological patterns helps us to determine the function of features, classify the structures, and make hypotheses for future experimentation. However, we must find these features by analyzing large amounts of complex data, so we need innovative computational techniques for comparing this data to extract relevant features.
Biological structure data includes both the 2-dimensional and 3-dimensional structures of molecules and the network structures formed by the various types of molecular interactions in the cell. Both have important functional properties that can be found by using information about similarities between structures, and linking preserved features to other common characteristics. Since the information about molecular structures and interaction networks is very complex and difficult to compute with, advanced techniques for their comparison need to be developed. This research will find new computational methods for finding these similarities, and also define appropriate models for measuring similarity. These models will be developed using knowledge about what types of similarity are relevant for the underlying biological data. Since these comparison problems are intractable in general, specific restrictions need to be determined that will make efficient algorithms possible; which of these restrictions are both needed and relevant will also be investigated. Being able to find these patterns will help decipher the underlying structures and networks, make good hypotheses about biological function, and enable inferences to be transferred between organisms. This research will also discover limitations on computational techniques for these problems.