Granted Patent B2

US 12,387,818 · App. 17/138,053 · Granted Aug 12, 2025

Inventors: Meysam Roodi (Richmond Hill, CA); Zahra Lak (Toronto, CA)

Assignee: HUAWEI TECHNOLOGIES CO., LTD.

G16B30/10G06F16/9024G16B50/30

Abstract

Claims (185)

1. A method comprising:

receiving, by a hardware device comprising at least one processing unit and memory including a first type and a second type of memory, a count table and an occurrence table for a reference genome sequence generated using a Burrows Wheeler Transform (BWT) algorithm, wherein the reference genome sequence comprises a sequence of base pairs (bps);

determining, by the at least one processing unit, a size of a first part of the occurrence table based on a size of the first type of memory and a minimum number of bytes in the first type of memory, the minimum number of bytes in the first type of memory based on a number of bps of short reads (SRs) to be processed using the first type of memory;

storing, by the at least one processing unit, the count table and the occurrence table in the memory, wherein the first part of the occurrence table is stored in the first type of memory and a second part of the occurrence table is stored in the second type of memory, wherein a first memory access time for accessing the first part of the occurrence table in the first type of memory is less than a second memory access time for accessing the second part of the occurrence table stored in the second type of memory;

receiving, by the hardware device, a short read (SR) of an input genome sample sequence comprising a first number of bps and a second number of bps; and

performing, by the at least one processing unit, alignment of the SR of the input genome sample sequence against the reference genome sequence to generate seeds using the count table and the occurrence table stored in the memory, wherein the first part of the occurrence table stored in the first type of memory comprises n levels of entries, each entry of an i-th level of the n levels of entries has a

1

4

i

memory access probability during the performing the alignment, 1≤i≤n, and the n levels of entries of the first part of the occurrence table have the highest memory access probabilities among all entries of the occurrence table, the performing comprising:

performing alignment of the first number of bps in the SR of the input genome sample sequence against the sequence of bps of the reference genome sequence using the first part of the occurrence table stored in the first type of memory; and

performing alignment of the second number of bps in the SR of the input genome sample sequence against the sequence of bps of the reference genome sequence using the second part of the occurrence table stored in the second type of memory.

2. The method of claim 1 , wherein the size of the first part of the occurrence table is determined based on

s

=

(

∑

i

=

0

n

-

1

4

i

+

1

)

×

4

,

where s is the minimum number of bytes in the first type of memory, n is the number of the bps of the SRs to be processed using the first type of memory.

3. The method of claim 1 , wherein the size of the first part of the occurrence table is determined based on

s

=

(

∑

i

=

0

n

-

1

4

i

+

1

)

×

4

×

2

,

where s is the minimum number of bytes in the first type of memory, n is the number of the bps of the SRs to be processed using the first type of memory.

4. The method of claim 1 , wherein the occurrence table comprises a plurality of rows, and a number of the plurality of rows equals a number of bps in the sequence of bps of the reference genome sequence.

5. The method of claim 4 , a row of the occurrence table comprises 4 entries of occurrence numbers corresponding to characters A, C, G, and T, respectively.

6. The method of claim 5 , further comprising:

initializing, by the at least one processing unit, a top pointer to 0;

initializing, by the at least one processing unit, a bottom pointer to a size of the genome reference sequence, wherein each of the top pointer and bottom pointer points to an entry in the occurrence table; and

determining, by the at least one processing unit, the first part of the occurrence table based on top new =count (char)+occurrence (top old , char) and bottom new =count (char)+occurrence (bottom old , char), wherein top new is a new value of the top pointer, top old is an old value of the top pointer, bottom new is a new value of the bottom pointer, bottom old is an old value of the bottom pointer, count (char) is a total count of characters that are smaller than character char, and occurrence (x, y) is an entry in the occurrence table indexed by row x and column y.

