Microsatellites are short sequences repeated in tandem in a genome, where the unit is generally from 2 to 6 base pairs (bp). These genomic regions tend to rapidly accumulate mutations in the form of duplication and deletion of repeat units, due to specific molecular mechanisms such as replication slippage, unequal crossing-over, unequal sister chromatide exchange and slipped-strand mis-pairing. Subsequent point mutation will also occur during DNA replication, repair, or recombination. The elevated length polymorphism (in base pairs) level makes the microsatellites appropriate markers for estimating within-population genetic diversity, which is an important indicator in biodiversity science.

Traditionally, microsatellites loci discovery involved long and costly molecular biology experiments using magnetic beads for enrichment in specific repeats, followed by cloning, clone screening and sequencing. The level of polymorphism in the discovered loci is then assessed by PCR amplification from several individual of a population using primers specific for conserved regions flanking the microsatellite loci, followed by length estimation in a capillary-based or acrylamide gel electrophoresis instrument. Depending on the flanking regions mutation level, the primers may amplify successfully in genomes of related species of the same genus, or even in more distantly related genera.

With the advent of genome sequencing projects, many bioinformatics tools have been developed for mining available sequence data for presence of microsatellite loci. These tools have methodological bias, and mining one set of sequences with different algorithms commonly results in widely different results (detected loci). In all case, they represent a useful, fast and low-cost alternative for discovering novel microsatellites loci in a genome. A few of these bioinformatics tools are presented here.

Table 1 Non-exhaustive list of bioinformatic algorithms and pipelines available for detecting tandem repeat sites from genomic sequence data; updated from Sharma et al 2007¹⁾ and Lerat 2009²⁾. WARNING: The table is still in construction, any inaccuracy can be reported to the QCBS team.

Abadjian 1994 and La Rota et al. 2005⁴⁸⁾ Sputnik uses a recursive algorithm and the performance depends on the recursion depth of the program. Sputnik reads through the entire sequence, assumes the existence of a repeat at every position, compares subsequent nucleotides and applies a simple scoring rule. If the resulting score rises above a preset threshold, the region along with its position and score is written out. Score is determined by the length of the repeat and the number of errors. Each nucleotide that matches the value predicted (by assuming a repeat) adds to the score. Each “error” subtracts from the score. When an error is encountered, the three possible kinds of errors (mismatch, insertion and deletion) are assumed and recursive calls to the comparison routine are made. If the resulting score from one of these is above the cutoff threshold, it is returned and the best of three pursued.

Sagot and Myers 1998⁴⁹⁾ It is an exhaustive search, but with a pre-filtering using a heuristic. It uses a general combinatorial framework of “consensus repeat” and uses of some heuristic filtering steps to avoid exponential increase in time complexity. The algorithm exhaustively searches for all possible consensus models whose edit distance to the real repeated units is no bigger than an upper bound. The algorithm works by extending prefix models. The first step is a filter that eliminates all regions whose probability of containing a satellite is less than one in a certain threshold (?), when percentage of sequence variation between units is 10%. The second part realizes an exhaustive exploration of the space of all possible models for the repeating units present in the sequence.

Rigoustos et al 1998⁵⁰⁾ Is a heuristic variation on TRF algorithm. It is a model less algorithm that replaces the TRF contiguous k-tuples with patterns of not necessarily contiguous k characters. The first scanning step detects potential elementary patterns, using the heuristics that the number of equi-spaced patterns reported is larger in TR regions than elsewhere in the sequence. The second step is a convolution phase, it is a verification step where elementary patterns are combined into larger patterns and false positives are discarded using a scoring system.

Benson 1999⁵¹⁾ It was originally designed to search for long tandem repeats. TRF is based on the alignment procedure and k-tuples. TRF uses a probabilistic algorithm that includes a “detection step” to identify the candidate repeats (seeds of miminum of 5 bp) and an “analysis” step, according to statistically-founded criteria to filter the candidate repeats.

Landau et al 2001⁵²⁾ The algorithm finds all approximate single repeats within a sequence. Considers two criterions of similarity: the Hamming distance (k mismatches) and the edit distance (k differences). In each iteration i, the input string is divided into substrings. Each substring is searched individually for all repeats that span its centre character.

