CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Fast algorithms for finding disjoint subsequences with extremal densities

Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Bioinformatik (Chalmers) ; Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers)) ; Anders Bergkvist
16th International Symposium on Algorithms and Computation ISAAC 2005, Lecture Notes in Computer Science Vol. 3827 (2005), p. 714-723.
[Konferensbidrag, refereegranskat]

We derive fast algorithms for the problem of finding, on the real line, a prescribed number of intervals of maximum total length that contain at most some prescribed number of points from a given point set. Basically this is a typical dynamic programming problem, however, for input sizes much bigger than the two parameters we can improve the obvious time bound by selecting a restricted set of candidate intervals that are sufficient to build some optimal solution. As a byproduct, the same idea improves an algorithm for a similar subsequence problem recently brought up by Chen, Lu and Tang at IWBRA 2005. The problems are motivated by the search for significant patterns in certain biological data. While the algorithmic idea for the asymptotic worst-case bound is rather evident, we also consider further heuristics to save even more time in typical instances. One of them, described in this paper, leads to an apparently open problem of computational geometry flavour (where we are seeking a subquadratic algorithm) which might be interesting in itself.

Nyckelord: data mining, holes in data, sparse dynamic programming

Denna post skapades 2006-08-25. Senast ändrad 2015-02-11.
CPL Pubid: 9566