Pattern Matching in Vision and Molecular Biology

理论计算机科学的作用之一是为各种应用领域发展一种算法理论。本研究是由计算机视觉和分子生物学中的一些实际问题所推动的。计算机视觉的主要激励问题是搜索航空或卫星照片。在本研究中，该问题被抽象为几个“纯”子问题-局部误差，缩放和旋转-并寻求有效的解决方案。然后尝试综合子问题的解，得到一种通用算法。解决方案的工具涉及到产生更一般的算法和数据结构问题的技术。这项研究还解决了来自分子生物学的问题。近年来，一些研究人员提出了高效的动态规划方法来确定RNA二级结构。新的信息表明，二级结构比原先认为的更为复杂。研究人员正在调查这个问题现在是否是NP困难的。这个问题的答案将决定是否寻求有效的算法或有效的近似解。

One of the roles theoretical computer science is to develop an algorithmic theory for various application domains. This research is motivated by some practical problems in computer vision and molecular biology. The main motivating problem in computer vision is that of searching aerial or satellite photographs. In this investigation, the problem is abstracted to several "pure" subproblems - local errors, scaling, and rotations - and efficient solutions are sought. The research then attempts to synthesize the subproblem solutions and obtain a general algorithm. The tools for the solution involve techniques that give rise to more general algorithmic and data structure problems. This research also addresses problems stemming from molecular biology. Recently, several researchers presented efficient dynamic programming methods for determining the RNA secondary structure. New information shows that the secondary structure is more involved than originally thought. The researchers are investigating whether the problem is now NP- hard. The answer to that question will determine if efficient algorithms or efficient approximations to its solution will be sought.