Kurtz et al 2001⁵³⁾ The algorithm uses two different distance models: the Hamming distance model and the edit distance model. It then assesses the significance of a repeat by computing its E-value, i.e. the number of repeats of the same length or longer and with the same number of errors or fewer that one would expect to find in a random DNA of the same length.

Temnykh et al 2001⁵⁴⁾ The script uses regular expressions to locate SSR patterns in sequence files. In a second step, it eliminates redundancy by locating candidate sites to original sequence using BLAST search.

Hauth and Joseph 2002⁵⁵⁾ The algorithm both locates and characterizes TR regions. Three main tasks are performed: 1) isolate a tandem repeat by determining its period and its approximate sequence location; 2) determine the pattern associated with a region period; 3) characterize the region using the pattern. As in TRF⁵⁶⁾, the algorithm uses k-length substrings in a sequence by finding recurring distances between identical substrings. The ComplexTR differs from TRF in that a statistical model is not used to locate interesting periods, but a simple and accurate filter. In the first step, a distance arrays D, parallel to S is constructed to record a distance d between identical occurrences of k-length substrings (termed words). The algorithm requires at least five identical d occurrences to be present in a run. ComplexTR uses word and distances similarities to determine significant periods within a region. The general procedure for the second step (construct region base pattern) is to select a segment of sequence corresponding to all or a portion of a copy, to align the segment to several copies and to for a pattern using the consensus. This constitutes the region based pattern. The third step (characterize using region pattern) uses wraparound dynamic programming to handle regular expressions un the context of TR identifications. The final alignment is displayed as a series of copies, each representing a pattern occurrence in S, and a consensus copy is formed.

Castelo et al 2002⁵⁷⁾ and Martins et al. 2006⁵⁸⁾ The algorithm uses the dictionary approach to find tandem repeats of pre-selected motifs. Find all occurrences from a list of patterns in a text string (the Aho–Corasick algorithm). At a mismatch character, it uses the failure links to continue to search without having to re-sample characters in the text. It uses “repeat buffer” operation to avoid missing repeats or counting the same site multiple times. Reads and write are done in constant time

Wexler et al 2004 or Wexler et al 2005⁵⁹⁾ The algorithm is heuristic search originally designed to search for long tandem repeats. First, the screening phase identifies substrings that have an unusually high probability of being an ATR using three similarity criteria. Second, the verification phase determines which of these candidates are in fact ATRs of the desired type.

Thiel et al 2003⁶⁰⁾ The algorithm is not described

Kolpakov et al 2003⁶¹⁾ The algorithm is a mixed combinatorial/heuristic paradigm. First an exhaustive combinatorial algorithm finds all approximate tandem repeats. Those repeats are then submitted to a heuristic treatment in order to obtain more biologically relevant representation of the repeats. This heuristic step includes trimming edges, computing the best period and merging, filtering out statistically expected repeats, gathering the results. The user specifies a resolution parameter that determines the ‘fuzziness’ of found repeats instead of introducing a scoring function and specifying a threshold score value for found repeats.

Parisi et al 2003⁶²⁾ The algorithm is a dynamic programming procedure originally designed to search for long tandem repeats. The general strategy is the following: (a) Instead of studying the whole sequence we examine only the tracts (interesting zones) that we consider to be the more promising ones. (b) Instead of studying all possible consensus words we examine only the words that we consider to be the more promising ones. Detailed steps: 1) First using a local alignment (autoalignment) procedure; 2) Second, by group in suitable clusters all the autoalignments obtained in phase 1, by putting in the same cluster all the autoalignments whose augmented extensions are not disjoint.

Sreenu et al 2003⁶³⁾ Scans a nucleotide sequence for the presence of perfect simple sequence repeats from motifs of 1 to 10 bp long.

Warburton et al 2004⁶⁴⁾ Algorithm not known

