SORTING CONJUGATES AND SUFFIXES OF WORDS IN A MULTISET

Research output: Contribution to journalArticle

5 Citations (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.
Original languageEnglish
Pages (from-to)1161-1175
Number of pages15
JournalInternational Journal of Foundations of Computer Science
Volume25
Publication statusPublished - 2014

    Fingerprint

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)

Cite this