Systems and methods for index hopping filtering

Patent metadata

Field	Value
Publication number	US-12112833-B2
Application number	US-202117168050-A
Country	US
Kind code	B2
Filing date	Feb 4, 2021
Priority date	Feb 4, 2020
Publication date	Oct 8, 2024
Grant date	Oct 8, 2024

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.

First claim

What is claimed is:

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 T HH 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 T HH 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.

2. 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.

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

4. 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×10 12 }.

5. 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.

6. 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×10 12 }.

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

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

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

10. 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.

11. 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.

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

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

14. 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.

15. 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.

16. 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 i

Assignees

• 10X Genomics Inc

Inventors

• Hepler Nicolaus Lance
• Aluru Chaitanya
• Marks Patrick J
• Srinivas Niranjan
• Delaney Nigel

Classifications

• G06F16/2365

  Ensuring data consistency and integrity · CPC title

• G06F16/2255

  Hash tables · CPC title

• G16B40/10

  Signal processing, e.g. from mass spectrometry [MS] or from PCR · CPC title

• G16B30/00 Primary

  ICT specially adapted for sequence analysis involving nucleotides or amino acids · CPC title