# US 12,112,833 B2 · Systems and methods for index hopping filtering

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

- Number: US 12,112,833 B2
- Document ID: US12112833B2
- Status: Granted
- Kind: B2
- Application number: 17/168,050
- Filed: 2021-02-04
- Published: 2021-08-05
- Granted: 2024-10-08
- Earliest claimed: 2020-02-04
- Assignees: 10x Genomics, Inc.
- Applicants: 10X Genomics, Inc.
- Inventors: Nicolaus Lance Hepler; Chaitanya Aluru; Patrick J. Marks; Niranjan Srinivas; Nigel Delaney
- Web page: https://patentgrep.com/patent/US12112833B2

## CPC

- G16B 30/00: ICT specially adapted for sequence analysis involving nucleotides or amino acids
- G06F 16/2255: {Hash tables}
- G06F 16/2365: {Ensuring data consistency and integrity}
- G16B 40/10: Signal processing, e.g. from mass spectrometry [MS] or from PCR
- G16B: BIOINFORMATICS, i.e. INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR GENETIC OR PROTEIN-RELATED DATA PROCESSING IN COMPUTATIONAL MOLECULAR BIOLOGY
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Methods for index hopping sequence read filtering are provided. Each read in a plurality of reads from a multiplexed reaction comprises an insert portion, and first (molecular identifier) and second (sample index) non-insert portions. For each of a plurality of hashes, a hash data structure is formed with a representation of each read. Each representation comprises a hash of the first non-insert portion of the corresponding read. Read pairs are identified in the hash data structures. Each pair includes a first and second read sharing a common hash value but differing index values. An entry is added into a heterogeneous data structure, for each such pair, that includes the first and second non-insert portions of the first and second reads of the pair. Reads with first non-insert portion values appearing more than a threshold number of times in the heterogeneous data structure are removed from the plurality of reads.

## Claims

### Claim 1

A method of filtering out erroneous sequence reads, the method comprising:
at a computer system having one or more processors, and memory storing one or more programs for execution by the one or more processors:
(A) obtaining a plurality of sequence reads, in electronic form, from a multiplexed sequencing reaction, wherein
the plurality of sequence reads comprises 10,000 sequence reads;
each respective sequence read in the plurality of sequence reads comprises a corresponding insert portion, a corresponding first non-insert portion consisting of N nucleotide positions, and a corresponding second non-insert portion consisting of M nucleotide positions,
N and M are positive integers,
each corresponding first non-insert portion represents an identifier of a unique molecule,
each corresponding second non-insert portion comprises a sample index,
the plurality of sequence reads includes one or more first sequence reads from a first sample that each have a first value for the sample index,
the plurality of sequence reads includes one or more second sequence reads from a second sample that each have a second value for the sample index;
(B) performing a uniqueness test by:
(i) obtaining a table THH that comprises the corresponding first and second non-insert portions of each sequence read in the plurality of sequence reads, lexicographically sorted on the first non-insert portion,
(ii) identifying each respective first non-insert portion represented in THH for which a predetermined second threshold number of unique second non-coding portion pairs can be made from pairs of sequence reads in Tim having the respective first non-insert portion, wherein each second non-coding portion pair in the threshold number of unique second non-coding portion pairs comprises an independent pair of different second non-coding portion values, and
(iii) removing from the plurality of sequence reads each sequence read in the plurality of sequence reads having an identified first non-insert portion;
(C) for each respective hash in a plurality of hashes, forming a corresponding hash data structure, wherein the corresponding hash data structure includes a representation of each respective sequence read, in the plurality of sequence reads, and comprises a hash value, of length L nucleotide positions, wherein L is less than N, formed by hashing at least the corresponding first non-insert portion of the respective sequence read in accordance with the respective hash, thereby forming a plurality of hash data structures;
(D) creating a heterogenous data structure comprising a plurality of entries by identifying a plurality of unique sequence read pairs in the plurality of hash data structures in greater than linear time, wherein
each respective sequence read pair in the plurality of unique sequence read pairs includes a corresponding first sequence read and a corresponding second sequence read sharing a common hash value and having different second values for the sample index, and
each corresponding entry in the heterogeneous data structure comprises a respective unique sequence read pair in the plurality of unique sequence read pairs, wherein the corresponding entry includes at least the corresponding first and second non-insert portions of the corresponding first sequence read and the corresponding first and second non-insert portions of the corresponding second sequence read of the respective unique sequence read pair;
(E) identifying a set of sequence reads using the heterogeneous data structure, wherein each sequence read in the set of sequence reads has a corresponding first non-insert portion value that appears more than a predetermined first threshold number of times in the heterogeneous data structure; and
(F) removing the set of sequence reads from the plurality of sequence reads thereby filtering out erroneous sequence reads.

