# US 2019/0171625 A1 · Quality score compression for improving downstream genotyping accuracy

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2019/0171625 A1
- Document ID: US20190171625A1
- Status: Published application
- Kind: A1
- Application number: 16/267,778
- Filed: 2019-02-05
- Published: 2019-06-06
- Earliest claimed: 2014-04-26
- Inventors: Bonnie Berger Leighton; Deniz Yorukoglu; Yun William Yu; Jian Peng
- Web page: https://patentgrep.com/patent/US20190171625A1

## CPC

- G06F 16/1744: {using compression, e.g. sparse files}
- G16B 30/00: ICT specially adapted for sequence analysis involving nucleotides or amino acids
- G16B 30/10: Sequence alignment; Homology search
- G16B 50/00: ICT programming tools or database systems specially adapted for bioinformatics
- G16B 50/50: Compression of genetic data
- G16C 10/00: Computational theoretical chemistry, i.e. ICT specially adapted for theoretical aspects of quantum chemistry, molecular mechanics, molecular dynamics or the like
- G16C 99/00: Subject matter not provided for in other groups of this subclass
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G16B: BIOINFORMATICS, i.e. INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR GENETIC OR PROTEIN-RELATED DATA PROCESSING IN COMPUTATIONAL MOLECULAR BIOLOGY
- G16C: COMPUTATIONAL CHEMISTRY; CHEMOINFORMATICS; COMPUTATIONAL MATERIALS SCIENCE

## Abstract

This disclosure provides for a highly-efficient and scalable compression tool that compresses quality scores, preferably by capitalizing on sequence redundancy. In one embodiment, compression is achieved by smoothing a large fraction of quality score values based on k-mer neighborhood of their corresponding positions in read sequences. The approach exploits the intuition that any divergent base in a k-mer likely corresponds to either a single-nucleotide polymorphism (SNP) or sequencing error; thus, a preferred approach is to only preserve quality scores for probable variant locations and compress quality scores of concordant bases, preferably by resetting them to a default value. By viewing individual read datasets through the lens of k-mer frequencies in a corpus of reads, the approach herein ensures that compression “lossiness” does not affect accuracy in a deleterious way.

## Claims

### Claim 1

Apparatus, comprising:
a hardware processor;
computer memory holding computer program instructions executed by the processor to process genomic data, the computer program instructions comprising program code configured to:
receive, as a dictionary, a set of data comprising commonly-occurring k-mers extracted from a read dataset;
compress NGS quality scores in a given read dataset by identifying k-mers from each read within a given mismatch distance from other k-mers in the dictionary to generate compressed quality scores, wherein the dictionary has the property that any given read dataset is covered from k-mers within a given Hamming distance; and
provide the compressed quality scores to a genotyping analysis pipeline.

### Claim 2 (depends on 1)

The apparatus as described in claim 1 wherein the program code configured to compress the NGS quality scores comprises program code further configured to:
set to a default value any quality score value corresponding to a position that is concordant with at least one supporting k-mer; and
save the quality score value at any position that is divergent from all supporting k-mers.

### Claim 3 (depends on 1)

The apparatus as described in claim 1 wherein the read dataset is a read dataset is a dataset associated with a population.

### Claim 4 (depends on 1)

The apparatus as described in claim 1 wherein the program code is further configured to generate the dictionary.

### Claim 5 (depends on 1)

The apparatus as described in claim 1 wherein the program code configured to compress NGS quality scores comprises program code further configured to:
break a read sequence in the read dataset into overlapping k-mers;
with respect to the read sequence, identify k-mers in the dictionary that are within a given mismatch distance from supporting k-mers; and
annotate a position different from a dictionary k-mer as a possible variant unless covered by a dictionary k-mer corresponding to a different supporting k-mer.

### Claim 6 (depends on 5)

The apparatus as described in claim 5 wherein the program code is configured to preserve all mismatches when two dictionary k-mers correspond to the same supporting k-mer unless a mismatch portion is covered by a dictionary k-mer corresponding to a different supporting k-mer.

### Claim 7 (depends on 6)

The apparatus as described in claim 6 wherein the program code is further configured to:
smooth the quality scores; and
set positions exhibiting a given quality value to a default value while retaining scores of uncovered and possible variant loci.

### Claim 8 (depends on 1)

The apparatus as described in claim 1 wherein compression of the NGS quality scores is lossy.

### Claim 9 (depends on 1)

The apparatus as described in claim 1 wherein the program code is further configured to perform an additional compression of the compressed quality scores.

### Claim 10 (depends on 1)

The apparatus as described in claim 1 wherein the program code is further configured to generate the dictionary using a counting algorithm and a collection of hash buckets.
