Recent Patents on DNA & Gene Sequences (DIscontinued)

Christian Bronner  
Institute of Genetics and Molecular and Cellular Biology
University of Strasboug
France

Back

Negative Information for Building Phylogenies

Author(s): Supaporn Chairungsee, Maxime Crochemore.

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.

Order Reprints Order Eprints Rights & PermissionsPrintExport

Article Details

VOLUME: 7
ISSUE: 2
Year: 2013
Page: [128 - 136]
Pages: 9
DOI: 10.2174/1872215611307020007
Price: $100