Skip to content

Latest commit

 

History

History
13 lines (11 loc) · 898 Bytes

Assignment_3.md

File metadata and controls

13 lines (11 loc) · 898 Bytes
Raw

Assignment 3

Task 1: Burrows-Wheeler Transform (BWT) (2 point)

Learning objective: Learn how Burrows-Wheeler Transform and FM-index work and how they can be used to perform sequence matching and alignment extremely fast.

Given the Borrows-Wheeler transformed string 'ACTCA$TA'.

  1. Construct the FM index
  2. Show how many times the pattern 'CA' occurs in original string using the FM index and LF(i) (Last-to-First) function
  3. Does the pattern 'CATTA' appear in original string?

Additional reading

  • Practice session recording from spring 2021: link
  • An entertaining video explaining how Burrows-Wheeler Transform works: link.
  • Explantation of the FM index from Ben Langmead: link