FastPrepDegenerate DNA Substring Search

Degenerate DNA Substring Search

Benchling logoBenchling● MediumFULLTIMEONSITE INTERVIEW
Learn

Problem statement

Search the uploaded DNA sequences for a substring matching query. Sequence characters are standard bases A, C, G, and T. Query characters may also use IUPAC degenerate bases:

  • R=AG, Y=CT, M=AC, K=GT, W=AT, S=CG
  • B=CGT, D=AGT, H=ACT, V=ACG, N=ACGT

Return the distinct matching sequences in lexicographic order.

Indexed search follow-up

The report also describes indexing each uploaded sequence by its four-base substrings. For a query of at least four bases, form candidate sets for its four-grams and intersect them, then verify each candidate by exact substring matching. The report gives ATTAGATT and query GATTA as a false positive for intersection alone: the required four-grams occur in different positions. For degenerate bases, union all compatible concrete four-gram postings before intersection; verify the original degenerate query against every remaining sequence. Queries shorter than four bases need a direct-scan fallback. Discuss retaining the index for multiple queries. The judged function uses the supplied finite array.

Function

findDegenerateDnaMatches(sequences: String[], query: String) → String[]

Examples

Example 1

sequences = ["GATTACA","GATTG"]query = "GATT"return = ["GATTACA","GATTG"]

Both sequences contain GATT.

Example 2

sequences = ["GATTACA","GATTG"]query = "GATTM"return = ["GATTACA"]

M accepts A or C, so only GATTACA matches.

Constraints

  • 1 <= sequences.length <= 1000.
  • 1 <= query.length <= 100.
  • 1 <= sequences[i].length <= 1000.
  • Sequence characters are ACGT; query characters are valid standard or degenerate IUPAC bases.

More Benchling problems

See Benchling hiring insights
public String[] findDegenerateDnaMatches(String[] sequences, String query) {
    // Write your code here.
}
sequences["GATTACA","GATTG"]
query"GATT"
expected["GATTACA", "GATTG"]
Checking account…