Grant: Discovery Grants Program - Individual
McMaster University
$25,000.00
Improved algorithms on strings
EF 2008-09
Résumé
I conduct research into methods (algorithms) for processing sequences of letters called strings -- objects so simple that there seems to be no need of "algorithms"! But, first of all, strings are ubiquitous: a text file, a computer program (millions of letters), a book (in English or Chinese), the human genome (3 billion letters), one day's e-mail traffic (trillions of letters). Secondly, efficient processing of strings is essential: repeating substrings in a genome may be of great biological/genetic significance, phrases may need to be identified/changed in a text file or computer program, books may need to be searched for significant phrases, e-mail traffic may need to be searched for undesirable messages (spam).
For 18 years I have been designing such algorithms. Current and future research focusses on three main areas:
(1) Using recent insights into the nature of "regularities" in strings, I seek new methods to efficiently compute repeating substrings -- with applications particularly to computational biology, data mining and data compression. Essentially I seek a more precise mathematical understanding of periodicity in strings.
(2) The "suffix array" is a specialized data structure used to improve the efficiency of string algorithms. I seek new efficient algorithms that use suffix arrays, again with frequent application to computational biology and many other areas.
(3) In many problems that arise in practice, it may be necessary to process strings that contain "indeterminate" (not fully defined) entries. I seek faster more effective algorithms for doing pattern-matching and other operations on these indeterminate strings.
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
8180-2007
Name nom
Smyth, William
Department département
Computing and Software
Organization id
27
Institution établissement
McMaster University
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2008
Competition year année de concours
2007
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
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
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
2
Nb partie
5
Application title
Improved algorithms on strings
Keyword
NA
Application summary
I conduct research into methods (algorithms) for processing sequences of letters called strings -- objects so simple that there seems to be no need of "algorithms"! But, first of all, strings are ubiquitous: a text file, a computer program (millions of letters), a book (in English or Chinese), the human genome (3 billion letters), one day's e-mail traffic (trillions of letters). Secondly, efficient processing of strings is essential: repeating substrings in a genome may be of great biological/genetic significance, phrases may need to be identified/changed in a text file or computer program, books may need to be searched for significant phrases, e-mail traffic may need to be searched for undesirable messages (spam).
For 18 years I have been designing such algorithms. Current and future research focusses on three main areas:
(1) Using recent insights into the nature of "regularities" in strings, I seek new methods to efficiently compute repeating substrings -- with applications particularly to computational biology, data mining and data compression. Essentially I seek a more precise mathematical understanding of periodicity in strings.
(2) The "suffix array" is a specialized data structure used to improve the efficiency of string algorithms. I seek new efficient algorithms that use suffix arrays, again with frequent application to computational biology and many other areas.
(3) In many problems that arise in practice, it may be necessary to process strings that contain "indeterminate" (not fully defined) entries. I seek faster more effective algorithms for doing pattern-matching and other operations on these indeterminate strings.