Using minimal absent words to build phylogeny

作者：Chairungsee Supa****^*; Crochemore Maxime

来源：Theoretical Computer Science, 2012, 450: 109-116.

DOI：10.1016/j.tcs.2012.04.031

• Minimal absent words
• Forbidden words
• Trie of bounded depth
• String similarity
• Phylogeny construction

An absent word in a sequence is a segment that does not occur in the given sequence. It is a minimal absent word if all its proper factors occur in the given sequence.
In this paper, we review the concept of minimal absent words, which includes the notion of shortest absent word. We present an efficient method for computing the minimal absent words of bounded length using a trie of bounded depth, representing bounded length factors. This method produces the minimal absent words of given bounded length, and furthermore our technique provides a linear-time algorithm with less memory usage than previous solutions. We also present an approach, the length-weighted index, to distinguish sequences of different organisms using their minimal absent words. The results show that we can build a phylogenetic tree based on the information collected.

• 出版日期2012-9-7