PriSeT: Efficient De Novo Primer Discovery

Marie Hoffmann; Michael T. Monaghan; Knut Reinert

When computing the k-mer frequency with varying values for k, one notices that for a specific position i in a reference R, it is likely that we will yield many k-mers of different lengths which successfully passed the frequency filter and start at the same index. In fact there are up to κ max − κ min + 1 many k-mers for the same location index. We introduce the TKMerID data type stored in a uint64_t, which primarily encodes the longest k-mer found at a specific text position (see Figure 3 ). We use the two bit encoding scheme shown in Table 3 . The reduction to the four basic nucleotides is justified by the observation that substrings containing ambiguous nucleotides are meaningless, since a single mismatch between primer and template may lead to an amplification failure. The two-bit encoding scheme has the property that taking the complement of the integer produces its DNA complement. We use this property to implement a k-linear time annealing test.