Topics in Algorithm Design

这项研究项目考察了(1)模式匹配、(2)DNA序列组装、(3)数据结构和(4)n体势场计算领域的算法设计问题。模式匹配中提出的问题涉及构造字符串和树的后缀树的有效方法，借助后缀树处理歧义符号，后缀树的外部存储算法，以及与字符串卷积计算有关的几个问题。这些研究对数字图书馆和计算生物学的广泛领域具有重要意义。随着更快的DNA测序方法的出现，迫切需要开发更好的算法来组装大量的DNA片段。对在这种序列组装中出现的几个问题进行了研究。最近，PI开发了一种很有吸引力的过程，用于将基于数据结构的算法从具有良好摊销速度的算法转换为具有匹配最坏情况速度特性的算法。该项目的另一个目标是探索该技术在与数据结构的持久性和最小生成树的动态维护相关的问题上的适用性。此外，PI还发展了d维空间中点的良好分离对分解的概念。对于n点的集合P，这包括其叶子在P中的二叉树，其内部节点以自然的方式对应于P的子集，以及节点对的列表，使得对应于每个节点的集合在几何上以适当的距离分开，并且每个不同的点对正好被节点对中的一个节点覆盖。PI利用这种分解设计了有效的算法来计算n体势场和几个相关问题。这些技巧被推广到其他问题。

This research project examines algorithm design issues in the areas of (1) Pattern Matching, (2) DNA Sequence Assembly, (3) Data Structures, and (4) Computation of n-body Potential Fields. The proposed problems in pattern matching deal with efficient methods for the construction of suffix trees of strings and trees, treatment of ambiguous symbols with the help of suffix trees, external memory algorithms for suffix trees, and several issues related to computation of convolutions of strings. These investigations are of great significance to the broad areas of Digital Libraries and Computational Biology. With the emergence of faster DNA sequencing methods, there is an immediate need to develop better algorithms for assembling large numbers of DNA fragments. Several problems that arise in such sequence assembly are investigated. Recently, the PI developed an attractive procedure for transforming data-structure-based algorithms which have good amortized speed into ones that have matching worst-case speed characteristics. Another goal of this project is to explore the applicability of this technique to problems related to persistence of data structures and dynamic maintenance of minimum spanning trees. In addition, the PI developed the concept of a well-separated pair decomposition of points in d-dimensional space. For a set P of n-points, this consists of a binary tree whose leaves are in P, with internal nodes corresponding to subsets of P in the natural way, and a list of pairs of nodes, such that the sets corresponding to each node are geometrically separated by appropriate distance, and each distinct pair of points is `covered` by exactly one of the pairs of the nodes. The PI had made use of this decomposition in designing efficient algorithms for n-body potential field computations and several related problems. These techniques are extended to other problems.