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 R<sup>2</sup> and a set of k inequalities Ax b is defined as the point-set (P Q)<sub>Ax b</sub>= 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)<sub>x1 Β</sub>, where P and Q consistof points with integer x<sub>1</sub>-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.

Published in:
Symposium on Computational Geometry, 310-318
Presented at:
Symposium on Computational Geometry 2007, Gyeongju, South Korea

 Record created 2008-05-13, last modified 2018-09-13

Rate this document:

Rate this document:
(Not yet reviewed)