Granted Patent B1

US 12,322,477 · App. 17/126,039 · Granted Jun 3, 2025

Inventor: John Hayward (Wheaton, IL)

G16B20/00G16B30/00G16B50/00

Abstract

Claims (34)

1. A computer-implemented method for determining the genetic relatedness of multiple individuals of a particular species with fewer computational steps by a processor, comprising executing on a processor the steps of:

obtaining from a computer memory digital files of a first deoxyribonucleic acid (DNA) sequence information of a first individual and a second DNA sequence information of a second individual, each of said first and second DNA sequence information including base pair data for a set of single nucleotide polymorphism (SNP) loci;

said processor organizes the base pair data of each of said first and second DNA sequence information, wherein the base pair data present at each of said set of SNP loci are transformed into a standardized SNP data sequence format according to a digital SNP loci template having a pre-determined set of SNP loci, wherein a first digital file comprising a first standardized SNP sequence from said first DNA sequence and a second digital file comprising second standardized SNP sequence from said second DNA sequence are created, wherein each bit in said first standardized SNP sequence and said second standardized SNP sequence represents a base pair at one of said pre-determined set of SNP loci;

said processor divides the first standardized SNP sequence into a first set of digital data blocks and the second standardized SNP sequence into a second set of digital data blocks, each of said data blocks having a pre-determined bit length that is equal to a bit word length of said processor; and

said processor compares said first set of digital blocks with said second set of digital blocks,

wherein said first set of digital data blocks is aligned with said second set of digital data blocks according to said digital SNP loci template, a first predetermined sequence of digital data blocks of said first set of digital data blocks represents a first comparison segment and a first predetermined sequence of said second set of data blocks represents a second comparison segment, wherein the first comparison segment and said second comparison segment have a pre-determined segment length, and said processor performs the comparison of the first comparison segment and the second comparison segment in a stepwise block-by-block process beginning at a last digital data block of each of the first and second comparison segments, working backwards toward a first digital data block of each of the first and second comparison segments until

(1) a mismatch between the first and second comparison segments at an SNP locus is found or

(2) the entire lengths of the first and second comparison segments are compared with no mismatches at the SNP loci found,

wherein aligned digital data blocks are compared in a single computational step by the processor, and in the event a mismatch is identified in the comparison of the first comparison segment and said second comparison segment, a third comparison segment of said pre-determined segment length is identified starting from the last digital data block free from mismatches between the SNP loci of the first and second comparison segments and extending for said pre-determined segment length along said first set of digital data blocks, and a fourth comparison segment of said pre-determined segment length is identified starting from the last digital data block free from mismatches and extending for said pre-determined segment length along said second set of digital data blocks, and

said processor performing a comparison of the third comparison segment and the fourth comparison segment in a stepwise block-by-block process beginning at a last digital data block of each of the third and fourth comparison segments working backwards toward a first digital data block of each of the third and fourth comparison segments until

(1) a mismatch at an SNP locus between the third and fourth comparison segments is found or

(2) the entire lengths of the third and fourth comparison segments are compared with no mismatches at the SNP loci.

2. The method of claim 1 , wherein said mismatch between base pairs of the first and second comparison segments occurs when they have opposite base pairs at a particular SNP locus.

3. The method of claim 1 , wherein said first and second comparison segments include a pre-determined cM length requirement, defining said pre-determined segment length.

4. The method of claim 1 , wherein each of the first and second DNA sequence information includes a single bit representing both sets of base pairs at each SNP locus in the digital SNP loci template for the corresponding individual.

5. The method of claim 4 , further comprising creating a second bit corresponding to each SNP locus in the digital SNP loci template that encodes whether the sets of base pairs at said SNP locus are homozygous or heterozygous.

6. The method of claim 1 , further converting a predetermined cM length requirement into a corresponding number of data blocks representing a number of SNP loci to satisfy the said predetermined cM length requirement, wherein said first comparison segment, said second comparison segment, said third comparison segment, and said fourth comparison segment each have a length that is equal to said predetermined cM length requirement.

7. A computer-implemented method for determining the genetic relatedness of multiple individuals executing machine-readable instructions on a general purpose computer, comprising:

obtaining first digital deoxyribonucleic acid (DNA) sequence data set of a first individual and second digital DNA sequence data set of a second individual from a computer memory;

