6533b874fe1ef96bd12d61d3

RESEARCH PRODUCT

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

Antonio RestivoSabrina MantaciGiovanna RosoneMarinella Sciortino

subject

Discrete mathematicsMultisetBurrows-Wheeler transform; Data Compression; Mitochondrial genome phylogenyBurrows–Wheeler transformMultiplicity (mathematics)Mitochondrial genome phylogenyBurrows-Wheeler transformData CompressionSurjective functionConjugacy classSequence comparisonPreprocessorAlgorithmMathematicsData compression

description

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.

yearjournalcountryeditionlanguage
2005-01-01
10.1007/11496656_16http://hdl.handle.net/11568/728471