Lecture 1.6

Read mapping

Learning objectives

After this lecture, you should be able to do the following.

Construct the Burrows-Wheeler transform of a short string, explain why it compresses, and trace backward search over the FM-index.

  1. Define the Burrows-Wheeler transform as the last column of the sorted rotations of the reference.
  2. Define the FM-index as that transform paired with its rank and count tables.
  3. Explain why sorting the suffixes groups their preceding characters, so the transform holds long runs of one character and compresses to near the size of the packed genome, resolving the suffix array’s memory problem.
  4. Explain the rank property of the transform: the \(k\)-th occurrence of a character in the last column is the \(k\)-th occurrence of that character in the first column, because every row is sorted.
  5. Trace backward search over the FM-index: starting from the last character of a query, narrow the row range one character at a time with the LF-mapping, and read the final range as every position where the query occurs.
  6. Construct the Burrows-Wheeler transform of a short string by taking, for each sorted suffix, the character immediately before it, wrapping around so the character before the first position is the sentinel.
  7. Use the LF-mapping, \(\text{new row} = C[\text{char}] + \text{rank}\), to step from a row to the position of its preceding character in sorted order without storing the first column.

Differentiate the three indexing strategies by what each trades away, and select one for a stated genome size, memory budget, and read count.

  1. Differentiate linear scan, the suffix array, and the FM-index by the speed and memory each trades away.
  2. Select the method that fits a given genome size, memory budget, and read count.

Explain what read mapping asks for that a database search does not, and why the reference is indexed once.

  1. Explain how read mapping differs from database search: many reads placed on one reference for speed and position, not one query ranked against a database by significance.
  2. Explain why mapping billions of reads makes indexing the reference once the decisive move, and why running Smith-Waterman or BLAST per read does not scale.

Build a suffix array from a short string, search it for a query, and account for the memory it costs.

  1. Explain why a suffix array costs several times the size of the packed genome in memory, and why the array must be searchable as stored, not merely small, to work as an index.
  2. Explain why the sentinel $ is appended to the reference before indexing: it makes every suffix unique, marks the end of the text, and sorts before every other character.
  3. Trace a binary search over a sorted suffix array to find the rows that begin with a query.
  4. Find every occurrence of a repeated pattern by locating its first and last rows in the suffix array with two binary searches, and explain why scanning outward from one match brings back the linear-scan cost.
  5. Build the suffix array of a short string by listing every suffix, sorting them, and reading off their starting positions.
Back to top