Exact and Approximation Pattern Matching, and Network Routing

本提案的主要重点是“模式匹配”，即在通常称为“文本”的较大主体中确定称为“模式”的对象。 模式可能是一个DNA序列，文本可能是一个DNA序列的（大）集合. 虽然人们已经很好地理解了如何找到对象的精确匹配，但找到对象的类似实例还没有被很好地理解，或者至少不知道如何有效地找到它们。 此外，很自然地假设，被匹配的对象之间的相似性越大，该任务可以被逐步地更有效地执行。 但总的来说，实现这一目标仍然存在问题。 该项目的目的是开发其效率随着相似性的增加而提高的方法。 激励问题包括已经提到的DNA匹配，文本中的单词或短语匹配，以及图像中的对象匹配。 这个建议的第二个重点是网络交换机的研究;更具体地说，设计发送（路由）消息的方法和设计，以促进这种路由。

The main focus of this proposal is on "pattern matching", the identifying of an object, called the "pattern", in a larger body, often called the `text". The pattern might be a DNA sequence and the text a (large) collection of DNA sequences. While it is fairly well understood how to find exact matches of an object, finding similar instances of an object is not as well understood, or at least it is not known how to find them nearly as efficiently. Further, it is natural to suppose that this task can be carried out progressively more efficiently the greater the similarity between the objects being matched. But, by and large, achieving this remains problematic. The aim of this project is to develop methods whose efficiency improves in tandem with increased similarity. Motivating problems include the already mentioned DNA matching, matching of words or phrases in bodies of text, and matching of objects in images. A secondary focus for this proposal is the study of network switches; more specifically, the devising of methods for sending (routing) messages and designs for facilitating such routings.