PriSeT: Efficient De Novo Primer Discovery

Marie Hoffmann; Michael T. Monaghan; Knut Reinert

The Primer Search Tool 4 by Tusnady et al. (2005) uses a dynamic programming approach inspired by Kaempke et al. (2001) . When combining candidate sequences Kaempke et al. (2001) make use of the sequence overlap and re-use computations of the shared substring. The online tool allows the upload of files containing multiple references, but produces errors when header lines contain special characters or sequences contain ambiguous one-letter encodings. A file of 114 KB sequences took 40 seconds to be processed including network traffic 5 . It outputs primer pairs scored by chemical fitness, but does not optimize towards coverage or amplicon variation. PRIMEX (Lexa & Valle, 2004) is intended to provide querying as an online service. The tool performs internally a lookup of k-mers derived from the query string in a prepared library and allows for mismatches. Unfortunately, PRIMEX is currently not available and it is not capable of discovering new primer sequences 6 . One of the few standalone tools is FastPCR (Kalendar et al., 2017) . It supports a variety of PCR protocols and chemical checks. It first computes a hash table with k-mers grouped together by overlap into so called k-tuples with k being 7, 9, or 12 nt long. The derivation of these k-tuples is not described. In a second step, FastPCR uses a sliding window approach to search for matches between k-tuples and reference sequences. Upon match, individual k-tuples are extended in both directions. FastPCR has no preference for frequent k-mers -it is designed to work on single genomes. The authors are not aware of a primer discovery tool suitable for metabarcoding experiments where the aim is a high taxonomic coverage and barcode variation and the input is a directory or source file composed of thousands of reference sequences. Before we explain in detail the data structures and algorithm to solve the problem of primer discovery, we give definitions of some concepts that are essential to make our approach time-efficient.