A geometric framework for solving subsequence problems in computational biology efficiently

In this paper, we introduce the notion of a constrained Minkowski sumwhich for two (finite) point-sets P,Q R2 and a set of k inequalities Ax b is defined as the point-set (P Q)Ax b= x = p+q | P, q Q, Ax b. We show that typical subsequenceproblems from computational biology can be solved by computing a setcontaining the vertices of the convex hull of an appropriatelyconstrained Minkowski sum. We provide an algorithm for computing such a setwith running time O(N log N), where N=|P|+|Q| if k is fixed. For the special case (P Q)x1 Β, where P and Q consistof points with integer x1-coordinates whose absolute values arebounded by O(N), we even achieve a linear running time O(N). Wethereby obtain a linear running time for many subsequence problemsfrom the literature and improve upon the best known running times forsome of them.The main advantage of the presented approach is that it provides a generalframework within which a broad variety of subsequence problems canbe modeled and solved.This includes objective functions and constraintswhich are even more complexthan the ones considered before. Copyright 2007 ACM.