摘要
In this paper we are interested in the study of the combinatorial aspects related to the extension of the Burrows-Wheeler transform to a multiset of words. Such study involves the notion of suffixes and conjugates of words and is based on two different order relations, denoted by %26lt;(lex) and w, that, even if strictly connected, are quite different from the computational point of view. In particular, we introduce a method that only uses the %26lt;(lex) sorting among suffixes of a multiset of words in order to sort their conjugates according to %26lt;(omega)-order. In this study an important robe is played by Lyndon words. This strategy could be used in applications specially in the field of Bioinformatics, where for instance the advent of %26quot;next-generation%26quot; DNA sequencing technologies has meant that huge collections of DNA sequences are now commonplace.
- 出版日期2014-12