Lossless compression of the enumeration space of founder line crosses

• US 9,041,566 B2
• Filed: 08/30/2013
• Issued: 05/26/2015
• Est. Priority Date: 08/30/2013
• Status: Expired due to Fees

• Current Assignee: GlobalFoundries, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Haws, David C., Parida, Laxmi P.
• Primary Examiner(s): NGUYEN, LINH V
• Application Number:
  US14/014,635
• Publication Number:
  US 20150061903A1
• Time in Patent Office: 634 Days
• Field of Search: 341/65, 341/67, 341/78, 341/79, 706 13- 44
• US Class Current: 341/79
• CPC Class Codes: G16B 10/00 ICT specially adapted for evolutionary bioinformatics, e.g. phylogenetic tree construction or analysis
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
• CPC Class Codes: H03M 7/4006 Conversion to or from arithmetic code

Abstract

Various embodiments provide lossless compression of an enumeration space for genetic founder lines. In one embodiment, an input comprising a set of genetic founder lines and a maximum number of generations G is obtained. A set of genetic crossing templates of a height h is generated. A determination is made if at least a first genetic crossing template in the set of genetic crossing templates is redundant with respect to a second genetic crossing template in the set of genetic crossing templates. Based on the at least first genetic crossing template being redundant is redundant with respect to the second genetic crossing template, the at least first genetic crossing template is removed from the set of genetic crossing templates. This process of removing the at least first genetic crossing template from the set of genetic crossing templates the redundant creates an updated set of genetic crossing templates.

Claims

1. A computer implemented method for providing lossless compression of an enumeration space for genetic founder lines, the computer implemented method comprising

obtaining an input comprising a set of genetic founder lines and a maximum number of generations G, wherein the following is iteratively performed for h=0, 1, . . . , G:

generating a set of genetic crossing templates of a height h, wherein each of the set of genetic crossing templates represents a binary tree, the binary tree comprising h levels representing a given generation, each of the h levels comprising a set of nodes wherein when h>

0 one or more of the h levels of the binary tree correspond to at least one cross between at least one pair of nodes in the set of nodes,

wherein each of the set of genetic crossing templates comprises an array of h entries, wherein a position of an entry within the array corresponds to a level in the binary tree represented by the genetic crossing template, each of the h entries in the array comprising a value indicating a number of leaf nodes in the set of nodes for the level in the binary tree; and

determining if at least a first genetic crossing template in the set of genetic crossing templates is redundant with respect to a second genetic crossing template in the set of genetic crossing templates; and

based on the at least first genetic crossing template being redundant, removing the at least first genetic crossing template from the set of genetic crossing templates, the removing creating an updated set of genetic crossing templates.

2. The computer implemented method of claim 1, wherein the determining comprises:

comparing the array of the at least first genetic crossing template with the array of the second genetic crossing template;

determining, based on the comparing, if the value within each entry of the array for the at least first genetic crossing template matches the value within each corresponding entry of the array for the second genetic crossing template; and

determining that the at least first genetic crossing template is redundant with respect to the second genetic crossing template based on the value within each entry of the array for the at least first genetic crossing template matching the value within each corresponding entry of the array for the second genetic crossing template.

3. The computer implemented method of claim 1, wherein at least one of the set of genetic crossing templates of height h is generated by combining a previously generated genetic crossing template of a height less than h with another previously generated genetic crossing template of a height less than h.

4. The computer implemented method of claim 1, further comprising:

generating a set of genetic crossing instances for each genetic crossing template in the updated set of genetic crossing templates based on the set of founder lines, wherein each genetic crossing instance in the set of genetic crossing instances is the binary tree represented by the genetic crossing template in the updated set of genetic crossing templates with leaf nodes at each of the h levels labeled with one of the set of genetic founder lines, wherein the set of genetic crossing instances comprises a genetic crossing instance for each of a plurality of different leaf node labeling variations based on the set of genetic founder lines.

5. The computer implemented method of claim 4, further comprising:

determining if at least a first genetic crossing instance in the set of genetic crossing instances is redundant with respect to a second genetic crossing instance in the set of genetic crossing instances; and

based on the at least first genetic crossing instance being redundant, removing the at least first genetic crossing instance from the set of genetic crossing instances, the removing creating an updated set of genetic crossing instances.

6. The computer implemented method of claim 5, wherein the determining comprises:

comparing the binary tree of the at least a first genetic crossing instance with the binary tree of the second genetic crossing instance;

determining, based on the comparing, if the label of each leaf node in the binary tree of the at least first genetic crossing instance matches a label of a corresponding leaf node in the binary tree of the second genetic crossing instance; and

determining that the at least first genetic crossing instance is redundant with respect to the second genetic crossing instance based on the label of each leaf node in the binary tree of the at least first genetic crossing instance matching a label of a corresponding leaf node in the binary tree of the second genetic crossing instance.

7. The computer implemented method of claim 4, wherein at least one of the set of genetic crossing instances is generated by combining each of a previously generated set of crossing instances of a given genetic crossing template in the update set of genetic crossing templates with each of a previously generated set of crossing instances of at least one other genetic crossing template in the update set of genetic crossing templates.