  In ongoing work to define a principled method for syntenic block discovery
and structuring, work based on homology-derived constraints and a
generalization of common intervals, we faced a fundamental computational
problem: how to determine quickly, among a set of indeterminate strings
(strings whose elements consist of subsets of characters), contiguous intervals
that would share a vast majority of their elements, but allow for sharing
subsets of characters subsumed by others, and also for certain elements to be
missing from certain genomes. An algorithm for this problem in the special case
of determinate strings (where each element is a single character of the
alphabet, i.e., "normal" strings) was described by Doerr et al., but its
running time would explode if generalized to indeterminate strings. In this
paper, we describe an algorithm for computing these special common intervals in
time close to that of the simpler algorithm of Doerr et al. and show that can
compute these intervals in just a couple of hours for large collections (tens
to hundreds) of bacterial genomes.
