Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Victoria

$19,000.00

Parameterized complexity in computational biology and cognitive psychology

EF 2006-07

Résumé
In many application areas, such as Computational Biology or Bioinformatics, there is a tremendous need for practical algorithms for NP-hard problems (i.e., problems where no polynomial time algorithm is known and most likely no such algorithm exists). Several approaches to tackle NP-hard problems exist including approximation algorithms and fixed-parameter-tractable algorithms. My expertise is in the latter one, which belongs to the area of Parameterized Complexity. We distinguish between parameterized problems which are fixed-parameter tractable and fixed-parameter intractable (i.e., hard for the class W[1]). For parameterized problems that are fixed-parameter tractable, there exist algorithms that have a polynomial-time behaviour for small parameters, that is such an algorithm may be of exponential time in the parameter, but of polynomial time in the non-parameterized input size. In Bioinformatics, I am especially interested in (1) analyzing the relationship between biological sequence data and (2) modeling the evolution of a genome. Other important applications I am investigating are in Cognitive Psychology, that is, the modeling of cognitive theories in general and understanding of human problem solving and decision making strategies in particular. Finally, my principle objectives are to design tractable algorithms for NP-hard problems and to extend the parameterized tractable algorithms design toolkit with new techniques (e.g., kernelization); the modeling of and algorithm design for genome rearrangement problems for given biological sequence data; the modeling of cognitive theories and their validation; and the investigation of human problem solving strategies when confronted with NP-hard problems.
Programme
Discovery Grants Program - Individual
Emplacement
British Columbia, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
249898-2006
Name nom
Stege, Ulrike
Department département
Computer Science
Organization id
7
Institution établissement
University of Victoria
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2006
Competition year année de concours
2006
Award amount
19000
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
1210
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Psychology
Area of application fr
Psychologie
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
Parameterized complexity in computational biology and cognitive psychology
Keyword
NA
Application summary
In many application areas, such as Computational Biology or Bioinformatics, there is a tremendous need for practical algorithms for NP-hard problems (i.e., problems where no polynomial time algorithm is known and most likely no such algorithm exists). Several approaches to tackle NP-hard problems exist including approximation algorithms and fixed-parameter-tractable algorithms. My expertise is in the latter one, which belongs to the area of Parameterized Complexity. We distinguish between parameterized problems which are fixed-parameter tractable and fixed-parameter intractable (i.e., hard for the class W[1]). For parameterized problems that are fixed-parameter tractable, there exist algorithms that have a polynomial-time behaviour for small parameters, that is such an algorithm may be of exponential time in the parameter, but of polynomial time in the non-parameterized input size. In Bioinformatics, I am especially interested in (1) analyzing the relationship between biological sequence data and (2) modeling the evolution of a genome. Other important applications I am investigating are in Cognitive Psychology, that is, the modeling of cognitive theories in general and understanding of human problem solving and decision making strategies in particular. Finally, my principle objectives are to design tractable algorithms for NP-hard problems and to extend the parameterized tractable algorithms design toolkit with new techniques (e.g., kernelization); the modeling of and algorithm design for genome rearrangement problems for given biological sequence data; the modeling of cognitive theories and their validation; and the investigation of human problem solving strategies when confronted with NP-hard problems.