SORTING CONJUGATES AND SUFFIXES OF WORDS IN A MULTISET

Risultato della ricerca: Article

5 Citazioni (Scopus)

Abstract

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.
Lingua originaleEnglish
pagine (da-a)1161-1175
Numero di pagine15
RivistaInternational Journal of Foundations of Computer Science
Volume25
Stato di pubblicazionePublished - 2014

    Fingerprint

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)

Cita questo