Computing Patterns in Strings

字符串是从某个字母表中提取的一系列符号，通常称为字母。《圣经》可以被认为是一个字符串，大约有200万位长，由英文字母、整数和标点符号组成；每个生物的基因组都可以被认为是一个字符串，其长度通常在数十亿位，在一个四个字母的DNA字母表(a，c，g，t)上；从太空传输的比特流是一个字符串，可能有数万亿个位长，在字母表(0，1)上。对于文学、生物或军事研究，这些字符串中的模式是基本的：某个短语在圣经中出现在哪里？基因组中重复的DNA片段如何表明帕金森氏症的易感性？某些重复出现的比特模式提供了关于电子传输的编码段的哪些线索？ 1975年，全世界只有几十名研究字符串算法的研究人员；现在肯定有数千名，这是计算机广泛用于信息存储和计算生物学的巨大热潮的结果。在过去的15年里，我的研究有两个主要主题：不确定字符串和正则性的计算。 在DNA序列中，可能不清楚给定的条目是a还是c，因此使用不确定的符号{a，c}。然后我们可以说，{a，c}与另一个符号{c，g}匹配，而该符号又与{g，t}匹配--但{a，c}肯定不匹配{g，t}！这种看似无伤大雅的困难，即匹配的不可传递性，使不确定字符串的处理变得更加困难。因此，对不确定字符串的组合理解对于开发处理它们的有效方法是必不可少的。 与普通字符串一样，对于不确定字符串，主要任务是识别/计算称为正则性的模式。例如，字符串acaaca具有句点3，因为位置i和i+3总是相同的；同时，即使acaaca不是周期性的，它仍然具有封面aca，因为aca的出现覆盖了每个位置。这些规则和其他许多规则是计算字符串中的模式的基础，这些模式为我们提供了对现实世界中的模式的理解。在DNA序列中，一个打破模式的字母可能标志着一个至关重要的基因组脆弱性或优势。 15年来，我的大部分研究都围绕这两个主题展开。使用基于数学分析的洞察力，我试图识别具有现实意义的规律性，特别是在不确定的字符串中，我试图设计方法(“算法”)来快速计算它们，即使是数十亿或数万亿的字符串长度。例如：DNA中的模式表明对特定疾病的易感性；以兆兆字节的互联网文本中指示含义或主题的术语的重合；重复出现暗示编码信息的适当的位模式。很多模式，很多应用！

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!