Devices and methods for genome sequencing
A device includes arrays of Non-Volatile Memory (NVM) cells. Reference sequences representing portions of a genome are stored in respective groups of NVM cells. Exact matching phase substring sequences representing portions of at least one sample read are loaded into groups of NVM cells. One or more groups of NVM cells are identified where the stored reference sequence matches the loaded exact matching phase substring sequence using the arrays at Content Addressable Memories (CAMs). Approximate matching phase substring sequences are loaded into groups of NVM cells. One or more groups of NVM cells are identified where the stored reference sequence approximately matches the loaded approximate matching phase substring sequence using the arrays as Ternary CAMs (TCAMs). At least one of the reference sequence and the approximate matching phase substring sequence for each group of NVM cells includes at least one wildcard value when the arrays are used as TCAMs.
1. A device, comprising:
a plurality of arrays of Non-Volatile Memory (NVM) cells; and
circuitry configured to:
store reference sequences in respective groups of NVM cells of the plurality of arrays, each reference sequence representing a portion of a genome;
load one or more exact matching phase substring sequences into groups of NVM cells of the plurality of arrays for comparison to reference sequences stored in the groups of NVM cells, the one or more exact matching phase substring sequences representing portions of at least one sample read;
identify, in an exact matching phase, one or more groups of NVM cells in the plurality of arrays where the stored reference sequence matches the loaded exact matching phase substring sequence using the plurality of arrays as Content Addressable Memories (CAMs), wherein none of the compared reference sequences and the one or more exact matching phase substring sequences include wildcard values when using the plurality of arrays as CAMs in the exact matching phase;
load one or more approximate matching phase substring sequences into groups of NVM cells of the plurality of arrays for comparison to reference sequences stored in the groups of NVM cells, the one or more approximate matching phase substring sequences representing portions of the at least one sample read;
identify, in an approximate matching phase, one or more groups of NVM cells in the plurality of arrays where the stored reference sequence approximately matches the loaded approximate matching phase substring sequence using the plurality of arrays as Ternary CAMs (TCAMs), wherein at least one of the compared reference sequence and the approximate matching phase substring sequence for each group of NVM cells includes at least one wildcard value when using the plurality of arrays as TCAMs in the approximate matching phase; and
based on an indication of one or more identified groups of NVM cells from a first array of the plurality of arrays where one or more stored reference sequences match or approximately match a first substring sequence, perform at least one of:
store one or more additional reference sequences in a second array of the plurality of arrays; and
load at least one additional substring sequence into the second array.
2. The device of claim 1 , wherein the circuitry is further configured to vary an encoding scheme for the reference sequences, the one or more exact matching phase substring sequences, and the one or more approximate matching phase substring sequences to switch between operation of the plurality of arrays as CAMs and as TCAMs.
3. The device of claim 1 , wherein for the approximate matching phase, the circuitry is further configured to:
retain reference sequences stored in groups of NVM cells of an array of the plurality of arrays following operation of the array as a CAM in the exact matching phase;
reset match lines of the array;
load at least one approximate matching phase substring sequence into the groups of NVM cells of the array; and
identify one or more groups of NVM cells in the array where the stored reference sequence approximately matches the loaded at least one approximate matching phase substring sequence for operation of the array as a TCAM in the approximate matching phase.
4. The device of claim 1 , wherein for the exact matching phase, the circuitry is further configured to:
retain reference sequences stored in groups of NVM cells of an array of the plurality of arrays following operation of the array as a TCAM in the approximate matching phase;
reset match lines of the array;
load at least one exact matching phase substring sequence into the groups of NVM cells of the array; and
identify one or more groups of NVM cells in the array where the stored reference sequence matches the loaded at least one exact matching phase substring sequence for operation of the array as a CAM in the exact matching phase.
5. The device of claim 1 , wherein for at least one of the exact matching phase and the approximate matching phase, the circuitry is further configured to:
concurrently load one or more substring sequences into arrays of the plurality of arrays; and
concurrently identify groups of NVM cells in the arrays where the stored reference sequence matches or approximately matches the concurrently loaded one or more substring sequences.
6. The device of claim 5 , wherein the concurrently loaded one or more substring sequences includes substring sequences that represent different portions of the same sample read.
7. The device of claim 1 , wherein the number of NVM cells used to represent a base of an approximate matching phase substring sequence in at least one group of NVM cells in the plurality of arrays differs from the number of NVM cells used to represent a base of an exact matching phase substring sequence in the at least one group of NVM cells.
8. The device of claim 1 , further comprising at least one memory configured to store an index indicating identified groups of NVM cells where the stored reference sequence approximately matches or matches a loaded substring sequence.
9. The device of claim 1 , further comprising at least one memory configured to store a Smith-Waterman scoring matrix used during an approximate matching phase.
10. The device of claim 1 , wherein for the exact matching phase, the circuitry is further configured to:
load, into arrays of the plurality of arrays, exact matching phase substring sequences of the one or more exact matching phase substring sequences, wherein the exact matching phase substring sequences represent portions from a plurality of sample reads;
identify one or more groups of NVM cells in the arrays where the stored reference sequence matches the loaded exact matching phase substring sequences, wherein each stored reference sequence represents a portion of a reference genome;
determine probabilistic locations of the plurality of sample reads within the reference genome based on the identified one or more groups of NVM cells; and
sort the plurality of sample reads into a plurality of sample groups based at least in part on the determined probabilistic locations of the respective sample reads for aligning the sample reads using approximate matching.
11. A method of genome sequencing, the method comprising:
storing reference sequences in respective groups of Non-Volatile Memory (NVM) cells of at least one array of NVM cells, each reference sequence representing a portion of a genome;
loading one or more exact matching phase substring sequences into groups of NVM cells of the at least one array for operation of the at least one array as a Content Addressable Memory (CAM), the one or more exact matching phase substring sequences representing one or more portions of at least one sample read;
identifying, in an exact matching phase, one or more groups of NVM cells in the at least one array where the stored reference sequence matches the loaded exact matching phase substring sequence, wherein none of the stored reference sequences and the loaded one or more exact matching phase substring sequences include wildcard values when the at least one array operates as a CAM in the exact matching phase;
loading one or more approximate matching phase substring sequences into groups of NVM cells of the at least one array for operation of the at least one array as a Ternary CAM (TCAM), the one or more approximate matching phase substring sequences representing one or more portions of the at least one sample read;
identifying, in an approximate matching phase, one or more groups of NVM cells in the at least one array where the stored reference sequence approximately matches the loaded approximate matching phase sequence, wherein at least one of the stored reference sequence and the loaded approximate matching phase substring sequence for each group of NVM cells includes at least one wildcard value when the at least one array operates as a TCAM in the approximate matching phase; and
based on an indication of one or more identified groups of NVM cells from a first array of the at least one array where one or more stored reference sequences match or approximately match a first substring sequence, performing at least one of:
storing one or more additional reference sequences in a second array of the at least one array; and
loading at least one additional substring sequence into the second array.
12. The method of claim 11 , further comprising varying an encoding scheme for the reference sequences, the one or more exact matching phase substring sequences, and the one or more approximate matching phase substring sequences to switch between operation of the at least one array as a CAM and as a TCAM.
13. The method of claim 11 , further comprising for the approximate matching phase:
retaining reference sequences stored in groups of NVM cells of an array of the at least one array following operation of the array as a CAM in the exact matching phase;
resetting match lines of the array;
loading at least one approximate matching phase sequence into the groups of NVM cells of the array; and
identifying one or more groups of NVM cells in the array where the stored reference sequence approximately matches the loaded at least one approximate matching phase sequence for operation of the array as a TCAM in the approximate matching phase.
14. The method of claim 11 , further comprising for the exact matching phase:
retaining reference sequences stored in groups of NVM cells of an array of the at least one array following operation of the array as a TCAM in the approximate matching phase;
resetting match lines of the array;
loading at least one exact matching phase substring sequence into the groups of NVM cells of the array; and
identifying one or more groups of NVM cells in the array where the stored reference sequence matches the loaded at least one exact matching phase substring sequence for operation of the array as a CAM in the exact matching phase.
15. The method of claim 11 , further comprising for at least one of the exact matching phase and the approximate matching phase:
concurrently loading one or more substring sequences for one or more sample reads into arrays of the at least one array; and
concurrently identifying groups of NVM cells in the arrays where the stored reference sequence matches or approximately matches the concurrently loaded one or more substring sequences.
16. The method of claim 15 , wherein the concurrently loaded one or more substring sequences include substring sequences representing different portions of the same sample read.
17. The method of claim 11 , wherein the number of NVM cells used to represent a base of an approximate matching phase substring sequence in at least one group of NVM cells in the at least one array differs from the number of NVM cells used to represent a base of an exact matching phase substring sequence in the at least one group of NVM cells.
18. The method of claim 11 , further comprising storing in at least one memory indications of identified groups of NVM cells where the stored reference sequence approximately matches or matches a loaded substring sequence.
19. The method of claim 11 , further comprising for the exact matching phase:
loading, into the at least one array, exact matching phase substring sequences of the one or more exact matching substring sequences, wherein the exact matching phase substring sequences represent portions from a plurality of sample reads;
identifying one or more groups of NVM cells in the at least one array where the stored reference sequence matches the loaded exact matching phase substring sequences, wherein each stored reference sequence represents a portion of a reference genome;
determining probabilistic locations of the plurality of sample reads within the reference genome based on the identified one or more groups of NVM cells; and
sorting the plurality of sample reads into a plurality of sample groups based at least in part on the determined probabilistic locations of the respective sample reads for aligning the sample reads using approximate matching.
20. A device for genome sequencing, the device comprising:
at least one array of Non-Volatile Memory (NVM) cells configured to store reference sequences in respective groups of the NVM cells, each reference sequence representing a portion of a genome; and
means for:
storing the reference sequences in the respective groups of NVM cells of the at least one array;
loading one or more exact matching phase substring sequences into groups of NVM cells of the at least one array for operation of the at least one array as a Content Addressable Memory (CAM), the one or more exact matching phase substring sequences representing one or more portions of at least one sample read;
identifying, in an exact matching phase, one or more groups of NVM cells in the at least one array where the stored reference sequence matches the loaded exact matching phase substring sequence, wherein none of the stored reference sequences and the loaded one or more exact matching phase substring sequences include wildcard values when the at least one array operates as a CAM in the exact matching phase;
loading one or more approximate matching phase substring sequences into groups of NVM cells of the at least one array for operation of the at least one array as a Ternary CAM (TCAM), the one or more approximate matching phase substring sequences representing one or more portions of the at least one sample read; and
identifying, in an approximate matching phase, one or more groups of NVM cells in the at least one array where the stored reference sequence approximately matches the loaded approximate matching phase sequence, wherein at least one of the stored reference sequence and the loaded approximate matching phase substring sequence for each group of NVM cells includes at least one wildcard value when the at least one array operates as a TCAM in the approximate matching phase; and
wherein at least one group of NVM cells in the at least one array is used as part of a CAM in the exact matching phase and is used as part of a TCAM in the approximate matching phase, and wherein the number of NVM cells used to represent a base of an approximate matching phase substring sequence in the at least one group of NVM cells differs from the number of NVM cells used to represent a base of an exact matching phase substring sequence in the at least one group of NVM cells.
21. A device, comprising:
a plurality of arrays of Non-Volatile Memory (NVM) cells capable of operating in a Content Addressable Memory (CAM) mode and a Ternary CAM (TCAM) mode; and
circuitry configured to:
store reference sequences in respective groups of NVM cells of the plurality of arrays;
load one or more exact matching phase substring sequences into groups of NVM cells of the plurality of arrays;
set the plurality of arrays in the CAM mode and identify, in an exact matching phase, one or more groups of NVM cells where the stored reference sequence matches the loaded exact matching phase substring sequence;
load one or more approximate matching phase substring sequences into groups of NVM cells of the plurality of arrays; and
set the plurality of arrays in the TCAM mode and identify, in an approximate matching phase, one or more groups of NVM cells where the stored reference sequence approximately matches the loaded approximate matching phase substring sequence, wherein at least one of the compared reference sequence and the approximate matching phase substring sequence includes at least one wildcard value in the approximate matching phase; and
wherein at least one group of NVM cells in the plurality of arrays is used as a CAM in the exact matching phase and is used as a TCAM in the approximate matching phase, and wherein the number of NVM cells used to represent a base of an approximate matching phase substring sequence in the at least one group of NVM cells differs from the number of NVM cells used to represent a base of an exact matching phase substring sequence in the at least one group of NVM cells.
22. The device of claim 21 , wherein the circuitry is further configured to vary an encoding scheme for the reference sequences, the one or more exact matching substring sequences, and the one or more approximate matching substring sequences to switch between operation of the plurality of arrays in the CAM and TCAM modes.
23. The device of claim 21 , wherein a pair of values is loaded or stored in an NVM cell to represent a wildcard value in the approximate matching phase.
24. The device of claim 21 , wherein the circuitry is further configured to use an indication of one or more identified groups of NVM cells from a first array of the plurality of arrays where one or more stored reference sequences match or approximately match a first substring sequence for at least one of:
determining one or more additional reference sequences to be stored in a second array of the plurality of arrays; and
determining at least one additional substring sequence to be loaded into the second array.
25. The device of claim 21 , wherein for at least one of the exact matching phase and the approximate matching phase, the circuitry is further configured to:
concurrently load one or more substring sequences into arrays of the plurality of arrays; and
concurrently identify groups of NVM cells in the arrays where the stored reference sequence matches or approximately matches the concurrently loaded one or more substring sequences.
26. The device of claim 25 , wherein the concurrently loaded one or more substring sequences includes substring sequences that represent different portions of the same sample read.