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.