Grant: Discovery Launch Supplement
McMaster University
$12,500.00
Efficient algorithms for computing regularities in strings
EF 2024-25
Résumé
In today's data-centric world enormous amounts of information and data exists which is in the form of strings that requires efficient processing to extract useful information from them. For instance, in the context of Bioinformatics, strings over the four letter DNA alphabet = {a,c,g,t} define the genome of every living species, and every instruction in a computer system is simply a string over the two letter alphabet {0,1}. To store and process strings (data) quickly, identifying regularities such as repeats, runs, covers and seeds is critical as it make processing faster for short strings and feasible for large strings. A string regularity that has recently gained interest in the research community is a cover which is a proper substring of a word such that the word can be constructed from possibly overlapping instances of it. While several notions of cover have been studied to identify regularities in strings, existing results are either computationally intensive or applicable to very few strings and are therefore not useful in practical applications.
Moreover, the development and usage of algorithms for string processing is often specific to a fixed type of the input string. The classical type of a string known as a regular string or word - is an ordered sequence of characters from a fixed finite set. Apart from this classical type, several other string types exist. For instance, the indeterminate or degenerate string that contains uncertainties at an index position such as {a,c}, meaning either a or c at position 3 in the sample string ab{a,c}aacbaba. The indeterminate string form is commonly seen in biological sequences. For instance, the National Library of Medicine which hosts the world's largest biomedical library contain strings in this form. Therefore, it is vital to develop efficient algorithms targeted for this string form.
The long-term objective of my research program is to develop efficient solutions to compute notions of covers and seeds to achieve text compression and develop efficient tools for string analysis. To achieve this, my current research program will focus on developing efficient and practical solutions for existing and new notions of covers (including approximate covers) and for computing regularities in indeterminate strings for the fundamental task of pattern matching. The software and libraries developed will be made publicly available facilitating the use of covers. Moreover, the pattern matching algorithms on indeterminate strings will enable us to develop code to process data better and mine useful information from it. It will also aid in the study of Bioinformatics (for instance, to study biological sequences and protein to protein interactions). Finally, the HQP trained in this program (3 Ph.D and 4 UG) will serve the current Canadian job market need for folks proficient in programming and algorithms.
Programme
Discovery Launch Supplement
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
DGECR-2024-00010
Name nom
Mhaskar, Neerja
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
12500
Program id
DGECR
Program name en
Discovery Launch Supplement
Program name fr
Supplément Tremplin vers la découverte
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
801
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
Computer software
Area of application fr
Logiciel
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
Efficient algorithms for computing regularities in strings
Keywords
alogrithms; data structures; strings; indeterminate strings; periodicites; bioinformatics; cover; pattern matching; v-order
Application summary
In today's data-centric world enormous amounts of information and data exists which is in the form of strings that requires efficient processing to extract useful information from them. For instance, in the context of Bioinformatics, strings over the four letter DNA alphabet = {a,c,g,t} define the genome of every living species, and every instruction in a computer system is simply a string over the two letter alphabet {0,1}. To store and process strings (data) quickly, identifying regularities such as repeats, runs, covers and seeds is critical as it make processing faster for short strings and feasible for large strings. A string regularity that has recently gained interest in the research community is a cover which is a proper substring of a word such that the word can be constructed from possibly overlapping instances of it. While several notions of cover have been studied to identify regularities in strings, existing results are either computationally intensive or applicable to very few strings and are therefore not useful in practical applications.
Moreover, the development and usage of algorithms for string processing is often specific to a fixed type of the input string. The classical type of a string known as a regular string or word - is an ordered sequence of characters from a fixed finite set. Apart from this classical type, several other string types exist. For instance, the indeterminate or degenerate string that contains uncertainties at an index position such as {a,c}, meaning either a or c at position 3 in the sample string ab{a,c}aacbaba. The indeterminate string form is commonly seen in biological sequences. For instance, the National Library of Medicine which hosts the world's largest biomedical library contain strings in this form. Therefore, it is vital to develop efficient algorithms targeted for this string form.
The long-term objective of my research program is to develop efficient solutions to compute notions of covers and seeds to achieve text compression and develop efficient tools for string analysis. To achieve this, my current research program will focus on developing efficient and practical solutions for existing and new notions of covers (including approximate covers) and for computing regularities in indeterminate strings for the fundamental task of pattern matching. The software and libraries developed will be made publicly available facilitating the use of covers. Moreover, the pattern matching algorithms on indeterminate strings will enable us to develop code to process data better and mine useful information from it. It will also aid in the study of Bioinformatics (for instance, to study biological sequences and protein to protein interactions). Finally, the HQP trained in this program (3 Ph.D and 4 UG) will serve the current Canadian job market need for folks proficient in programming and algorithms.