Exact and Approximate Repeats in DNA Sequences using Suffix Array and Divide & Conquer

Author Name(s):
Author Email:


Microsatellites or Simple Sequence Repeats are short motifs, for the most part 2-8 base pairs long that are repeated numerous times in genomic DNA. Here, motifs are short, repeating patterns in DNA that have an organic capacity. These SSRs are responsible for sequence-binding locations for proteins like Transcription factor. Such groupings are extremely normal over the eukaryotic genomes and are found in plenitude with variable recurrence of event. In the event that the rates of transformations at the repeat loci is observed to be high contrasted with different locales of genomic DNA it can often lead to generation of inter and intra-specific hereditary variety, and thus permit their hereditary marker exploitation. Recent evidences demonstrate the auxiliary and utilitarian essentialness of microsatellites and have consequently made it an imperative subject in contemporary research in addition to their time–proven use as an efficient molecular marker system. Taking after the transformation in sequencing advances, even the extent that non model life forms are concerned, the whole genomes can now be possibly screened utilizing bio tools to locate the presence of SSRs.


Repeats in DNA successions comprise of short arrangements or examples that repeat. These repeats can be either scattered or tandem. Blended repeats are long, less incessant and far separated while tandem rehashes are continuous events of an example that are contiguous each other. These repeats examples are either precise or there might be inclusion or deletion or substitution of a base, because of transformations, as needs be there are correct and surmised pair rehashes. Pair repeats are additionally grouped into microsatellites, mini-satellites and satellite DNA in light of the time of the repeat. Rehashes comprising of under 1 to 6 nucleotides are alluded to as microsatellites. Small scale satellites are those that have a period estimate more prominent than 6 nucleotides and satellite DNA have more noteworthy than 100 nucleotides.  Tandem repeats are identified with numerous human illnesses brought about by hereditary issue, for example, Huntington’s infection, delicate X mental impediment, ‘myotonic dystrophy’, strong decay and “Friedreichs ataxia”. These repeats additionally help in deciding the parentage and individual legacy qualities. Certain adjustments in the recurrence of these repeats can bring about tumor. Blemished preservation of examples and the perplexing structure makes it hard to distinguish tandem repeats. Also the yield gotten for a given information shifts from technique to strategy. Most tandem repeats finders create distinctive, frequently non overlapping surmising, reflecting attributes of the fundamental calculations as opposed to the genuine circulation of Tandem Repeats (TRs) in DNA sequences.

Two types of sequence repeats are –

Perfect Sequence Repeats: A exact tandem repeat is a sequence A = (B) t which is a continuous copies of two or more sequence B of length p where p ≥ 2 is repeating t times. The sequence B is called the repeating pattern of A.

Approximate Sequence Repeats: Due to gene mutation, sequence repeats in DNA generally don’t consist of perfectly repeated patterns. Each repeating unit are different from other or it may be the same and different. Since there is more than multiple way to distinguish between repeated units (e.g edit distance, hamming distance or statistical methods), multiple definitions of approx. tandem repeats exist.


  1. Sequence Repeat Searching tools

Given the considerable interest in tandem repeats, it is hardly surprising to find a rich abundance of bioinformatics tools developed for detecting and characterizing them. Two surveys have founded more than 30 tools TRF, MREPSi, Sputnik, ATR Hunter, Repeat Masker etc.


  1. B. Repeat Detection

The majority of the search tools embrace a two-stage way to deal with identifying “tandem repeats”: search and filtering. In the main stage, either one of the two sorts of algorithms is ordinarily actualized:

  1. A combinatorial search algorithm that comprehensively areas the whole sequence into subsequence’s and compares about each contiguous subsequence to recognize potential sequence repeats for all positions and all period sizes.
  2. A measurable or heuristicibasedialgorithmithat uses little section windows to look over the sequence to first identify the conceivable repetitive loci (regularly little exact repeats) before combine them to decide the more extended repeats. The runtime for the combinatorial algorithm grows exponentially, particularly when the search includes imperfect and covering repeats.


  1. Significant repeats filtering

In next step, different types of filtering techniques are utilized to recognize and remove the naturally noteworthy repeats. It can be a straightforward length channel or a more intricate execution of heuristic-based, (for example, k-mean clustering) or measurements based models. Likewise, arrangement algorithms, for example, wraparound dynamic programming or star-focused algorithm are additionally utilized to decide the imperfect repeats in view of the given insertion and deletion (indels) or mismatch with limit settings. For the vast majority of these tools, the clients are permitted to change the filtering parameters to satisfy their particular application however the announced outcomes are exceedingly delicate to these settings. In addition, distinctive developers utilize or prescribe diverse settings to identify what they consider as “biologically significant repeats”, subsequently making it troublesome for clients to comprehend their complicated impacts.


Our program can find repeats of motif length in a given range with given maximum period limitation. We have modified the algorithm proposed by Main and Lorentz to find approximate tandem repeats by introducing a tolerance factor. Further this algorithm can be improved by applying Euclidean distance or edit distance because hamming distance has many drawbacks it only calculates character to character mismatch while edit distance can calculate score based on insertion, replacement or deletion by giving weight to each type of operation. The algorithm can also be useful in DNA compression (e.g. replacing ‘xxxx’ as ‘x4’ where ‘x’ is a repeating unit) and in DNA pattern recognition. For large DNA sequences greater than 100 MB can’t be processed on simple system so parallel programming concept can enhance the memory and time efficiency of this program. Parallel programming concept can be applied easily to divide and conquer method.


