Abstract

An absent word (also called a forbidden word or an unword in other contexts) in a sequence is a segment that does not appear in the given sequence. It is a minimal absent word if all its proper factors occur in the given sequence. In this article, we review the concept of minimal absent words, which includes the notion of shortest absent words but is much stronger. We present an efficient method for computing the minimal absent words of bounded length for DNA sequence using a Trie of bounded depth, representing bounded length factors. This method outputs the whole set of minimal absent words and furthermore our technique provides a linear-time algorithm with less memory usage than previous solutions. We also present an approach to distinguish sequences of different organisms using their minimal absent words. Our solution applies a length-weighted index to discriminate sequences and the results show that we can build phylogenetic tree based on the patent collected information.

Keywords: Forbidden words, indexing, minimal absent words, phylogeny construction, string similarity, trie of bounded depth.