Circular Pattern Discovery.

Given a text or database T, the circular pattern discovery (CPD) problem is to identify 'interesting' circular patterns in T. Here, no specific input pattern is provided, and what is interesting is typically defined in terms of constraints in the search. We propose two algorithms for the CPD problem. The first algorithm uses suffix trees and suffix links to solve the exact CPD problem in O(m₂²N) time, where m₂ is the maximum length of the circular patterns and N is the total length of the sequence database. The second algorithm uses suffix arrays to solve the more challenging approximate CPD (ACPD) problem in O(km₂²N²) worst case, and O(km₂²N²) on average, where k is the maximum allowed error(s). By exploiting the nature of the ACPD problem, the complexity is reduced to O(m₂²N²) time in the worst case, and O(m₂²N) on average. [ABSTRACT FROM AUTHOR]