Negative Information for Building Phylogenies
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.
Rights & PermissionsPrintExport