Grant: Discovery Grants Program - Individual
McMaster University
$23,000.00
Computing Patterns in Strings
FY 2018-19
Summary
A string is a sequence of symbols, usually called letters, drawn from some alphabet. The Bible can be thought of as a string, about two million positions long, on an alphabet of English letters, integers and punctuation symbols; the genome of every living thing can be thought of as a string, whose length is usually in the billions, on a four-letter DNA alphabet (a,c,g,t); a bit stream transmitted from space is a string, perhaps trillions of positions long, on alphabet (0,1). For literary, biological or military research, the patterns in these strings are fundamental: Where does a certain phrase recur in the Bible? How do repeated DNA segments in the genome indicate susceptibility to Parkinson's disease? What clues do certain recurring bit patterns provide about coded segments of the electronic transmission?*In 1975 there were a few dozen researchers in string algorithms round the world; now there are surely many thousands, a result of the widespread use of computers for information storage and a huge upsurge in computational biology. For the last 15 years there have been two main themes of my research: indeterminate strings and the computation of regularities.*In a DNA sequence it may be unclear whether a given entry is a or c, and so the indeterminate symbol {a,c} is used. We could then say that {a,c} matches another symbol {c,g} which in turn matches {g,t} -- but {a,c} certainly does not match {g,t}! This seemingly innocuous difficulty, the nontransitivity of matching, makes the processing of indeterminate strings much more difficult. Thus a combinatorial understanding of indeterminate strings becomes essential to the development of efficient methods for their processing.*With indeterminate strings, as with ordinary ones, the main task is the recognition/computation of patterns called regularities. For example, the string acaacaa has period 3, since positions i and i+3 are always the same; at the same time, even though acaacaca is not periodic, it nevertheless has a cover aca, since an occurrence of aca covers every position. These regularities, and many others, are fundamental to the calculation of the patterns in strings that provide us with the understanding we seek about patterns in the real world. In a DNA sequence, a single letter that breaks the pattern can mark a crucial genomic vulnerability or advantage.*For 15 years, much of my research has embraced these two themes. Using insights based on mathematical analysis, I seek to identify regularities, especially in indeterminate strings, that have real-world significance, and I try to design methods (""algorithms"") to compute them quickly, even for string lengths in the billions or trillions. For example: patterns in DNA that indicate susceptibility to specific diseases; coincidence of terminology in terabytes of Internet text that indicate meaning or topic; recurring appropriate bit patterns that suggest a coded message. Many patterns, many applications!*
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2017-04691
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
2018
Competition year année de concours
2017
Award amount
23000
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
802
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
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
Computing Patterns in Strings
Keyword
NSERC
Application summary
A string is a sequence of symbols, usually called letters, drawn from some alphabet. The Bible can be thought of as a string, about two million positions long, on an alphabet of English letters, integers and punctuation symbols; the genome of every living thing can be thought of as a string, whose length is usually in the billions, on a four-letter DNA alphabet (a,c,g,t); a bit stream transmitted from space is a string, perhaps trillions of positions long, on alphabet (0,1). For literary, biological or military research, the patterns in these strings are fundamental: Where does a certain phrase recur in the Bible? How do repeated DNA segments in the genome indicate susceptibility to Parkinson's disease? What clues do certain recurring bit patterns provide about coded segments of the electronic transmission?*In 1975 there were a few dozen researchers in string algorithms round the world; now there are surely many thousands, a result of the widespread use of computers for information storage and a huge upsurge in computational biology. For the last 15 years there have been two main themes of my research: indeterminate strings and the computation of regularities.*In a DNA sequence it may be unclear whether a given entry is a or c, and so the indeterminate symbol {a,c} is used. We could then say that {a,c} matches another symbol {c,g} which in turn matches {g,t} -- but {a,c} certainly does not match {g,t}! This seemingly innocuous difficulty, the nontransitivity of matching, makes the processing of indeterminate strings much more difficult. Thus a combinatorial understanding of indeterminate strings becomes essential to the development of efficient methods for their processing.*With indeterminate strings, as with ordinary ones, the main task is the recognition/computation of patterns called regularities. For example, the string acaacaa has period 3, since positions i and i+3 are always the same; at the same time, even though acaacaca is not periodic, it nevertheless has a cover aca, since an occurrence of aca covers every position. These regularities, and many others, are fundamental to the calculation of the patterns in strings that provide us with the understanding we seek about patterns in the real world. In a DNA sequence, a single letter that breaks the pattern can mark a crucial genomic vulnerability or advantage.*For 15 years, much of my research has embraced these two themes. Using insights based on mathematical analysis, I seek to identify regularities, especially in indeterminate strings, that have real-world significance, and I try to design methods (""algorithms"") to compute them quickly, even for string lengths in the billions or trillions. For example: patterns in DNA that indicate susceptibility to specific diseases; coincidence of terminology in terabytes of Internet text that indicate meaning or topic; recurring appropriate bit patterns that suggest a coded message. Many patterns, many applications!*