6533b856fe1ef96bd12b1d30
RESEARCH PRODUCT
SORTING CONJUGATES AND SUFFIXES OF WORDS IN A MULTISET
Marinella SciortinoSilvia BonomoGiovanna RosoneSabrina MantaciAntonio Restivosubject
Lyndon words; Burrows-Wheeler transform; Extended Burrows-Wheeler transform; Circular words; Conjugates; Suffixes; SortingSuffixesMultisetTheoretical computer sciencePoint (typography)Burrows–Wheeler transformSettore INF/01 - InformaticaSortingcircular wordExtension (predicate logic)Lyndon wordsBurrows-Wheeler transformLyndon wordField (computer science)ConjugatesconjugateComputer Science (miscellaneous)sortOrder (group theory)suffixeArithmeticextended Burrows-Wheeler transformCircular wordssortingMathematicsdescription
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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2014-12-01 |