A geometric framework for solving subsequence problems in computational biology efficiently
Thorsten Bernholt, Friedrich Eisenbrand, Thomas Hofmeister · 2007
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.