Grant: Discovery Grants Program - Individual
McMaster University
$36,000.00
Patterns in Strings & Applications
EF 2024-25
Résumé
A string is a sequence of symbols, usually called letters, drawn from some alphabet. Thus the Bible is a string, about two million positions long, on an alphabet of English letters (lower case and upper case), integers, and punctuation symbols; the genome of every living thing can be represented by a string, of a length 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 an electronic transmission?
In 1975 there were only a few dozen researchers in string algorithms round the world; now there are tens of thousands, a result of widespread computer use and a huge corresponding upsurge in computational biology. Accordingly, over the last quarter-century, at least 150 of my publications have dealt with two main themes -- indeterminate strings and the computation of regularities.
For example, in a DNA sequence it may be unclear whether a given entry is a (adenine) or c (cytosine), and so the indeterminate symbol {a,c} is used. We could then say that {a,c} "matches" 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 processing of indeterminate strings much more difficult. Thus a combinatorial understanding of indeterminate strings becomes essential to finding efficient methods for their processing.
With indeterminate strings, as with ordinary ones, a central task is the recognition/computation of patterns called regularities. For example, the string acaacaa has period 3, since positions i and i+3 always match; on the other hand, while acaacaca does not have period 3, it nevertheless has cover aca, since occurrences of aca match all positions. These regularities, and many others, are fundamental to the calculation of the patterns in strings that provide us with an understanding of their significance in the real world. In a DNA sequence, a single letter that breaks the pattern can mark a crucial genomic vulnerability or advantage.
Going forward, based on mathematical analysis, I continue and expand my work, seeking to identify regularities, especially in indeterminate strings, that have real world significance, and to discover 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; similar terminology over terabytes of Internet text that identify meaning or an important topic; recurring bit patterns that suggest a coded message. A few of many practical applications of this research.
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
RGPIN-2024-05921
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
2024
Competition year année de concours
2024
Award amount
36000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
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
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Patterns in Strings & Applications
Keywords
string; regular/indeterminate string; data structure; algorithm; bioinformatics; dna/protein sequences; discrete mathematics; pattern/cover/border; maximal/approximate cover; periodicity
Application summary
A string is a sequence of symbols, usually called letters, drawn from some alphabet. Thus the Bible is a string, about two million positions long, on an alphabet of English letters (lower case and upper case), integers, and punctuation symbols; the genome of every living thing can be represented by a string, of a length 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 an electronic transmission?
In 1975 there were only a few dozen researchers in string algorithms round the world; now there are tens of thousands, a result of widespread computer use and a huge corresponding upsurge in computational biology. Accordingly, over the last quarter-century, at least 150 of my publications have dealt with two main themes -- indeterminate strings and the computation of regularities.
For example, in a DNA sequence it may be unclear whether a given entry is a (adenine) or c (cytosine), and so the indeterminate symbol {a,c} is used. We could then say that {a,c} "matches" 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 processing of indeterminate strings much more difficult. Thus a combinatorial understanding of indeterminate strings becomes essential to finding efficient methods for their processing.
With indeterminate strings, as with ordinary ones, a central task is the recognition/computation of patterns called regularities. For example, the string acaacaa has period 3, since positions i and i+3 always match; on the other hand, while acaacaca does not have period 3, it nevertheless has cover aca, since occurrences of aca match all positions. These regularities, and many others, are fundamental to the calculation of the patterns in strings that provide us with an understanding of their significance in the real world. In a DNA sequence, a single letter that breaks the pattern can mark a crucial genomic vulnerability or advantage.
Going forward, based on mathematical analysis, I continue and expand my work, seeking to identify regularities, especially in indeterminate strings, that have real world significance, and to discover 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; similar terminology over terabytes of Internet text that identify meaning or an important topic; recurring bit patterns that suggest a coded message. A few of many practical applications of this research.