Krishnan and Tang 2004⁶⁵⁾ It is an exhaustive search. The algorithm takes a definition of tandem repeat that uses the Hamming distance measure, and provably finds all tandem repeats. The definition is parameterized by a mismatch ratio p which allows for more mismatches in longer tandem repeats (and fewer in shorter), thereby avoiding the problems of a fixed mismatch count. Additionally, the algorithm uses a filtering algorithm that prunes the resultant exhaustive set to a smaller one with fewer redundancies. The different algorithms are parallel (can independently search for tandem repeats for different pattern lengths k) and well suited for Beowulf-class clusters.

Sharma et al. 2004⁶⁶⁾ The algorithm uses the following steps: 1) Input a DNA sequence of length n. 2) Compute the power spectrum, S( f ), and the spectral average, Š, of the entire sequence. 3) Identify all peaks with S(fi)/ Š > T (the threshold, here chosen to be 4). For each frequency fi so identified, there are potential repeats of length Ni = 1/fi. 4) For each of these, compute the Pm( j ) = S(fi)/ Š in a sliding window of length m centered on position j in the sequence. Regions containing the repeat of length Ni can be identified directly as those where Pm( j ) exceeds the threshold. 5) Since both the repeat length, Ni, and its location are known, an exact method (step 6) is used to identify the repeat units. 6) Consider all Ni-mers in the repeat region and identify those occurring most frequently by local alignment. This automatically makes it possible to allow for insertions and deletions to any desired level.

Delgrange and Rivals 2004⁶⁷⁾ The algorithm detects all significant Approximate Tandem Repeats (ATR) of a given motif, where significance is assessed using the Minimum Description Length (MDL) criterion. MDL provides an absolute measure of the significance of an ATR independently of the motif. It evaluates how many mutations are allowed in an ATR when compared to an ETR of the best possible length. The STAR algorithm needs no threshold value and optimally locates ATR of any input motif with respect to the MDL criterion.

Bilgen et al 2004⁶⁸⁾ Is a useful algorithm for expressed sequences. There are two different algorithms implemented in two modules. The first module searches for exact and compound motifs. It searches for Sn, a string of repeated units in a DNA sequence wn- S1 = w1 [i1, j1] symbolizes the S1 starting with the i1-th and ending with the j1-th bases of the DNA sequence w1. The distance between i1 and j1 will therefore be equal to m1 × r1 where m1 and r1 refer to a type of DNA motif length and the number of repeats in S1 string of each w of a fixed length, respectively. When applicable, strings in a sequence of w are referred to as S1, S2, S3 . . . Sn for each consecutive string in a sequence w. The distance between S1 and S2 is referred to as d1, the distance between S2 and S3 is d2 and so on till Sn, dn- . The second module that searches for inexact and compound motifs with STRING algorithm (Parisi). Overall, program goes as follows: (i) searches the user defined organism (s) and/or keywords (organs, cell lines, tissue types or development stages) analyzing the whole data set provided in a data folder; (ii) isolates simple and non-simple (compound, imperfect and extended compound) tandem repeats by determining their type, lengths, and sequence location in a given DNA strings within DNA sequences; (iii) characterizes the repeats containing sequences based on the user defined parameters/ options, and; (iv) displays the results according to the user’s parameters/options.

Thurston and Field 2005⁶⁹⁾ No published description of the algorithm could be found. According to the online access, regular expression (regex), multipass or iterative search engines can be used.

de Riddera at al 2006⁷⁰⁾ Is a combination of straightforward FA technology combined with a flavour of Moore machine technology. It uses regular expressions.

Mayer 2010⁷¹⁾ Uses the alignment score as an optimality criterion to decide whether to extend a satellite up or downstream; is able to find alternative alignments with different units for the same satellite.

Anwar and Khan 2006⁷²⁾ Uses dictionary approach to find simple sequence repeats of pre-selected motifs.

Boeva et al 2006⁷³⁾ The algorithm is based on calculation of the repeat’ statistical significance, and identifies the length of the repeated unit and the number of repetitions. It consider only the repeated structures whose number of copies is integer and greater than two. Since algorithm does not search for tandem repeats with period size less than 3, it does not detect poly-A or TATA-like sequences.

