Locating all tandem repeat families in a sequence

We present a new data structure called the BSCP (block sorted common prefix), and its tree representation, called the BSCP tree. We also introduce the notion of PTR family - a biologically motivated description and representation of the tandem repetitions hi a sequence. The PTR family implicitly encodes each distinct primitive tandem repeat in the sequence as its part. Based on the BSCP tree, we describe a method to locate all the primitive tandem repeat families in an input sequence T. The proposed method requires average space and time complexity in O(u), where u = |T|.