Efficient Computation of Discriminative Absent Words for String Collections

Minimal absent words (MAWs) provide a compact and combinatorially meaningful representation of a string or of a collection of strings, and have been successfully used in alignment-free sequence comparison and classification methods. Among MAW-based approaches, the set of discriminative absent words (DAWs) for two string collections isolates those minimal absent words of one collection that actually occur as a factor in the other, thus capturing the shortest witnesses of structural differences. In this paper, we present a linear-time algorithm for computing the set of discriminative absent words for two collections of strings. We detect DAWs through a single scan of LCP-based arrays, without explicitly con- structing the full sets of minimal absent words of the two string collections. The algorithm naturally extends to the circular setting, preserving linear time and space complexity with respect to the total input size. This yields a conceptually simple and efficient framework for large scale sequence comparison.