Speed Testing
The time complexity of the algorithm is O(n2). To test the speed in practice, we use arbitrarily generated DNA and protein sequences. We ran our software on a PC with Pentium 4 3.4G CPU and 1GB memory, the result is shown in Table 3. We can see that for long DNA and protein sequences, our software can get the result in short time. For example, if the length of the sequence is 10000, it takes about 10.8 seconds and 26.9 seconds for DNA sequences and protein sequences, respectively. In some real applications, the length of sequences could be much longer than 10000. In this case, one can cut the long sequence into several short pieces and find out the repeated regions for each piece. If a region covers two pieces, then we can re-cut that segment to get that region.
Table 3  Results for the speed test of LocRepeat
Length  2000  4000  6000  8000  10000
DNA  0.5s  2.2s  4.8s  7.0s  10.8s
PROTEIN  1.1s  4.3s  10.0s  17.7s  26.9s