Faster Algorithms for Finding Missing Patterns

Li, S.C.

The missing pattern pair problem, introduced in (Inenaga, Kivioja & M�akinen 2004), was motivated by the need for optimization in Polymerase Chain Reaction, a technique commonly used in bioinformatics. The problem is to find a pair of patterns of the shortest total length within a string of length n, where the two patterns do not occur within a distance ? anywhere in the string. Inenaga et al. (Inenaga et al. 2004) gave an algorithm with time complexity O(min{?n log n, n2}) to solve this problem. In this paper we propose an algorithm of time complexity O(min{?n log n, n3/2}), improving on the quadratic bound part of the earlier algorithm. We also design a simple algorithm of time complexity O(n2 ? log2 n), which is O(n log2 n) if ? = _(n).

Cite as: Li, S.C. (2006). Faster Algorithms for Finding Missing Patterns. In Proc. Twelfth Computing: The Australasian Theory Symposium (CATS2006), Hobart, Australia. CRPIT, 51. Gudmundsson, J. and Jay, B., Eds. ACS. 107-111.

(from crpit.com) (local if available)