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.

Bonomo, S., Mantaci, S., Restivo, A., Rosone, G., Sciortino, M. (2014). SORTING CONJUGATES AND SUFFIXES OF WORDS IN A MULTISET. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 25(08), 1161-1175 [10.1142/S0129054114400309].

SORTING CONJUGATES AND SUFFIXES OF WORDS IN A MULTISET

MANTACI, Sabrina;RESTIVO, Antonio;ROSONE, Giovanna;SCIORTINO, Marinella
2014-01-01

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
2014
Bonomo, S., Mantaci, S., Restivo, A., Rosone, G., Sciortino, M. (2014). SORTING CONJUGATES AND SUFFIXES OF WORDS IN A MULTISET. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 25(08), 1161-1175 [10.1142/S0129054114400309].
File in questo prodotto:
File Dimensione Formato  
BMRRS_IJFCS2014.pdf

Solo gestori archvio

Descrizione: Articolo
Dimensione 276.3 kB
Formato Adobe PDF
276.3 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10447/124392
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 14
  • ???jsp.display-item.citation.isi??? 9
social impact