# US 10,373,707 B2 · Algebraic phasing of polyploids > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,373,707 B2 - Document ID: US10373707B2 - Status: Granted - Kind: B2 - Application number: 16/236,866 - Filed: 2018-12-31 - Published: 2019-05-09 - Granted: 2019-08-06 - Earliest claimed: 2017-05-17 - Assignees: International Business Machines Corporation - Applicants: International Business Machines Corporation - Inventors: Laxmi P. Parida; Filippo Utro - Web page: https://patentgrep.com/patent/US10373707B2 ## CPC - G16B 30/20: Sequence assembly - G06F 17/16: Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} - G16B 20/00: ICT specially adapted for functional genomics or proteomics, e.g. genotype-phenotype associations - G16B 30/00: ICT specially adapted for sequence analysis involving nucleotides or amino acids - G16B: BIOINFORMATICS, i.e. INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR GENETIC OR PROTEIN-RELATED DATA PROCESSING IN COMPUTATIONAL MOLECULAR BIOLOGY - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Embodiments of the present invention include method, systems and computer program products for algebraic phasing of polyploids. Aspects of the invention include receiving a matrix including a set of two or more single-nucleotide poloymorphisms (SNPs) for two or more sample organisms. Each row of the matrix is set to a ploidy based on a number of ploidies present in the two or more sample organisms. Each allele in the set of two or more SNPs is represented as a binary number. A set of algebraic rules is received, wherein the set of algebraic rules include an algebraic phasing algorithm. And the set of algebraic rules are applied to the matrix to determine a haplotype of a parent of the two or more sample organisms. ## Claims ### Claim 1 A computer-implemented method for applying algebraic rules to single-nucleotide polymorphisms (SNPs), the method comprising: receiving, by a processor, a matrix comprising a set of rows and a set of columns, the matrix representing a set of two or more SNPs for two or more sample organisms; setting each row in the set of rows to a ploidy based on a number of ploidies present in the two or more sample organisms; receiving a set of algebraic rules, wherein the set of algebraic rules comprises an algebraic phasing algorithm; and applying the set of algebraic rules to the matrix to determine a haplotype of a parent of the two or more sample organisms. ### Claim 2 (depends on 1) The method of claim 1, wherein each of the two or more sample organisms is a polyploid. ### Claim 3 (depends on 1) The method of claim 1, wherein the ploidy for each of the two or more sample organisms is equal. ### Claim 4 (depends on 1) The method of claim 1 further comprising representing each allele in the set of two or more SNPs as a zero for a minor allele. ### Claim 5 (depends on 1) The method of claim 1, further comprising representing each allele in the set of two or more SNP as one for a major allele. ### Claim 6 (depends on 1) The method of claim 1, wherein the algebraic phasing algorithm comprises: a row intersect operation for a first row and a second row in the matrix to determine a minimum ploidy value; performing a relaxed intersection on the first row and the second row, wherein the relaxed intersection is defined by the minimum ploidy value; and creating a first new row for the matrix based at least in part on a result of the relaxed intersection on the first row and the second row. ### Claim 7 (depends on 6) The method of claim 6, wherein the algebraic phasing algorithm further comprises: performing a row difference operation for the first row and the first new row to create a second new row; performing a row difference operation for the second row and the first new row to create a third new row; replacing the first row with the second new row; and replacing the second row with the third new row. ### Claim 8 (depends on 1) The method of claim 1, wherein the algebraic phasing algorithm comprises: selecting a row in the matrix with a ploidy greater than two; extracting a homozygous diploid row from the row; replace the selected row in the matrix with two rows comprising: a first row comprising an intersection of the homozygous diploid row and the selected row, wherein a ploidy of the first row is the ploidy of the selected row minus two; and a second row comprising a difference of the selected row and the homozygous diploid row. ### Claim 9 (depends on 1) The method of claim 1, wherein the set of rules are applied to the matrix until all rows of the matrix have a ploidy of one. ### Claim 10 (depends on 1) The method of claim 1, wherein the set of rules are applied to the matrix until no change occurs between one iteration of the algorithm and a next iteration of the algorithm. ### Claim 11 A computer system for applying algebraic rules to single-nucleotide polymorphisms (SNPs), the computer system including a processor communicatively coupled to a memory, the processor configured to: receive a matrix comprising a set of rows and a set of columns, the matrix representing a set of two or more SNPs for two or more sample organisms; set each row in the set of rows to a ploidy based on a number of ploidies present in the two or more sample organisms; receive a set of algebraic rules, wherein the set of algebraic rules comprises an algebraic phasing algorithm; and apply the set of algebraic rules to the matrix to determine a haplotype of a parent of the two or more sample organisms. ### Claim 12 (depends on 11) The system of claim 11, wherein each of the two or more sample organisms is a polyploid. ### Claim 13 (depends on 11) The system of claim 11, wherein the algebraic phasing algorithm comprises: a row intersect operation for a first row and a second row in the matrix to determine a minimum ploidy value; performing a relaxed intersection on the first row and the second row, wherein the relaxed intersection is defined by the minimum ploidy value; and creating a first new row for the matrix based at least in part on a result of the relaxed intersection on the first row and the second row. ### Claim 14 (depends on 13) The system of claim 13, wherein the algebraic phasing algorithm further comprises: performing a row difference operation for the first row and the first new row to create a second new row; performing a row difference operation for the second row and the first new row to create a third new row; replacing the first row with the second new row; and replacing the second row with the third new row. ### Claim 15 (depends on 11) The system of claim 11, wherein the algebraic phasing algorithm comprises: selecting a row in the matrix with a ploidy greater than two; extracting a homozygous diploid row from the row; replace the selected row in the matrix with two rows comprising: a first row comprising an intersection of the homozygous diploid row and the selected row, wherein a ploidy of the first row is the ploidy of the selected row minus two; and a second row comprising a difference of the selected row and the homozygous diploid row. ### Claim 16 A computer program product for applying algebraic rules to single-nucleotide polymorphisms (SNPs), the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a processor to cause the processor to perform: receiving, by the processor, a matrix comprising a set of rows and a set of columns, the matrix representing a set of two or more SNPs for two or more sample organisms; setting each row in the set of rows to a ploidy based on a number of ploidies present in the two or more sample organisms; receiving a set of algebraic rules, wherein the set of algebraic rules comprises an algebraic phasing algorithm; and applying the set of algebraic rules to the matrix to determine a haplotype of a parent of the two or more sample organisms. ### Claim 17 (depends on 16) The computer program product of claim 16, wherein the algebraic phasing algorithm comprises: a row intersect operation for a first row and a second row in the matrix to determine a minimum ploidy value; performing a relaxed intersection on the first row and the second row, wherein the relaxed intersection is defined by the minimum ploidy value; and creating a first new row for the matrix based at least in part on a result of the relaxed intersection on the first row and the second row. ### Claim 18 (depends on 17) The computer program product of claim 17, wherein the algebraic phasing algorithm further comprises: performing a row difference operation for the first row and the first new row to create a second new row; performing a row difference operation for the second row and the first new row to create a third new row; replacing the first row with the second new row; and replacing the second row with the third new row. ### Claim 19 (depends on 16) The computer program product of claim 16, wherein the algebraic phasing algorithm comprises: selecting a row in the matrix with a ploidy greater than two; extracting a homozygous diploid row from the row; replace the selected row in the matrix with two rows comprising: a first row comprising an intersection of the homozygous diploid row and the selected row, wherein a ploidy of the first row is the ploidy of the selected row minus two; and a second row comprising a difference of the selected row and the homozygous diploid row. ### Claim 20 (depends on 16) The computer program product of claim 16, wherein the set of rules are applied to the matrix until all rows of the matrix have a ploidy of one.