A1.6

Question 1 Single best answer Level 1 1 point

Every rotation of a reference that ends in a sentinel is written as one row of a matrix, and the rows are then sorted lexicographically. Which string read from that matrix is the Burrows-Wheeler transform?

  1. The first column, read from the top row to the bottom row
  2. The last column, read from the top row to the bottom row
  3. The last row, read from the leftmost character to the rightmost
  4. The starting position of each sorted row, read from the top row to the bottom row

Question 2 Single best answer Level 2 1 point

A linear scan finds a seed by comparing it at every position of the genome. Why does building an index instead pay off when hundreds of millions of reads have to be mapped?

  1. The index is rebuilt for each read, and building it costs less than comparing that read at every position
  2. A scan cannot report how many times a read occurs without a second pass over the genome
  3. A scan rereads the whole genome for every read, while the index is built once and then skips most of the text
  4. The index compresses the genome, so the reference fits in memory and the search no longer touches the disk

Question 3 Single best answer Level 2 1 point

A sentinel character that occurs nowhere else in the reference is appended to it before its rotations are sorted. What does appending it accomplish for the construction?

  1. It occurs once, so no two rotations are equal and the sorted order is unique
  2. It separates the repeated characters so that run-length encoding can find the runs
  3. It marks the position in the reference where a read is expected to align
  4. It pads every rotation to the same length so that the rows can be compared

Question 4 Single best answer Level 2 1 point

In the sorted list of the suffixes of a reference, every occurrence of a seed lies in one unbroken block of rows. Why does sorting put them there?

  1. Every occurrence begins a suffix that has the seed as its prefix, and sorting groups strings that share a prefix
  2. The sentinel sorts before every other character, which gathers the matching suffixes near the top of the list
  3. The suffix array lists the starting positions in increasing order, which keeps the matching suffixes adjacent
  4. The occurrences of a seed lie near each other in the reference, so their suffixes stay near each other

Question 5 Single best answer Level 2 1 point

A run-length encoder shrinks the Burrows-Wheeler transform of a genome much more than it shrinks the genome itself. What does the transform do to make that possible?

  1. Sorting the rotations replaces each repeated substring with a pointer to its first occurrence in the text
  2. Sorting the rotations drops the characters that repeat, leaving a transform shorter than the text
  3. Sorting the rotations groups positions with the same following context, so the characters before them fall into long runs
  4. Sorting the rotations puts the characters of the genome in sorted order, giving one run per distinct character

Question 6 Single best answer Level 2 1 point

In the sorted rotation matrix, the \(k\)-th occurrence of a character in the last column and the \(k\)-th occurrence of that character in the first column come from the same rotation. Why do the two orders agree?

  1. The sentinel row sits at the top of the matrix, which keeps the first and last columns aligned row by row
  2. The rows starting with the character and the rows ending with it are ordered by the same following context
  3. Sorting the matrix leaves the last column sorted too, so a character occurs in the same order in both columns
  4. Both columns hold the same characters, so their occurrences line up in the order the characters appear in the reference

Question 7 Single best answer Level 3 1 point

A sentinel that sorts before every base is appended to the reference tactac, and all seven rotations of the resulting text are sorted lexicographically. The last character of the transform is the sentinel. What are the six characters before it?

  1. AACCTT
  2. CAATTC
  3. CTTAAC
  4. TACTAC

Question 8 Single best answer Level 3 1 point

The last column of a sorted rotation matrix holds, from row 0 down, the characters A, G, T, T, A, C and the sentinel, and the count table gives \(C[A] = 1\), \(C[C] = 3\), \(C[G] = 4\) and \(C[T] = 5\). Using \(\mathrm{LF}(i) = C[L[i]] + \operatorname{occ}(L[i], i)\), which row does row 4 map to?

  1. Row 1
  2. Row 3
  3. Row 5
  4. Row 2

Question 9 Single best answer Level 3 1 point

The last column of an eight-row index holds, from row 0 down, T, C, the sentinel, T, A, A, G and G, and the count table gives \(C[A] = 1\), \(C[C] = 3\), \(C[G] = 4\) and \(C[T] = 6\). Backward search for the read AGT starts with rows 0 to 7 and updates the range with \(\mathit{top} \leftarrow C[c] + \operatorname{occ}(c, \mathit{top})\) and \(\mathit{bottom} \leftarrow C[c] + \operatorname{occ}(c, \mathit{bottom} + 1) - 1\). Where does the search end, and how often does the read occur?

  1. The range is empty, so the read does not occur
  2. Row 4 only, so the read occurs once
  3. Rows 1 to 2, so the read occurs twice
  4. Rows 4 to 5, so the read occurs twice

Question 10 Single best answer Level 4 1 point

A lab maps 400 million reads against a 3.1 Gb reference and needs two references resident at the same time on a machine with 16 GB of memory. For one reference, the packed sequence is under 1 GB, a suffix array of it is about 12 GB, and an FM-index of it is about 2 GB. Which method fits the job?

  1. The linear scan, since the packed reference is the only thing it has to hold in memory
  2. The suffix array, since it gives the fastest search once it has been built
  3. The FM-index, since two of them fit in memory and each search skips most of the text
  4. The gzipped reference, since it is the smallest of the four to keep in memory
Back to top