We introduce a generalization of the Burrows-Wheeler Transform (BWT) that can be applied to a multiset of words. The extended transformation, denoted by E, is reversible, but, differently from BWT, it is also surjective. The E transformation allows to give a definition of distance between two sequences, that we apply here to the problem of the whole mitochondrial genome phylogeny. Moreover we give some consideration about compressing a set of words by using the E transformation as preprocessing.

MANTACI, S., RESTIVO, A., ROSONE, G., SCIORTINO, M. (2005). An extension of the Burrows Wheeler Transform and applications to sequence comparison and data compression. In LNCS (pp. 178-189) [10.1007/11496656_16].

An extension of the Burrows Wheeler Transform and applications to sequence comparison and data compression

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

Abstract

We introduce a generalization of the Burrows-Wheeler Transform (BWT) that can be applied to a multiset of words. The extended transformation, denoted by E, is reversible, but, differently from BWT, it is also surjective. The E transformation allows to give a definition of distance between two sequences, that we apply here to the problem of the whole mitochondrial genome phylogeny. Moreover we give some consideration about compressing a set of words by using the E transformation as preprocessing.
2005
MANTACI, S., RESTIVO, A., ROSONE, G., SCIORTINO, M. (2005). An extension of the Burrows Wheeler Transform and applications to sequence comparison and data compression. In LNCS (pp. 178-189) [10.1007/11496656_16].
File in questo prodotto:
File Dimensione Formato  
MRRS_LNCS_CPM_2005.pdf

Solo gestori archvio

Dimensione 219.66 kB
Formato Adobe PDF
219.66 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/30580
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 37
  • ???jsp.display-item.citation.isi??? 30
social impact