### Claim 2 (depends on 1)

The method of claim 1, wherein the plurality of sequence reads is from more than five different biological samples and comprises more than one hundred thousand sequence reads.

### Claim 3 (depends on 1)

The method of claim 1, wherein the unique molecular identifier has a nucleotide length of between 8 nucleotide positions and 20 nucleotide positions.

### Claim 4 (depends on 1)

The method of claim 1, wherein the unique molecular identifier encodes a unique predetermined value selected from the set {1, . . . , 1024}, selected from the set {1, . . . , 4096}, selected from the set {1, . . . , 16384}, selected from the set {1, . . . , 65536}, selected from the set {1, . . . , 262144}, selected from the set {1, . . . , 1048576}, selected from the set {1, . . . , 4194304}, selected from the set {1, . . . , 16777216}, selected from the set {1, . . . , 67108864}, or selected from the set {1, . . . , 1×1012}.

### Claim 5 (depends on 1)

The method of claim 1, wherein the corresponding first non-insert portion of each respective sequence read in the plurality of sequences reads comprises a corresponding independent barcode, from a plurality of barcodes, wherein each barcode in the plurality of barcodes represents a different gel bead-in emulsion in a plurality of gel bead-in emulsions.

### Claim 6 (depends on 5)

The method of claim 5, wherein each barcode in the plurality of barcodes encodes a unique predetermined value selected from the set {1, . . . , 1024}, selected from the set {1, . . . , 4096}, selected from the set {1, . . . , 16384}, selected from the set {1, . . . , 65536}, selected from the set {1, . . . , 262144}, selected from the set {1, . . . , 1048576}, selected from the set {1, . . . , 4194304}, selected from the set {1, . . . , 16777216}, selected from the set {1, . . . , 67108864}, or selected from the set {1, . . . , 1×1012}.

### Claim 7 (depends on 1)

The method of claim 1, wherein
N is between 10 and 100, and
M is between 5 and 20.

### Claim 8 (depends on 7)

The method of claim 7, wherein L is between 4 and 99.

### Claim 9 (depends on 1)

The method of claim 1, wherein
N is between 36 and 40, and
M is 8.

### Claim 10 (depends on 1)

The method of claim 1, wherein the hash value formed by hashing at least the corresponding first non-insert portion of the respective sequence read in accordance with the respective hash comprises forming the hash value from a predetermined subset of nucleotide positions in the corresponding first non-insert portion, wherein the predetermined subset of nucleotide positions is defined by the respective hash and is unique to the respective hash.

### Claim 11 (depends on 10)

The method of claim 10, wherein each respective hash in the plurality of hashes defines a different predetermined subset of nucleotide positions in the first non-insert portion.

### Claim 12 (depends on 1)

The method of claim 1, wherein the plurality of hashes consists of between three and one hundred hashes.

### Claim 13 (depends on 1)

The method of claim 1, wherein the predetermined second threshold number is a number between 500 and 100,000.

### Claim 14 (depends on 1)

The method of claim 1, wherein
the corresponding hash data structure is a corresponding first table,
each row in the corresponding first table includes the representation of a respective sequence read in the plurality of sequence reads,
the representation of each sequence read further comprises the corresponding second portion of the sequence read, and
the corresponding first table is sorted on hash value.

