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 <_lex and ≺_ω, that, even if strictly connected, are quite different from the computational point of view. In particular, we introduce a method that only uses the <_lex sorting among suffixes of a multiset of words in order to sort their conjugates according to ≺_ω-order. In this study an important role is played by Lyndon words. This strategy could be used in applications specially in the field of Bioinformatics, where for instance the advent of "next-generation" DNA sequencing technologies has meant that huge collections of DNA sequences are now commonplace.
|Autori:||Bonomo S; Mantaci S; Restivo A; Rosone G; Sciortino M|
|Titolo:||Sorting conjugates and Suffixes of Words in a Multiset|
|Anno del prodotto:||2014|
|Digital Object Identifier (DOI):||10.1142/S0129054114400309|
|Appare nelle tipologie:||1.1 Articolo in rivista|