Systems and methods for encoding genetic variation for a population

• US 10,460,829 B2
• Filed: 01/26/2016
• Issued: 10/29/2019
• Est. Priority Date: 01/26/2016
• Status: Active Grant

• Current Assignee: Seven Bridges Genomics, Inc.
• Original Assignee: Seven Bridges Genomics, Inc.
• Inventors: Murray, Benjamin
• Primary Examiner(s): Dunston, Jennifer
• Application Number:
  US15/006,391
• Publication Number:
  US 20170211205A1
• Time in Patent Office: 1,372 Days
• CPC Class Codes: G16B 20/00 ICT specially adapted for functional genomics or proteomics, e.g. genotype-phenotype associations
• CPC Class Codes: G16B 20/20 Allele or variant detection, e.g. single nucleotide polymorphism [SNP] detection
• CPC Class Codes: G16B 20/40 Population genetics; Linkage disequilibrium
• CPC Class Codes: G16B 35/00 ICT specially adapted for in silico combinatorial libraries of nucleic acids, proteins or peptides
• CPC Class Codes: G16C 20/60 In silico combinatorial chemistry
• CPC Class Codes: G16H 10/60 for patient-specific data, e.g. for electronic patient records
• CPC Class Codes: H03M 7/60 General implementation details not specific to a particular type of compression

Abstract

In one embodiment, a method of encoding variation data for a population comprises receiving, by a variant encoding engine executing on a processor, information describing genetic variation of a population of individuals. The information comprises a plurality of variable sites within the reference genome of the population and the genotypes of a plurality of individuals in the population with respect to those variable sites. The method further comprises selecting an encoding strategy for the information based on the characteristics of the genetic variation across the population, and encoding the information according to the selected encoding strategy. In certain embodiments, selecting an encoding strategy may comprise determining the variability of a variable site within the population, and encoding information associated with the variable site based on the variability.

Claims

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.