# US 2019/0377851 A1 · Efficient payload extraction from polynucleotide sequence reads

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2019/0377851 A1
- Document ID: US20190377851A1
- Status: Published application
- Kind: A1
- Application number: 16/003,013
- Filed: 2018-06-07
- Published: 2019-12-12
- Earliest claimed: 2018-06-07
- Assignees: Microsoft Technology Licensing, LLC
- Applicants: Microsoft Technology Licensing, LLC
- Inventors: Konstantin Makarychev
- Web page: https://patentgrep.com/patent/US20190377851A1

## CPC

- G16B 40/00: ICT specially adapted for biostatistics; ICT specially adapted for bioinformatics-related machine learning or data mining, e.g. knowledge discovery or pattern finding
- G16H 50/20: for computer-aided diagnosis, e.g. based on medical expert systems
- G16B 30/00: ICT specially adapted for sequence analysis involving nucleotides or amino acids
- G16B 50/00: ICT programming tools or database systems specially adapted for bioinformatics
- G16B: BIOINFORMATICS, i.e. INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR GENETIC OR PROTEIN-RELATED DATA PROCESSING IN COMPUTATIONAL MOLECULAR BIOLOGY
- G16H: HEALTHCARE INFORMATICS, i.e. INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR THE HANDLING OR PROCESSING OF MEDICAL OR HEALTHCARE DATA

## Abstract

Systems and techniques for extracting information-containing payloads from DNA or other polynucleotides are provided. Decoding the sequence of payload regions from multiple polynucleotides to obtain encoded information includes sequencing the molecules with a polynucleotide sequencer. Reads generated by the polynucleotide sequencer can include information from multiple different sources mixed together. Primer sequences present in the reads identify which reads contain information from the same source. A computationally efficient technique for finding primer sequences in the reads includes comparing hashes of the reads and hashes of primer sequences to find an approximate location then computing edit distances between the primer sequences and the reads to find an exact location. Reads that include the same primer sequences may be clustered together. Sequences of the payload regions are extracted based on the locations of the primer sequences.

## Claims

### Claim 1

A system comprising:
one or more processing units;
one or more computer-readable media in communication with the one or more processing units;
a hashing module stored in the one or more computer-readable media and executable on the one or more processing units to generate a first hash of a primer sequence, generate a second hash of a subsequence of a read produced by a polynucleotide sequencer, and determine that the second hash has less than a threshold difference from the first hash; and
an edit distance module stored in the one or more computer-readable media and executable on the one or more processing units to identify an evaluation window in the read which includes and is longer than the subsequence of the read and determine a best-match subsequence within the evaluation window that is a same length as the primer sequence and that has a smallest edit distance from the primer sequence relative to other subsequences within the evaluation window.

### Claim 2 (depends on 1)

The system of claim 1, wherein the hashing module generates the first hash by encoding k-mers present in the primer sequence as a first vector, generates the second hash by encoding k-mers present in the read as a second vector, and the threshold difference is a threshold distance from the first vector to the second vector.

### Claim 3 (depends on 2)

The system of claim 2, wherein a distance from the first vector to the second vector is calculated by one of an L1 distance, a Hamming distance, or a number of positions that are zero in the first vector but non-zero in the second vector.

### Claim 4 (depends on 1)

The system of claim 1, wherein the edit distance module uses dynamic programming to identify the best-match subsequence by recursively calculating edit distances for subsequences the same length as the primer sequence within the evaluation window by advancing a region of comparison one base pair per iteration.

### Claim 5 (depends on 1)

The system of claim 1, further comprising a payload extraction module stored in the one or more computer-readable media and executable on the one or more processing units to separate a payload region of the read from other sequences in the read.

### Claim 6 (depends on 1)

The system of claim 1, further comprising an exact match module stored in the one or more computer-readable media and executable on the one or more processing units to identify an exact match between the primer sequence and a subsequence of the read by one of (i) determining that the subsequence of the read has an edit distance of zero from the primer sequence or (ii) building a deterministic finite automaton (DFA) having an accept state representing the primer sequence.

### Claim 7 (depends on 1)

