An extension of the Burrows Wheeler Transform and applications to sequence comparison and data compression
- Autori: MANTACI, S; RESTIVO, A; ROSONE, G; SCIORTINO, M
- Anno di pubblicazione: 2005
- Tipologia: Capitolo o Saggio
- OA Link: http://hdl.handle.net/10447/30580
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.