Worked solutionOne step at a time
Build the index once
Take every 32-letter word in the chromosome, keep its start position, and sort the words alphabetically. For chr21 that is 40,087,038 entries (windows containing N are skipped).
Search by halving
Open the middle entry and compare it with your read. If the read comes later alphabetically, the whole first half can be thrown away; otherwise the second half. Repeat.
Count the halvings
After k looks, n / 2ᵏ entries are left. You are done when that reaches 1, so k = ⌈log₂ n⌉.
Answer: A, 32 looks
log₂ 3,100,000,000 = 31.5, so 32 looks. A genome 77 times bigger costs only log₂ 77 ≈ 6.3 more halvings. That is why read aligners such as BWA and Bowtie are built on sorted indexes (the suffix array and the FM-index) rather than on scanning.
What the computation showedReal chromosome, real timings
The reel's code loads human chromosome 21 from the hg38 assembly (46,709,983 positions, 40,088,619 of them A, C, G or T) and builds the index with numpy.
- Each 32-letter word is packed into one 64-bit number (2 bits per letter), and all 40,087,038 are sorted.
- The read shown, ATTATTTTTGTAAAATAAAAAAATCTTATTTT, occurs once, at position 37,875,223. The logged binary search took 26 looks, the worst case for this index.
- On a laptop, Python's built-in text search needs about 97 ms to scan the whole chromosome for a missing read; a lookup in the sorted index (numpy searchsorted) takes about 3.2 µs.
Wrong answersWhy each one is tempting
| Pick | What went wrong |
|---|---|
| B · 2,000 | Scaled the looks linearly with genome size, like a scan. |
| C · 77 | Used the size ratio itself as the answer. |
| D · 26 million | Thought of a scan, not a halving search. |
Follow-ups an interviewer asks nextTry these before opening them
The index stores a 64-bit word and a position per entry. How big is it for the whole genome?
About 3 billion entries × 16 bytes ≈ 48 GB. That is why real aligners use the FM-index (a compressed Burrows–Wheeler transform), which fits the human genome in a few gigabytes and still answers in a number of steps proportional to the read length.
Your read has one sequencing error. What happens?
An exact search fails. Aligners look up short exact seeds (say 20 letters) from several parts of the read, then extend and score the candidates with a gapped alignment.
Why 32 letters?
32 letters × 2 bits = 64 bits, one machine word, so comparisons are single integer compares. It is also long enough that most 32-letter words occur once in a chromosome.
Could a hash table beat 32 looks?
For exact lookups of fixed-length words, yes: one hash and a probe. But a sorted index also answers prefix queries (all words starting with a given 20 letters), which a hash table cannot.