The system of claim 1, further comprising a primer location prediction module stored in the one or more computer-readable media and executable on the one or more processing units to predict a location of the primer sequence in the read based on (i) a known length of a payload region and a different location of a different primer sequence, (ii) an offset from a start of the read, the offset based on sequencing technology used by the polynucleotide sequencer, or (iii) a known sequence of an additional primer that is paired with the primer sequence.

### Claim 8

A method comprising:
receiving a plurality of reads from a polynucleotide sequencer;
receiving a plurality of primer sequences;
locating primer sequences within the plurality of reads; and
extracting payload regions from the plurality of reads, the payload regions located between two primer sequences, such that payload regions associated with a same pair of primers are grouped together.

### Claim 9 (depends on 8)

The method of claim 8, wherein the locating primer sequences comprises:
identifying an approximate location by comparing a first hash of a one of the primer sequences to a second hash of a first subsequence of a one of the plurality of reads; and
identifying an exact location by finding a second subsequence in the approximate location having a smallest edit distance from the one of the primer sequences.

### Claim 10 (depends on 9)

The method of claim 9, wherein the first hash and the second hash are computed by counting a number of k-mers within the one of the primer sequences and the first subsequence of the one of the plurality of reads respectively.

### Claim 11 (depends on 9)

The method of claim 9, wherein identifying the exact location comprises:
sliding a window for comparison one nucleotide per iteration along the approximate location; and
identifying an alignment of the window with respect to the approximate location that has an edit distance to the one of the primer sequences that is smaller than any other alignment.

### Claim 12 (depends on 8)

The method of claim 8, wherein the locating primer sequences comprises:
finding exact matches between subsequences of the reads and the primer sequences by (i) identifying subsequences of the reads that have an edit distance of zero from one of the primer sequences or (ii) building a deterministic finite automaton (DFA) having accept states representing the primer sequences.

### Claim 13

A method comprising:
identifying, in a polynucleotide read generated by a polynucleotide sequencer, a first primer sequence and a second primer sequence, the identifying performed by:
finding a first location of a first subsequence of the polynucleotide read for which a first subsequence hash is less than a threshold distance from a first primer hash of the first primer sequence;
identifying the first primer sequence in the polynucleotide read based on the first location of the first subsequence of the polynucleotide read and a first edit distance from the first primer sequence;
finding a second location of a second subsequence of the polynucleotide read for which a second subsequence hash is less than the threshold distance from a second primer hash of the second primer sequence; and
identifying the second primer sequence in the polynucleotide read based on the location of the second subsequence of the polynucleotide read and a second edit distance from the second primer sequence;
labeling a third subsequence of the polynucleotide read between the first primer sequence and the second primer sequence as a payload sequence; and
extracting the payload sequence together with a plurality of other payload sequences also associated with the first primer and the second primer.

### Claim 14 (depends on 13)

The method of claim 13, wherein the first subsequence hash is a vector in 4k dimensional space indexed by k-mers such that the t-th coordinate of the first subsequence hash equals a number of occurrences oft in the first subsequence of the polynucleotide read.

### Claim 15 (depends on 13)

The method of claim 13, wherein the threshold distance from the first primer hash to the first subsequence hash is determined by one of an L1 distance, a Hamming distance, or a number of positions in the first subsequence hash and the first primer hash for which one of the hashes has a zero value and the other hash has a non-zero value.

### Claim 16 (depends on 13)

The method of claim 13, wherein identifying the first primer sequence further comprises finding a subsequence of the polynucleotide read such that the first edit distance to the first primer is minimized.

### Claim 17 (depends on 13)

The method of claim 13, wherein the payload sequence is adjacent to an end of the first primer sequence and adjacent to an end of the second primer sequence.

### Claim 18 (depends on 13)

The method of claim 13, wherein identifying the first primer sequence further comprises evaluating the first edit distance over an evaluation window which is a portion of the polynucleotide read that includes and is longer than the first subsequence of the polynucleotide read.

### Claim 19 (depends on 18)

The method of claim 18, wherein the first edit distance is calculated by dynamic programming that recursively evaluates multiple partially overlapping subsequences in the evaluation window.

### Claim 20 (depends on 13)

The method of claim 13, further comprising decoding the payload sequence and the other payload sequences to generate a computer file.