Du et al 2007⁷⁴⁾ The optimized moving window spectral analysis uses Fourier spectrogram, is a text-free digital signal processing based method. The moving window spectral analysis procedure produces the spectrogram at each frequency k and location n in the location-frequency plane. Therefore, the weight vector W can be set dependent on the spectrum at the frequency k and location n. If it shows the periodic components as highlighted regions in the spectrogram in the location-frequency plane, then from the coordinates (n, k) of the regions, it can obtain the information of both the periods and locations of DNA repeats.

Mudunuri et al 2007⁷⁵⁾ It is a simple string-matching algorithm that scans the entire sequence using sliding window approach and reports the results in a single run. Is a two-step procedure: (a) identification of microsatellite nucleation sites (b) extension of the nucleation sites on both sides. IMEx progressively scans for nucleation sites starting from the longest repeat unit. The repeating motif at every iteration can harbor up to ‘k’ number of point mutations (substitutions or indels of nucleotides) and the user can set a value for ‘k’ between 0 and m where m = repeat motif size.

Kofler et al 2007⁷⁶⁾ The programs contain two main modules: an SSR search module, which supports five different SSR search modes and a module for SSR-statistics, notably for mismatch frequency and compound microsatellite analysis. A nucleotide at position i is tested for identity with the nucleotide at position i + t, where t is the motif length (1–6). Upon identity i is increased i = i + 1 until no further identity can be found.

Faircloth 2008⁷⁷⁾ It uses regular expression pattern matching within each DNA sequence to locate microsatellite arrays within user-selected repeat classes. Is used to locate all microsatellite repeats fitting these designations. DNA sequences are first scanned in the 5'–3' orientation. The program then takes a second pass through the complement of the sequence in the 3'–5'orientation.

Otto et al 2008⁷⁸⁾ It is a pipeline that is based on similarity searches, the interpretation of sequence landscapes (SL), the assembly of clustered sequences and in-house Perl scripts. First, all reads are compared to each other with BLAST, with a word size of 8 and an e-value cut-off of 10-20, or with NUCMER tool, with a word size of 11. Each result is pre-processed by joining overlapping hits and by deleting self-hits. For each read, an SL is constructed by counting how often each base of the read is part of a hit with another read. Generate the graph using external tools. The minimal length that an alignment must have to enter into the analysis was defined as l. Runs with different values for l can be performed.

Jorda and Kajava 2009⁷⁹⁾ Mainly designed for amino acid repeats. Based on clustering of lengths between identical short strings by using a K-means algorithm and on the idea that in a tandem repeat region, the most frequently occurred length between identical SSs should be equal to the repeat length. Therefore, detection of regions of an analyzed sequence where certain lengths between identical SSs have anomalously high occurrence may lead to the localization of the tandem repeats. Steps are as follow: 1) Short string probes and K-means clustering (Use K-means algorithm for unsupervised classification) 2) Establishment of tandem repeat lengths 3) Contiguity filtering, results in identification of hypothetical repeats 4) Extension and bridging of runs 5) Similarity filtering using a build-in program based on “center-star algorithm”, CLUSTALW and MUSCLE.

Pokrzywa and Polanski 2010⁸⁰⁾ It is an efficient data compression algorithm based on the idea of backward search with the Burrows–Wheeler Transform (BWT) algorithm. It allows listing all occurrences of exact tandem repeats in a given string of length n in O(n log n) time. It then uses the efficient string indexing structure by Ferragina and Manzini for searching for the occurrences of so called rearmost tandem repeats that are then used to list the locations of the desire preferred tandem repeats, namely, the maximal tandem repeats of the primitive motif.

Meglecz et al 2010⁸¹⁾ The algorithm takes the following steps: 1) Sequence cleaning and microsatellite detection (Sort according to sequence tags, trims vector and adaptors sequences). 2) Sequence similarity detection (Is time consuming, is meant to remove redundancy, and sequences that are part of a repetitive region of the genome). 3) Iterative primer design using Primer3. Iterations (a) from designing primers only for perfect microsatellites with no short repeats in the flanking region till allowing multiple target microsatellites, short repetitions and homopolymers in the amplified region (b) produce primer pairs with PCR products in different size ranges. 4) BLASTs selected sequences to Genbank to detect serious contaminations or mixing up samples.