### Claim 15 (depends on 14)

The method of claim 14, wherein each sequence read further comprises a file identifier identifying a file name that contains the sequence read and the representation of each sequence read in the corresponding first table further comprises the file identifier.

### Claim 16 (depends on 1)

The method of claim 1, wherein
the heterogeneous data structure is a second table,
each row in the second table includes a corresponding entry, and
the second table is sorted in lexicographic field order using at least the first and second non-insert portions of the corresponding first sequence read and the first and second non-insert portions of the corresponding second sequence read of each corresponding entry in the second table.

### Claim 17 (depends on 16)

The method of claim 16, wherein the corresponding entry further includes a file identifier of the corresponding first sequence read and the file identifier of the corresponding second sequence read of the respective unique sequence read pair.

### Claim 18 (depends on 1)

The method of claim 1, wherein the plurality of sequence reads includes sequence reads from a plurality of biological samples, wherein each biological sample in the plurality of biological samples is assigned a different sample index value for the sample index.

### Claim 19 (depends on 1)

The method of claim 1, wherein the plurality of sequence reads is obtained by loading test nucleic acids onto a plurality of gel bead-in emulsions beads.

### Claim 20 (depends on 1)

The method of claim 1, wherein the first predetermined threshold number of times is an integer that is greater than 1 and that is less than a number of hashes in the plurality of hashes.

### Claim 21 (depends on 1)

The method of claim 1, wherein the first predetermined threshold number of times is four, five, six, or seven and the number of hashes in the plurality of hashes is eight.

### Claim 22 (depends on 1)

The method of claim 1, wherein the multiplexed sequencing is a single-strand consequence sequencing or a duplex consensus sequencing.

### Claim 23 (depends on 1)

The method of claim 1, wherein the first non-insert portion comprises two or more predetermined non-contiguous portions of each respective sequence read in the plurality of sequence reads.

### Claim 24 (depends on 1)

The method of claim 1, wherein the plurality of sequence reads is scRNA-seq sequence reads or scATAC-seq sequence reads.

### Claim 25 (depends on 1)

The method of claim 1, wherein the plurality of sequences reads collectively map to one megabase of a reference genome with a coverage of at least 1.

### Claim 26

A computing system, comprising:
one or more processors;
memory storing one or more programs to be executed by the one or more processors;
the one or more programs comprising instructions for:
(A) obtaining a plurality of sequence reads, in electronic form, from a multiplexed sequencing reaction, wherein
the plurality of sequence reads comprises 10,000 sequence reads;
each respective sequence read in the plurality of sequence reads comprises a corresponding insert portion, a corresponding first non-insert portion consisting of N nucleotide positions, and a corresponding second non-insert portion consisting of M nucleotide positions,
N and M are positive integers,
each corresponding first non-insert portion represents an identifier of a unique nucleic acid molecule,
each corresponding second non-insert portion comprises a sample index,
the plurality of sequence reads includes one or more first sequence reads from a first sample that each have a first value for the sample index,
the plurality of sequence reads includes one or more second sequence reads from a second sample that each have a second value for the sample index;
(B) performing a uniqueness test by:
(i) obtaining a table THH that comprises the corresponding first and second non-insert portions of each sequence read in the plurality of sequence reads, lexicographically sorted on the first non-insert portion,
(ii) identifying each respective first non-insert portion represented in THH for which a predetermined second threshold number of unique second non-coding portion pairs can be made from pairs of sequence reads in THH having the respective first non-insert portion, wherein each second non-coding portion pair in the threshold number of unique second non-coding portion pairs comprises an independent pair of different second non-coding portion values, and
(iii) removing from the plurality of sequence reads each sequence read in the plurality of sequence reads having an identified first non-insert portion;
(C) for each respective hash in a plurality of hashes, forming a corresponding hash data structure, wherein the corresponding hash data structure includes a representation of each respective sequence read in the plurality of sequence reads that comprises a hash value, of length L nucleotide positions, wherein L is less than N, formed by hashing at least the corresponding first non-insert portion of the respective sequence read in accordance with the respective hash, thereby forming a plurality of hash data structures;
(D) creating a heterogenous data structure comprising a plurality of entries by identifying a plurality of unique sequence read pairs in plurality of hash data structures in greater than linear time, wherein
each respective sequence read pair in the plurality of unique sequence read pairs includes a corresponding first sequence read and a corresponding second sequence read sharing a common hash value and having different second values for the sample index, and
each corresponding entry in the heterogeneous data structure comprises a respective unique sequence read pair in the plurality of unique sequence read pairs, wherein the corresponding entry includes at least the corresponding first and second non-insert portions of the corresponding first sequence read and the corresponding first and second non-insert portions of the corresponding second sequence read of the respective unique sequence read pair;
(E) identifying a set of sequence reads using the heterogeneous data structure, wherein each sequence read in the set of sequence reads has a corresponding first non-insert portion value that appears more than a predetermined first threshold number of times in the heterogeneous data structure; and
(F) removing the set of sequence reads from the plurality of sequence reads thereby filtering out erroneous sequence reads.

