Exact Tandem Repeats using Suffix Array and Longest Common Prefix

Author Name(s): Dr Raju Bhukya, Naveen.I, Rohan Gupta, Anurag.K, Achyuth.A, Taruni
Author Email: rrajunitw@gmail.com


Tandem Repeats (TRs) are the repeats which occur in a chromosome, while a pattern of 1 or more nucleotides (A, C, G, T) is repeated more than one time and the repetitions are continuous. Repeating patterns also referred to as motifs or base patterns, can be of various lengths. There is a complete of 25 linkage groups or chromosomes in the Zebrafish genome. The proposed algorithm reported exact tandem repeats with a motif length of at least three 3 with the help of an algorithm that uses a suffix array and longest common prefix. An overall of 119,909 repeats, with a base pattern of at least 3 nucleotides were detected. A massive number of repeats with a base period of 18, 24, 27 30 had been detected. The algorithm produces better results as compared to the existing results in terms of a number of repeats.


Genomes are comprised of nucleotides which are represented by A, C, G, T. The zebra fish genome is large, it is approximately 1.7 billion bases lengthy with a complete of 25 linkage groups [1], that is more or less half the dimensions of the human genome. Single nucleotide polymorphisms rate inside the zebra fish genome is approximately one in 2 hundred bases, while in human beings it is one in keeping with 1,000 bases[2]. Depending on the length of repeating motif DNA repeats are classified into subtypes. Patterns or motifs of length less than 10 are known as microsatellites or short tandem repeats (STR) [3] and repeats of longer lengths for example 1000 nucleotides are referred to as minisatellites [4]. Zebra fish are studied as a model vertebrate organism which is an animal of a large group distinguished by the possession of a backbone with an early embryonic development which is similar to the development of a human[5]. As compared to Zebra fish genome this is 1.7 billion bases lengthy, the human genome is 3.2 billion bases long and this equates to 3 million variations throughout the human genome and eight million variations across the zebrafish genome. These patterns are characteristic of protein-coding sequences. Duplication happens in large regions of a genome and this results in the
repetition of a pattern. For example, if a pattern ACG is repeating 10times then the resulting sequence will beACGACGACGACGACGACGACGACGACGACG this can be written as(ACG)10 where ACG is called as the base pattern and 10 is the copy number means the pattern is repeating 10 times [6]. To detect and report these highly degenerate sequence motifs from genomic sequence collections we need more efficient tools. Thus, it is very important to identify and characterize repeating sequences in both the genome assembly and genomic sequences including weak or decentralized repeating sequences. For detecting repeats various computational approaches are developed. These approaches have some limitations which can be categorized into deterministic and probabilistic. Other than these, there are three main groups [7]. The first group detects and reports repeats indirectly and it is based on the alignment of matrices. The limitation of these algorithms is time complexity with the best algorithm having a time complexity of O(N2logN)[7]. The second group detects the repeats without any alignment. This kind of algorithms either assume some kind of similarity between possible repeats or they require some kind of input from the user. For example, the input may consist of predefined threshold on similarity, the number of nucleotides ( A, C, G, T ) between repeats, motif lengths[7].


We proposed a method based on Suffix Array and Longest common prefix array techniques to find motif length, frequency and stating position of that motif. Suffix array can always be constructed in linear time O(n) for any given sequence, where n represents the sequence length. Construction of LCPA from Suffix array also takes linear time O(n) overall time complexity of the proposed algorithm is O(n). The proposed algorithm (ESL) is compared with the existing algorithm (SWA) in terms of number of repeats. The proposed technique shows better performance when compared with the existing techniques. In this technique we had found the repeats length from 3 to 50 in Zebrafish chromosomes. Our future work is to apply the algorithm for all the species with better complexity.

434 total views, 1 views today

Download PDF File

About the author: admin