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}！这个看似无关紧要的困难，即匹配的非传递性，使得处理不确定字符串变得更加困难。因此，对不确定字符串的组合理解对于开发处理不确定字符串的有效方法至关重要。******对于不确定字符串，与普通字符串一样，主要任务是识别/计算称为规则性的模式。例如，字符串acaacaa的周期是3，因为位置i和i+3总是相同的；同时，即使acaacaca不是周期性的，它仍然有一个覆盖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!*****