7. The method of claim 1 , wherein the count table comprises four entries corresponding to four different bp types, each entry of the count table comprising a total count of bps in the reference genome sequence that are smaller than a bp corresponding to the entry, and wherein the occurrence table comprises a plurality of rows and four columns, the four columns corresponding to the four different bp types, each entry of the occurrence table indexed by a row index and a column index comprises a count of a bp corresponding to the column index up to the row index.

8. A hardware device comprising:

at least one processing unit;

memory including a first type and a second type of memory;

a non-transitory computer readable storage medium storing programming for execution by the at least one processing unit, the programming including instructions to cause the hardware device to perform operations including:

receiving a count table and an occurrence table for a reference genome sequence generated using a Burrows Wheeler Transform (BWT) algorithm, wherein the reference genome sequence comprises a sequence of base pairs (bps);

determining a size of a first part of the occurrence table based on a size of the first type of memory and a minimum number of bytes in the first type of memory, the minimum number of bytes in the first type of memory based on a number of bps of short reads (SRs) to be processed using the first type of memory;

storing the count table and the occurrence table in the memory, wherein the first part of the occurrence table is stored in the first type of memory and a second part of the occurrence table is stored in the second type of memory, wherein a first memory access time for accessing the first part of the occurrence table in the first type of memory is less than a second memory access time for accessing the second part of the occurrence table stored in the second type of memory;

receiving a short read (SR) of an input genome sample sequence comprising a first number of bps and a second number of bps; and

performing alignment of the SR of the input genome sample sequence against the reference genome sequence to generate seeds using the count table and the occurrence table stored in the memory, wherein the first part of the occurrence table stored in the first type of memory comprises n levels of entries, each entry of an i-th level of the n levels of entries has a

1

4

i

memory access probability during the performing the alignment, 1≤i≤n, and the n levels of entries of the first part of the occurrence table have the highest memory access probabilities among all entries of the occurrence table, the performing the alignment comprising:

 performing alignment of the first number of bps in the SR of the input genome sample sequence against the sequence of bps of the reference genome sequence using the first part of the occurrence table stored in the first type of memory; and

performing alignment of the second number of bps in the SR of the input genome sample sequence against the sequence of bps of the reference genome sequence using the second part of the occurrence table stored in the second type of memory.

9. The hardware device of claim 8 , wherein the size of the first part of the occurrence table is determined based on

s

=

(

∑

i

=

0

n

-

1

4

i

+

1

)

×

4

,

where s is the minimum number of bytes in the first type of memory, n is the number of the bps of the SRs to be processed using the first type of memory.

10. The hardware device of claim 8 , wherein the size of the first part of the occurrence table is determined based on

s

=

(

∑

i

=

0

n

-

1

4

i

+

1

)

×

4

×

2

,

where s is the minimum number of bytes in the first type of memory, n is the number of the bps of the SRs to be processed using the first type of memory.

11. The hardware device of claim 8 , wherein the occurrence table comprises a plurality of rows, and a number of the plurality of rows equals a number of bps in the sequence of bps in the reference genome sequence.

12. The hardware device of claim 11 , wherein a row of the occurrence table comprises 4 entries of occurrence numbers corresponding to characters A, C, G, and T, respectively.

13. The hardware device of claim 12 , the operations further comprising:

initializing a top pointer to 0;

initializing a bottom pointer to a size of the reference genome sequence, wherein each of the top pointer and bottom pointer points to an entry in the occurrence table; and

determining the first part of the occurrence table based on top new =count (char)+occurrence (top old , char) and bottom new =count (char)+occurrence (bottom old , char), wherein top new is a new value of the top pointer, top old is an old value of the top pointer, bottom new is a new value of the bottom pointer, bottom old is an old value of the bottom pointer, count (char) is a total count of characters that are smaller than character char, and occurrence (x, y) is an entry in the occurrence table indexed by row x and column y.

14. A non-transitory computer-readable medium having instructions stored thereon that, when executed by at least one processing unit of a hardware device comprising memory that includes a first type and a second type, cause the at least one processing unit to perform operations comprising:

