Memory Allocation to Optimize Computer Operations of Seeding for Burrows Wheeler Alignment

A hardware device comprising:

• at least one processor unit;
• memory including a first type of memory;
• a non-transitory computer readable storage medium storing programming for execution by the at least one processor unit, the programming including instructions to:
• receive 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);
• determine a size of a first part of the occurrence table based on a size of the first type of memory and a number of bps of short reads (SRs) to be processed using the first type of memory;
• store 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;
• receive a short read (SR) of an input genome sample sequence comprising a first number of bps and a second number of bps;
• and
• perform 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, 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.

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 of memory, cause the at least one processing unit to perform operations, the 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 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;
• 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, 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.