PRUNER: algorithms for finding monad patterns in DNA sequences

We present new algorithms for discovering monad patterns in DNA sequences. Monad patterns are of the form (l,d)-k, where l is the length of the pattern, d is the maximum number of mismatches allowed, and k is the minimum number of times the pattern is repeated in the given sample. The time-complexity of some of the best known algorithms to date is O(nt²l^d|Σ|^d2/), where t is the number of input sequences, and n is the length of each input sequence. The first algorithm that we present takes O(n²t²l^d2/|Σ|^d2/) and space O(ntl^d2/|Σ|^d2/), and the second algorithm takes O(n³t³l^d2/|Σ|^d2/ time using O(l^d2/|Σ|^d2/) space. In practice, our algorithms have much better performance provided the d/l ratio is small.