Finding LPRs in DNA sequences based on a new index - SUA

This paper proposes a new concept of repetitions, the largest pattern repetition (the LPR) and a concept of pattern unit. A lightweight index structure, namely, the succeeding unit array (the SUA) is designed based on pattern unit. The SUA decreases the space consumption efficiently and solves the space bottleneck in the search of repetitions. On the SUA all the atomic patterns which constitute the LPRs can be detected and the LPRs can be identified by connecting the same patterns. The theoretical analysis and experimental results show that both space and time complexity of the algorithms is O(n).