# US 2021/0241853 A1 · 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 2021/0241853 A1 - Document ID: US20210241853A1 - Status: Published application - Kind: A1 - Application number: 17/168,050 - Filed: 2021-02-04 - Published: 2021-08-05 - 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/US20210241853A1 ## 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) 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; (C) for each respective hash data structure in the plurality of hash data structures, performing a first procedure that comprises: identifying zero or more unique sequence read pairs in the respective hash data structure, wherein each respective sequence read pair in the zero or more 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 adding a corresponding entry into a heterogeneous data structure for each respective unique sequence read pair in the zero or more unique sequence read pairs identified using the respective hash data structure, 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; (D) 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 (E) 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, 2) The method of claim 1 or 2, wherein the unique molecular identifier has a nucleotide length of between 8 nucleotide positions and 20 nucleotide positions. ### Claim 4 (depends on 1, 2) The method of claim 1 or 2, 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, 2, 3, 4) The method of any one of claims 1-4, 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, 2, 3, 4, 5, 6) The method of any one of claims 1-6, wherein N is between 10 and 100, and M is between 5 and 20. ### Claim 8 (depends on 1, 2, 3, 4, 5, 6) The method of any one of claims 1-6, wherein N is between 36 and 40, and M is 8. ### Claim 9 (depends on 7) The method of claim 7, wherein L is between 4 and 99. ### Claim 10 (depends on 8) The method of claim 8, wherein L is between 4 and 35. ### Claim 11 (depends on 1, 2, 3, 4, 5, 6, 7, 8, 9, 10) The method of any one of claims 1-10, 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 12 (depends on 11) The method of claim 11, wherein each respective hash in the plurality of hashes defines a different predetermined subset of nucleotide positions in the first non-insert portion. ### Claim 13 (depends on 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12) The method of any one of claims 1-12, wherein the plurality of hashes consists of between three and one hundred hashes. ### Claim 14 (depends on 1) The method of claim 1, the method further comprising reducing a computational expense of the identifying (D) by removing each respective sequence read in the plurality of sequence reads that fails to satisfy a uniqueness test. ### Claim 15 (depends on 14) The method of claim 14, the method further comprises evaluating each respective sequence read in the plurality of sequence reads to determine whether it satisfies the uniqueness test by performing a second procedure that comprises: (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, 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 each sequence read in the plurality of sequence reads having an identified first non-insert portion. ### Claim 16 (depends on 15) The method of claim 15, wherein the predetermined second threshold number is a number between 500 and 100,000. ### Claim 17 (depends on 15) The method of claim 15, wherein the predetermined second threshold number is a number between 5,000 and 25,000. ### Claim 18 (depends on 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17) The method of any one of claims 1-17, 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 19 (depends on 18) The method of claim 18, 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 20 (depends on 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18) The method of any one of claims 1-18, 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 21 (depends on 20) The method of claim 20, 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 22 (depends on 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21) The method of any one of claims 1-21, 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 23 (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 24 (depends on 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23) The method of any one of claims 1-23, 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 25 (depends on 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23) The method of any one of claims 1-23, 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 26 (depends on 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25) The method of any one of claims 1-25, wherein the multiplexed sequencing is a single-strand consequence sequencing or a duplex consensus sequencing. ### Claim 27 (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 28 (depends on 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27) The method of any one of claims 1-27, wherein the plurality of sequence reads collectively map to one megabase of a reference genome with an coverage of at least 1. ### Claim 29 (depends on 1) The method of claim 1, wherein the identifier of the unique molecule is a predetermined unique molecular identifier. ### Claim 30 (depends on 1) The method of claim 1, wherein the plurality of sequence reads are scRNA-seq sequence reads. ### Claim 31 (depends on 1) The method of claim 1, wherein the plurality of sequence reads are scATAC-seq sequence reads. ### Claim 32 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) 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; (C) for each respective hash data structure in the plurality of hash data structures, performing a first procedure that comprises: identifying zero or more unique sequence read pairs in the respective hash data structure, wherein each respective sequence read pair in the zero or more 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 adding a corresponding entry into a heterogeneous data structure for each respective unique sequence read pair in the zero or more unique sequence read pairs identified using the respective hash data structure, 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; (D) 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 (E) removing the set of sequence reads from the plurality of sequence reads thereby filtering out erroneous sequence reads. ### Claim 33 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) 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; (C) for each respective hash data structure in the plurality of hash data structures, performing a first procedure that comprises: identifying zero or more unique sequence read pairs in the respective hash data structure, wherein each respective sequence read pair in the zero or more 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 adding a corresponding entry into a heterogeneous data structure for each respective unique sequence read pair in the zero or more unique sequence read pairs identified using the respective hash data structure, 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; (D) 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 (E) removing the set of sequence reads from the plurality of sequence reads thereby filtering out erroneous sequence reads.