Theoretically Speaking Seminar Series: "New Approaches to Covering a String" by Neerja Mhaskar

Abstract:

A string is simply an ordered sequence of letters chosen from a finite set called
the Alphabet. For example, strings on the four-letter DNA alphabet {a, c, g, t} define the
genome of every living species. A long string over a relatively small alphabet (for example, a
DNA sequence is several gigabytes long) will have interesting properties known as
“regularities”: long repeating patterns, periodicities, tandem repeats, and others. Study of these regularities is important due to their applications in numerous and diverse areas:
bioinformatics, text searching, data compression, language processing, and many more.
Studying periodicities in strings, in particular, is of fundamental importance. However, very
few strings are periodic over their entire length. Thus, in order to extend the idea’s utility,
various kinds of approximate periodicity have been proposed: cover or quasiperiodicity, kcover, enhanced cover, and α-partial cover, the most general yet discovered. In this talk we
describe this avenue of research, discuss some very recent new ideas and approaches, and
outline promising paths for future development.