The SCP and compressed domain analysis of biological sequences

We introduce the SCP - the sorted common prefix, and study some of its properties. Based on the internal representations used by a class of new compression schemes, we show how the SCP table can be constructed using an O(u+| Σ |K_max) number of comparisons on average, and O(u | Σ |) worst case, where u is the size of the sequence, | Σ | is the number of symbols, and K_max is the maximum SCP value. We describe one application of the SCP to the problem of anchor points in multiple sequence alignment.