Topics in Algorithm Design

算法设计主题

• 批准号: 9508545
• 负责人: S. Rao Kosaraju
• 金额: $ 28.75万
• 依托单位: Johns Hopkins University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1995
• 资助国家: 美国
• 起止时间: 1995-08-01 至 1999-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9508545&HistoricalAwards=false
• 关键词: Topics; Algorithm; Design

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.

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