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). |
(from crpit.com)