### Claim 27

A non-transitory computer readable storage medium storing one or more programs configured for execution by a computer, the one or more programs comprising instructions for:
(A) obtaining a plurality of sequence reads, in electronic form, from a multiplexed sequencing reaction, wherein
the plurality of sequence reads comprises 10,000 sequence reads;
each respective sequence read in the plurality of sequence reads comprises a corresponding insert portion, a corresponding first non-insert portion consisting of N nucleotide positions, and a corresponding second non-insert portion consisting of M nucleotide positions,
N and M are positive integers,
each corresponding first non-insert portion represents an identifier of a unique molecule,
each corresponding second non-insert portion comprises a sample index,
the plurality of sequence reads includes one or more first sequence reads from a first sample that each have a first value for the sample index,
the plurality of sequence reads includes one or more second sequence reads from a second sample that each have a second value for the sample index;
(B) performing a uniqueness test by:
(i) obtaining a table THH that comprises the corresponding first and second non-insert portions of each sequence read in the plurality of sequence reads, lexicographically sorted on the first non-insert portion,
(ii) identifying each respective first non-insert portion represented in THH for which a predetermined second threshold number of unique second non-coding portion pairs can be made from pairs of sequence reads in THH having the respective first non-insert portion, wherein each second non-coding portion pair in the threshold number of unique second non-coding portion pairs comprises an independent pair of different second non-coding portion values, and
(iii) removing from the plurality of sequence reads each sequence read in the plurality of sequence reads having an identified first non-insert portion;
(C) for each respective hash in a plurality of hashes, forming a corresponding hash data structure, wherein the corresponding hash data structure includes a representation of each respective sequence read in the plurality of sequence reads that comprises a hash value, of length L nucleotide positions, wherein L is less than N, formed by hashing at least the corresponding first non-insert portion of the respective sequence read in accordance with the respective hash, thereby forming a plurality of hash data structures;
(D) creating a heterogenous data structure comprising a plurality of entries by identifying a plurality of unique sequence read pairs in the plurality of hash data structures in greater than linear time, wherein
each respective sequence read pair in the plurality of unique sequence read pairs includes a corresponding first sequence read and a corresponding second sequence read sharing a common hash value and having different second values for the sample index, and
each corresponding entry in the heterogeneous data structure comprises a respective unique sequence read pair in the plurality of unique sequence read pairs, wherein the corresponding entry includes at least the corresponding first and second non-insert portions of the corresponding first sequence read and the corresponding first and second non-insert portions of the corresponding second sequence read of the respective unique sequence read pair;
(E) identifying a set of sequence reads using the heterogeneous data structure, wherein each sequence read in the set of sequence reads has a corresponding first non-insert portion value that appears more than a threshold number of times in the heterogeneous data structure; and
(F) removing the set of sequence reads from the plurality of sequence reads thereby filtering out erroneous sequence reads.