[1]  Abouelhoda M.I. et al. (2004) Replacing suffix trees with enhanced suffix arrays. J. Discrete Algorithms, 2, 53–86.

[2]  Kurtz S. (1999) Reducing the space requirement of suffix trees. Softw. Pract. Exp., 29, 1149–1171.

[3]  Lim K.G. et al. (2013) Review of tandem repeat search tools: a systematic approach to evaluating algorithmic performance. Brief. Bioinf., 14, 67–81.

[4]  Madesis P. et al. (2013) Microsatellites: Evolution and contribution In: Microsatellites. Springer, pp. 1–13.[PubMed] [5]  Manber U., Myers G. (1993) Suffix arrays: a new method for on-line string searches. SIAM J. Comput., 22, 935–948.

[6]  McCreight E.M. (1976) A space-economical suffix tree construction algorithm. J. ACM (JACM), 23, 262–272.

[7]  Schlotterer C., Tautz D. (1992) Slippage synthesis of simple sequence DNA. Nucleic Acids Res., 20, 211–215.

[8]  Ukkonen E. (1995) On-line construction of suffix trees. Algorithmica, 14, 249–260.

[9]  Weiner P. (1973) Linear pattern matching algorithms. Switching and Automata Theory, 1973. SWAT'08. In: IEEE Conference Record of 14th Annual Symposium on IEEE, pp. 1–11.

[10]  Benson,G. (1999) Tandem repeats finder: a program to analyze DNA sequences. Nucleic Acids Res., 27, 573–580.

[11]  R. Pokrzywa, Application of the Burrows-Wheeler Transform for searching for tandem repeats in DNA sequences, Int. J. Bioinform. Res. Appl. vol. 5 (4) (2009) 432–446.

[12]  Merkel A, Gemmell N. Detecting microsatellites in genome data:Briefings in bioinformatics CS . VOL 9. NO 5. 355,366

[13]  Adalberto T. Castelo, Wellington Martins and Guang R. Gao. Tandem Repeat Occurrence Locator: Bioinformatics (2002) 18 (4): 634-636. doi: 10.1093/bioinformatics/18.4.634

[14]  Pamela Vinitha Eric, Kusum Rajput, Gopakumar G ,An Improved Method to Identify Exact and Approximate Tandem Repeats in DNA Sequences using Biclustering, International Journal of Computer Applications (0975 – 8887) Volume 146 – No.9, July 2016

[15]  Wexler Y, Yakhini Z, Kashi Y, et al. Finding approximate tandem repeats in genomic sequences. J Comput Biol 2005;12:928–42.

[16]  B. D. Pickett, S. M. Karlinsey, C. E. Penrod, M. J. Cormier,M. T. W. Ebbert, D. K.Shiozawa, C. J. Whipple and P. G. Ridge,SA-SSR: a suffix array-based algorithm for exhaustive and efficient SSR discovery in large genetic sequences ,Bioinformatics, 32(17), 2016, 2707–2709

[17]  Kasai, T.; Lee, G.; Arimura, H.; Arikawa, S.; Park, K. (2001). Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications. 181–192. doi:10.1007/3-540-48194- X_17. ISBN 978-3- 540-42271- 6.

[18]  Barsky, Marina; Stege, Ulrike; Thomo, Alex; Upton, Chris (2009), Suffix trees for very large genomic sequences;, CIKM Proceedings of the 18th ACM Conference on Information and Knowledge Management, New York, NY, USA: ACM.

[19]  Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (2002). The Enhanced Suffix Array and Its Applications to Genome Analysis. Algorithms in Bioinformatics. Lecture Notes in Computer Science. 2452. p. 449. doi:10.1007/3-540- 45784-4_35. ISBN 978-3- 540-44211-0.

[20]  Juha Kärkkäinen, Peter Sanders, and Stefan Burkhardt. 2006. Linear work suffix array construction. J. ACM 53, 6 (November 2006), 918-936. doi:10.1145/1217856.1217858

[21]  Tao Tao (2011-08- 24). Single Letter Codes for Nucleotides". [NCBI Learning Center]. National Center for Biotechnology Information. Retrieved 2012-03- 15.

[22]  Delgrange, O. and Rivals, E. STAR: An Algorithm to Search for Tandem Approximate Repeats. Bioinformatics, 20:2812–2820, 2004

[23]  Kolpakov, R. and Kucherov, G. Finding Approximate Repetitions under Hamming Distance. Theoret. Comput. Sci., 303, 2003.

[24]  Landau, G., Schmidt, J. and Sokol, D. An Algorithm for Approximate Tandem Repeats. J. Comput. Biol., 8(1):1–18, 2001.

[25]  Milosavljevic, A. and Jurka, J. Discovering simple DNA sequences by the algorithmic significance method. Comput. Appl. Biosci., 9(4):407–411, 1993.

[26]  Wexler Y, Yakhini Z, Kashi Y, Geiger D (2004) Finding approximate tandem repeats in genomic sequences. Proc. 8th Annual Int Conf Res Comput Mol Biol (RECOMB04) pp 223–232

[27]  Roman Kolpakov, Ghizlane Bana, Gregory Kucherov: Mreps: efficient and flexible detection of tandem repeats in DNA, Nucleic Acid Res. 2003 Jul 1; 31(13): 3672–3678.

[28]  Main M.G, Lorentz R.J :An O(nlogn) algorithm for finding all repetitions in a string, Journal of Algorithms pg. 422-32


227 total views, 1 views today

About the author: dev