Granted Patent B2

US 10,460,829 · App. 15/006,391 · Granted Oct 29, 2019

Inventor: Benjamin Murray (London, GB)

Assignee: SEVEN BRIDGES GENOMICS INC.

G16B35/00G16B20/00G16C20/60G16H10/60H03M7/60

Abstract

Claims (40)

1. A method of encoding variation data for a population, comprising using at least one computer hardware processor connected to at least one non-transitory computer-readable storage medium to perform:

receiving information describing genetic variation of a population of individuals, the information comprising a plurality of variable sites within a reference genome of the population and a plurality of genotypes of a plurality of individuals in the population with respect to those variable sites;

determining a prevalence for each variable site within the population, wherein the prevalence comprises the frequency at which alternative alleles of a given variable site occur in the population;

selecting an encoding strategy for each of the plurality of variable sites based on the determined prevalence of each variable site across the population, wherein if the prevalence for a variable site is less than 10%, less than 5%, less than 1%, or less than 0.1% of the population, the encoding strategy is a compression encoding strategy, and otherwise the encoding strategy is a bit field encoding strategy;

encoding the information according to the encoding strategy selected for each of the plurality of variable sites; and

storing the encoded information in the at least one non-transitory computer-readable storage medium.

2. The method of claim 1 , wherein the bit field encoding strategy comprises encoding each genotype as a minimal number of bits.

3. The method of claim 1 , wherein the compression encoding strategy is a run length encoding strategy.

4. The method of claim 3 , wherein the run length encoding strategy comprises:

for each variable site of the plurality of variable sites:

selecting the genotypes of the plurality of individuals with respect to that variable site, the genotypes comprising a sequence of symbols, the sequence of symbols comprising alternating runs of adjacent identical symbols;

determining, for each run of adjacent identical symbols, a run length; and

encoding the sequence of symbols as a plurality of symbols and run lengths.

5. The method of claim 4 , wherein encoding each run length of said runs of adjacent identical symbols uses a variable bit format, wherein the variable bit format comprises a number of bits sufficient to encode the symbol and an associated run length.

6. The method of claim 5 , wherein the variable bit format comprises 1 bit to encode a symbol and 3 bits to encode an associated run length.

7. The method of claim 1 , wherein encoding the information according to the selected encoding strategy comprises:

identifying a set of variable sites having alleles that occur together with a level of statistical significance;

determining each actual combination of alleles for the identified set of variable sites;

assigning a unique value to each actual combination of alleles; and

encoding the set of variable sites using the assigned unique values.

8. The method of claim 7 , wherein identifying a set of variable sites having alleles that occur together with a level of statistical significance comprises identifying a set of variable sites having alleles that exhibit fewer combinations than would be expected by chance.

9. The method of claim 1 , wherein encoding the information according to the selected bit field encoding strategy comprises:

identifying a set of variable sites having alleles that occur together with a level of statistical significance;

determining each actual combination of alleles for the identified set of variable sites;

assigning a unique value to each actual combination of alleles; and

encoding the set of variable sites using the assigned unique values and the bit field encoding strategy.

10. A system for encoding variation data for a population, comprising:

a memory, storing information describing genetic variation of a population of individuals, the information comprising a plurality of variable sites within a reference genome of the population and a plurality of genotypes of the plurality of individuals in the population with respect to those variable sites; and

a processor configured to:

for each variable site in the population:

determine the variability of the variable site in the population; and

encode the information associated with the variable site based on the frequency of alternate alleles of the variable site occurring in the population, wherein a variable site having more than 10%, more than 5%, more than 1%, or more than 0.1% frequency of alternate alleles is encoded using a bit field encoding strategy, and otherwise the variable site is encoded using a run length encoding strategy; and

store the encoded information in the memory.

11. A method of encoding variation data for a population, comprising using at least one computer hardware processor connected to at least one non-transitory computer-readable storage medium to perform:

receiving information describing genetic variation of a population of individuals, the information comprising a plurality of variable sites within a reference genome of the population and a plurality of genotypes of a plurality of individuals in the population with respect to those variable sites; and

for each variable site:

calculating a first number of bits required to encode the variable site and its associated genotypes according to a run length encoding strategy, wherein calculating the first number of bits required to encode the variable site according to the run length encoding strategy comprises calculating the number of run length entries required to encode the variable site;

calculating a second number of bits required to encode the variable site and its associated genotypes according to a bit field encoding strategy;

comparing the first number of bits and second number of bits; and

encoding, based on the comparison, the variable site and its corresponding genotypes using either the run length encoding strategy or the bit field encoding strategy, wherein the variable site is encoded using the bit field encoding strategy if the first number of bits exceeds the second number of bits, and otherwise the variable site is encoded using the run length encoding strategy.

Assignments (12)

Continuity (1)