3S: A Fast and Exhaustive STR Search Algorithm

Short tandem repeats (STRs) are contiguous repetitions of motifs (1 and 6nts) over DNA sequence and considered as important genetic markers. The design of a computational method for accurately and efficiently identifying STRs across whole genome sequences will be useful. We observe that atomic motifs, which we refer to as seeds, are the fundamental building blocks of STRs. We develop an algorithm that determines whether a motif is atomic as it moves through a sequence, and examines its non-cyclic redundancy and non-enclosing qualities to determine whether it can continue to repeat as a tandem pattern. The method is known as STR Seed Selection (3S) since its goal is to locate the seeds of STRs and track their sustainability. The approach extracts all the non-redundant STRs in linear time and using only a single scan of the sequence. Experiments show that 3S outperforms state-of-the-art exhaustive approaches in extracting STRs from genome-wide sequences.