Chapter-3.5.1-BWT-and-LF-mapping

# MOST WIDELY USED FOR DNA

Burrows-Wheeler transformation & LF mapping

• Most widely used tools:
  • bwa
  • bowtie

Burrows-Wheeler transformation

• This text is uded to do text compression
• Reversible premutation used originally in compressin.
• Database sequence T = acaacg$

Why BWT is useful for compression?

• once BWT(T) is built,everything else is discarded.

• First column of BWM can be derived by sotring BWT(T).

• Characters will tend to cluster togeter:

  • BWT(T) gc$aaac -> compression -> gc$3ac

• How can we recreate T using BWT(T)?

  • using LF mapping.

• Property taht makes BWT(T) Reversible is "LF mapping".

  • ith occurence of a charactr in the LAst Column is the same text occurences as the ith occurence in the first column

• To recreate T from BWT(T), repeatedly apply rule: T = BWT[LF(i) + T; i = LF(i)]