Abstract

A weighted sequence is a string in which a set of characters may appear at each position with respective probabilities of occurrence. Weighted sequences are able to summarize poorly defined short sequences, as well as the profiles of protein families and complete chromosome sequences. Thus it is of biological and theoretical significance to design powerful algorithms on weighted sequences. A common task is to identify repetitive motifs in weighted sequences, with presence probability not less than a given threshold. We define two types of repeats in weighted sequences, called the loose repeats and the strict repeats, respectively, and then attempt to locate these repeats. Using an iterative partitioning technique, we present algorithms for computing all the loose repeats and strict repeats of every length, respectively. Each solution costs O(n2)time.

Keywords: Border check array, loose repeat, partitioning, strict repeat, structural overlap, weighted sequence