NSF Young Investigator: Algorithms for Molecular Biology, Optimal Triangulation, Minimum Spanning Trees, and Geometric Optimization

该项目致力于算法设计和分析的研究，其动机是计算机科学的许多其他领域的应用。 非常相似的问题往往会出现在非常不同的应用中。 例如，与某些生物序列比较问题相关的“最小权重子序列问题”也出现在页面布局算法、VLSI设计理论和计算几何中。 零件搬运机的运动规划也可以用自动机理论的语言来表达，并与编码理论中的一些问题密切相关。 因此，理论计算机科学研究可能最适合按解决方案的风格和技术进行分组，而不是按它所解决的问题进行分组。 沿着传统的顺序算法，还有并行（PRAM模型）算法的工作。 分子生物学中的算法变得越来越重要，因为已知的DNA序列信息的数量的增长速度超过了计算机处理它的能力。直到最近，生物算法的大多数工作者都是数学家和生物学家。 他们的研究确定并形式化了这一领域的许多问题，但他们开发的算法往往是动态规划的简单应用。 这项工作将更复杂的技术应用于这些问题，从而导致一个或两个数量级的加速。 也将有正在进行的研究问题的计算最小生成树，无论是图形和平面点集。 主要的重点是动态版本的最小生成树等问题。 这导致了更一般的离线算法的研究，并查询对MST的影响，对未来的潜在更新的数据结构。

This project addresses research in the design and analysis of algorithms, motivated by applications in many other areas of computer science. Very similar problems tend to arise in very different applications. As an example, the ``least weight subsequence problem'' which is studied in connection with certain biological sequence comparison problems has also appeared in page layout algorithms, VLSI design theory, and computational geometry. Also work in motion planning for parts handlers may be couched in the language of automata theory, and is closely related to some problems in coding theory. As a consequence, theoretical computer science research might be most appropriately grouped by solution style and technique, rather than by the problems that it solves. Along with traditional sequential algorithms, there is work with parallel (PRAM model) algorithms. Algorithms in molecular biology have become increasingly important, as the quantity of DNA sequence information known has been growing more quickly than the ability of computers to process it. Until recently, most workers in biological algorithms were mathematicians and biologists. Their research identified and formalized many problems in this area, but the algorithms they developed tended to be simple applications of dynamic programming. This work applies more sophisticated techniques to these problems, resulting in speedups of one or two orders of magnitude. There will also be ongoing research on problems of computing minimum spanning trees, both for graphs and for planar point sets. The main focus is on dynamic versions of such problems as the minimum spanning tree. This has led to a more general study of off-line algorithms, and to data structures for querying the effects on the MST on potential future update.