a processor of said general purpose computer transforms base pair data at single nucleotide polymorphism (SNP) loci in the first digital DNA sequence data set to generate a first digital file comprising a first digital comparison sequence according to an SNP loci sequence template, wherein each bit in said first digital comparison sequence represents a homozygous set of base pairs at one of said SNP loci;

said processor transforms base pair data at SNP loci data in the second digital DNA sequence data to generate a second digital file comprising a second digital comparison sequence according to said SNP loci sequence template, wherein each bit in said second digital comparison sequence represents a homozygous set of base pairs at one of said SNP loci;

said processor divides the first comparison sequence into a first set of digital data blocks and the second comparison sequence into a second set of digital data blocks, wherein the number of bits in each digital data block is equal to the bit word length of a computer processor and each bit in each digital data block represents an identity of a set of homozygous base pairs at an SNP locus in the SNP loci sequence template; comparing a first set of digital data blocks from said first comparison sequence with a second set of digital data blocks from said second comparison sequence to identify mismatches in base pair data at SNP loci, wherein said first set of digital data blocks and said second digital data blocks are aligned according to said SNP loci sequence template and have a predetermined length that has a number of SNP loci required to satisfy a pre-determined centimorgan (cM) length, wherein said comparison begins between a last data block of said first set of digital data blocks and a last data block of said second set of digital data blocks and proceeds in a retrograde progression from the last data digital blocks until either a mismatch occurs between the first and second sets of digital data blocks at an SNP locus or the comparison does not identify a mismatch at any SNP locus; and

said processor determines whether the SNP loci of the first and second sets of digital data blocks match by comparing the bits between two corresponding digital data blocks of said first and second sets of digital data blocks in a single computational operation.

8. A digital computing system having a processor and, a computer-readable memory, and having software enabling said digital computing system to convert and compare digital DNA sequence data set from multiple individuals to determine the genetic relatedness of the multiple individuals with fewer computational operations by said processor, comprising:

said processor operable to:

obtain from a computer-readable medium first and second digital deoxyribonucleic acid (DNA) sequence data sets of a first individual and a second individual, respectively, said first and second digital DNA sequence data sets including base pair data for single nucleotide polymorphism (SNP) loci of said first and second individuals;

create first and second digital comparison sequences each comprising said base pair data at said SNP loci from said first and second digital DNA sequence data sets according to a digital SNP sequence template, wherein each bit in the first and second comparison sequences represents an identity of a base pair at an SNP locus;

divide the first comparison sequence into a first set of digital data blocks and the second comparison sequence into a second set of digital data blocks, each of said data blocks having a pre-determined bit length equal to a bit word length of said processor; and

compare said first comparison sequence of said first individual with said second comparison sequence of said second individual in a stepwise block-by-block process beginning at a last digital data block of each of the first and second sets of digital data blocks and working backwards toward a first digital data block of each of the first and second sets of digital data blocks, wherein

a. a comparison of one digital data block of said first set of digital data blocks and one digital block of said second set of digital data blocks is completed in a single computational operation by the processor, and

b. said first set of digital data blocks is aligned with said second set of digital data blocks according to said digital SNP sequence template, such that bit values at the SNP loci in the one digital data block of said first set of digital data blocks and the one digital data block of said second set of digital data blocks are directly compared during said single computational operation.

9. The method of claim 1 , said digital file of a first DNA sequence information is obtained from a first DNA kit and said second DNA sequence information is from a second DNA kit, wherein said first DNA kit and second DNA kit have partially differing sets of SNP loci, and said first DNA sequence information and said second DNA sequence information are organized according to said SNP loci template to pre-align the data to allow the first DNA sequence information and said second DNA sequence information to be compared for matching segments.

10. The method of claim 7 , said first digital DNA sequence data set is obtained from a first DNA kit and said second digital DNA sequence data set is from a second DNA kit, wherein said first DNA kit and second DNA kit have partially differing sets of SNP loci, and said first digital DNA sequence data set and said second digital DNA sequence data set are organized according to said SNP sequence template to pre-align the data to allow the first DNA sequence information and said second DNA sequence information to be compared for matching segments.

11. The method of claim 8 , said first digital DNA sequence data set is obtained from a first DNA kit and said second digital DNA sequence data set is from a second DNA kit, wherein said first DNA kit and second DNA kit have partially differing sets of SNP loci, and said first digital DNA sequence data set and said second digital DNA sequence data set are organized according to said digital SNP sequence template to pre-align the data to allow the first DNA sequence information and said second DNA sequence information to be compared for matching segments.

Continuity (2)

References Cited (57)