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

点击翻译按钮获取中文摘要

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.