Generic placeholder image

Recent Patents on DNA & Gene Sequences


ISSN (Print): 1872-2156
ISSN (Online): 2212-3431

Negative Information for Building Phylogenies

Author(s): Supaporn Chairungsee and Maxime Crochemore

Volume 7 , Issue 2 , 2013

Page: [128 - 136] Pages: 9

DOI: 10.2174/1872215611307020007

Price: $65


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 & Permissions Print Export Cite as
© 2022 Bentham Science Publishers | Privacy Policy