receiving a count table and an occurrence table for a reference genome sequence generated using a Burrows Wheeler Transform (BWT) algorithm, wherein the reference genome sequence comprises a sequence of base pairs (bps);

determining a size of a first part of the occurrence table based on a size of the first type of memory and a minimum number of bytes in the first type of memory, the minimum number of bytes in the first type of memory based on a number of bps of short reads (SRs) to be processed using the first type of memory;

storing the count table and the occurrence table in the memory, wherein the first part of the occurrence table is stored in the first type of memory and a second part of the occurrence table is stored in the second type of memory, wherein a first memory access time for accessing the first part of the occurrence table in the first type of memory is less than a second memory access time for accessing the second part of the occurrence table stored in the second type of memory;

receiving a short read (SR) of an input genome sample sequence comprising a first number of bps and a second number of bps; and

performing alignment of the SR of the input genome sample sequence against the reference genome sequence to generate seeds using the count table and the occurrence table, wherein the first part of the occurrence table stored in the first type of memory comprises n levels of entries, each entry of an i-th level of the n levels of entries has a

1

4

i

memory access probability during the performing the alignment, 1≤i≤n, and the n levels of entries of the first part of the occurrence table have the highest memory access probabilities among all entries of the occurrence table, the performing comprising:

 performing alignment of the first number of bps in the SR of the input genome sample sequence against the sequence of bps of the reference genome sequence using the first part of the occurrence table stored in the first type of memory; and

performing alignment of the second number of bps in the SR of the input genome sample sequence against the sequence of bps of the reference genome sequence using the second part of the occurrence table stored in the second type of memory.

15. The non-transitory computer-readable medium of claim 14 , wherein the size of the first part of the occurrence table is determined based on

s

=

(

∑

i

=

0

n

-

1

4

i

+

1

)

×

4

,

where s is the minimum number of bytes in the first type of memory, n is the number of the bps of the SRs to be processed using the first type of memory.

16. The non-transitory computer-readable medium of claim 14 , wherein the size of the first part of the occurrence table is determined based on

s

=

(

∑

i

=

0

n

-

1

4

i

+

1

)

×

4

×

2

,

where s is the minimum number of bytes in the first type of memory, n is the number of the bps of the SRs to be processed using the first type of memory.

17. The non-transitory computer-readable medium of claim 14 , wherein the occurrence table comprises a plurality of rows, and a number of the plurality of rows equals a number of bps in the sequence of bps of the reference genome sequence.

18. The non-transitory computer-readable medium of claim 17 , wherein a row of the occurrence table comprises 4 entries of occurrence numbers corresponding to characters A, C, G, and T, respectively.

19. The non-transitory computer-readable medium of claim 18 , the operations further comprising:

initializing a top pointer to 0;

initializing a bottom pointer to a size of the genome reference sequence, wherein each of the top pointer and bottom pointer points to an entry in the occurrence table; and

determining the first part of the occurrence table based on top new =count (char)+occurrence (top old , char) and bottom new =count (char)+occurrence (bottom old , char), wherein top new is a new value of the top pointer, top old is an old value of the top pointer, bottom new is a new value of the bottom pointer, bottom old is an old value of the bottom pointer, count (char) is a total count of characters that are smaller than character char, and occurrence (x, y) is an entry in the occurrence table indexed by row x and column y.

20. The non-transitory computer-readable medium of claim 14 , wherein the count table comprises four entries corresponding to four different bp types, each entry of the count table comprising a total count of bps in the reference genome sequence that are smaller than a bp corresponding to the entry, and wherein the occurrence table comprises a plurality of rows and four columns, the four columns corresponding to the four different bp types, each entry of the occurrence table indexed by a row index and a column index comprises a count of a bp corresponding to the column index up to the row index.

Assignments (1)

Continuity (3)

References Cited (21)