We present a method for segmenting qualitative sequences, according to a type of composition criteria whose definition and evaluation are founded on the notion of predictors and additive prediction. Given a set of predictors, a partition of a sequence can be precisely evaluated. We present a language for the declaration of predictors. One of the problems is to optimize the partition of a sequence into a given number of segments. The other problem is to obtain a suitable number of segments for the partitioning of the sequence. We present an algorithm which, given a sequence and a set of predictors, can successively compute the optimal partitions of the sequence for growing numbers of segments. The time- and space-complexity of the algorithm are linear for the length of sequence and number of predictors. Experimentally, the computed partitions are highly stable regard to the number of segments, and we present an application of this approach to the determination of the origins of replication of bacterial chromosomes.