Computing Patterns in Strings

点击翻译按钮获取中文摘要

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!*****