transformée de Burrows-Wheeler

La transformée de Burrows-Wheeler, couramment désignée par le sigle BWT (pour anglais : Burrows-Wheeler Transform) est un prétraitement utilisé en compression de données. Inventée par Michael Burrows et David Wheeler, elle a été publiée en 1994, à la suite de travaux précédents de Wheeler en 1983. Il ne s'agit pas d'un algorithme de compression, car aucune réduction de taille n'est effectuée. Il s'agit d'une méthode de réorganisation des données : la probabilité que des caractères identiques initialement éloignés les uns des autres se retrouvent côte à côte dans le résultat est accrue. La technique est à la base de l'algorithme de compression bzip2 qui est actuellement l'un de ceux offrant un des meilleurs taux de compression. Elle est aussi très utilisée en génomique, par exemple pour les problèmes d'alignement de lectures courtes issues des nouvelles technologies de séquençage d'ADN (ou d'ARN) ou pour des problèmes de comptage de mots (détection de répétitions).