# US 2015/0178446 A1 · Iterative clustering of sequence reads for error correction

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

- Number: US 2015/0178446 A1
- Document ID: US20150178446A1
- Status: Published application
- Kind: A1
- Application number: 14/574,914
- Filed: 2014-12-18
- Published: 2015-06-25
- Earliest claimed: 2013-12-18
- Assignees: Pacific Biosciences of California, Inc.
- Applicants: Pacific Biosciences of California, Inc.
- Inventors: Huei-Hun Tseng
- Web page: https://patentgrep.com/patent/US20150178446A1

## CPC

- G16B 40/30: Unsupervised data analysis
- G16B 30/00: ICT specially adapted for sequence analysis involving nucleotides or amino acids
- G16B 30/10: Sequence alignment; Homology search
- G16B 40/00: ICT specially adapted for biostatistics; ICT specially adapted for bioinformatics-related machine learning or data mining, e.g. knowledge discovery or pattern finding
- G16B: BIOINFORMATICS, i.e. INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR GENETIC OR PROTEIN-RELATED DATA PROCESSING IN COMPUTATIONAL MOLECULAR BIOLOGY

## Abstract

Exemplary embodiments provide methods and systems for iterative clustering of sequence reads for error correction. Aspects of the exemplary embodiment include receiving a set of sequence reads and associated quality values; grouping the sequence reads into a set of initial clusters based on sequence similarity; generating a cluster consensus for each of the initial clusters; iteratively improving the clustering based on the cluster consensus and the quality values associated with the sequence reads; and generating and outputting a final cluster consensus for each of the clusters.

## Claims

### Claim 1

A method for iterative clustering of sequence reads for error correction, the method performed at least one software component executing on at least one processor, comprising:
receiving a set of sequence reads and associated quality values;
grouping the sequence reads into a set of initial clusters based on sequence similarity;
generating a cluster consensus for each of the initial clusters;
iteratively improving the clustering based on the cluster consensus and the quality values associated with the sequence reads; and
generating and outputting a final cluster consensus for each of the clusters.

### Claim 2 (depends on 1)

The method of claim 1, wherein iteratively improving the clustering further comprises:
calculating a probability of each sequence read belonging to each cluster using the quality values;
reassigning individual sequence reads from one cluster to another cluster having a highest calculated probability; and
merging highly similar clusters.

### Claim 3 (depends on 2)

The method of claim 2, wherein calculating a probability of each sequence read belonging to each cluster using the quality values, further comprises:
aligning each of the sequence reads in each of the clusters to each of the cluster consensus;
responsive to a current sequence read not aligning to any of the cluster consensus with a sufficiently high percent of similarity, ignoring the sequence read for having a bad probability;
responsive to the current sequence read (S) aligning to one or more of the cluster consensus (C), calculating a probability of the current read belonging to each of the clusters given the cluster consensus and the quality values (QVs) for the current read:
Pr(Si|Cu, QVs(Si))

### Claim 4 (depends on 3)

The method of claim 3, wherein responsive to the QVs being unavailable, then calculating:
Pr(Si|Cu QVs(Si))=(θmatch)count(match) (⅓ θsub)count(sub) (⅓ θins)count(ins) (⅓ θdel)count(del),
where θ is the probability of a match of a substitution (sub), an insertion (ins), and a deletion (del), respectively.

### Claim 5 (depends on 2)

The method of claim 2, further comprising:
responsive to no alignment existing between any of the sequence reads and any of the clusters, considering the sequence reads orphans, and forming new clusters from the orphans.

### Claim 6 (depends on 5)

The method of claim 5, further comprising:
responsive to a new cluster having only one sequence read, randomly generating a random probability for each orphan node; and
responsive to random probability being smaller than a predefined threshold probability, reassigning the orphan to one of the clusters having a non-zero computed probability of membership for the orphan.

### Claim 7 (depends on 1)

The method of claim 1, wherein the sequence reads received comprise full-length long reads, and wherein the generating and outputting the final cluster consensus further comprises:
inputting non-full-length reads into a final polishing processes that generates the final cluster consensus.

### Claim 8 (depends on 7)

The method of claim 7, wherein the reads comprise full-length long reads range in length from 0.5 kb to 1, 2, 3, 5, 10, 15, 20 kb.

### Claim 9 (depends on 1)

The method of claim 1, wherein grouping the sequence reads into a set of initial clusters based on sequence similarity further comprises:
aligning the sequence reads to create aligned reads;
building similarity graphs using the aligned reads; and
finding maximal cliques using the similarity graphs.

### Claim 10 (depends on 9)

The method of claim 9, wherein finding maximal cliques comprises: non-deterministically partitioning the similarity graphs into non-overlapping maximal cliques.

### Claim 11

An executable software product stored on a computer-readable medium containing program instructions for iterative clustering of sequence reads for error correction, the program instructions executing on at least one processor, comprising:
receiving a set of sequence reads and associated quality values;
grouping the sequence reads into a set of initial clusters based on sequence similarity;
generating a cluster consensus for each of the initial clusters;
iteratively improving the clustering based on the cluster consensus and the quality values associated with the sequence reads; and
generating and outputting a final cluster consensus for each of the clusters.

### Claim 12 (depends on 11)

The executable software product of claim 11, wherein iteratively improving the clustering further comprises:
calculating a probability of each sequence read belonging to each cluster using the quality values;
reassigning individual sequence reads from one cluster to another cluster having a highest calculated probability; and
merging highly similar clusters.

### Claim 13 (depends on 12)

The executable software product of claim 12, wherein calculating a probability of each sequence read belonging to each cluster using the quality values, further comprises:
aligning each of the sequence reads in each of the clusters to each of the cluster consensus;
responsive to a current sequence read not aligning to any of the cluster consensus with a sufficiently high percent of similarity, ignoring the sequence read for having a bad probability;
responsive to the current sequence read (S) aligning to one or more of the cluster consensus (C), calculating a probability of the current read belonging to each of the clusters given the cluster consensus and the quality values (QVs) for the current read:
Pr(Si|Cu, QVs(Si))

### Claim 14 (depends on 13)

The executable software product of claim 13, wherein responsive to the QVs being unavailable, then calculating:
Pr(Si|Cu QVs(Si))=(θmatch)count(match) (⅓ θsub)count(sub) (⅓ θins)count(ins) (⅓ θdel)count(del),
where θ is the probability of a match of a substitution (sub), an insertion (ins), and a deletion (del), respectively.

### Claim 15 (depends on 12)

The executable software product of claim 12, further comprising:
responsive to no alignment existing between any of the sequence reads and any of the clusters, considering the sequence reads orphans, and forming new clusters from the orphans.

### Claim 16 (depends on 15)

The executable software product of claim 15, further comprising:
responsive to a new cluster having only one sequence read, randomly generating a random probability for each orphan node; and
responsive to random probability being smaller than a predefined threshold probability, reassigning the orphan to one of the clusters having a non-zero computed probability of membership for the orphan.

### Claim 17 (depends on 11)

The executable software product of claim 11, wherein the sequence reads received comprise full-length long reads, and wherein the generating and outputting the final cluster consensus further comprises:
inputting non-full-length reads into a final polishing processes that generates the final cluster consensus.

### Claim 18 (depends on 15)

The executable software product of claim 15, wherein the reads comprise full-length long reads range in length from 0.5 kb to 1, 2, 3, 5, 10, 15, 20 kb.

### Claim 19 (depends on 11)

The executable software product of claim 11, wherein grouping the sequence reads into a set of initial clusters based on sequence similarity further comprises:
aligning the sequence reads to create aligned reads;
building similarity graphs using the aligned reads; and
finding maximal cliques using the similarity graphs.

### Claim 20 (depends on 19)

The executable software product of claim 19, wherein finding maximal cliques comprises: non-deterministically partitioning the similarity graphs into non-overlapping maximal cliques.

### Claim 21

A system for iterative clustering of sequence reads for error correction, comprising:
a memory; and
a processor coupled to the memory configured to:
receiving a set of sequence reads and associated quality values;
grouping the sequence reads into a set of initial clusters based on sequence similarity;
generating a cluster consensus for each of the initial clusters;
iteratively improving the clustering based on the cluster consensus and the quality values associated with the sequence reads; and
generating and outputting a final cluster consensus for each of the clusters.

### Claim 22 (depends on 21)

The system of claim 21, wherein iteratively improving the clustering further comprises:
calculating a probability of each sequence read belonging to each cluster using the quality values;
reassigning individual sequence reads from one cluster to another cluster having a highest calculated probability; and
merging highly similar clusters.

### Claim 23 (depends on 22)

The system of claim 22, wherein calculating a probability of each sequence read belonging to each cluster using the quality values, further comprises:
aligning each of the sequence reads in each of the clusters to each of the cluster consensus;
responsive to a current sequence read not aligning to any of the cluster consensus with a sufficiently high percent of similarity, ignoring the sequence read for having a bad probability;
responsive to the current sequence read (S) aligning to one or more of the cluster consensus (C), calculating a probability of the current read belonging to each of the clusters given the cluster consensus and the quality values (QVs) for the current read:
Pr(Si|Cu, QVs(Si))

### Claim 24 (depends on 23)

The system of claim 23, wherein responsive to the QVs being unavailable, then calculating:
Pr(Si|Cu QVs(Si))=(θmatch)count(match) (⅓ θsub)count(sub) (⅓ θins)count(ins) (⅓ θdel)count(del),
where θ is the probability of a match of a substitution (sub), an insertion (ins), and a deletion (del), respectively.

### Claim 25 (depends on 22)

The system of claim 22, further comprising:
responsive to no alignment existing between any of the sequence reads and any of the clusters, considering the sequence reads orphans, and forming new clusters from the orphans.

### Claim 26 (depends on 25)

The system of claim 25, further comprising:
responsive to a new cluster having only one sequence read, randomly generating a random probability for each orphan node; and
responsive to random probability being smaller than a predefined threshold probability, reassigning the orphan to one of the clusters having a non-zero computed probability of membership for the orphan.

### Claim 27 (depends on 21)

The system of claim 21, wherein the sequence reads received comprise full-length long reads, and wherein the generating and outputting the final cluster consensus further comprises:
inputting non-full-length reads into a final polishing processes that generates the final cluster consensus.

### Claim 28 (depends on 25)

The system of claim 25, wherein the reads comprise full-length long reads range in length from 0.5 kb to 1, 2, 3, 5, 10, 15, 20 kb.

### Claim 29 (depends on 21)

The system of claim 21, wherein grouping the sequence reads into a set of initial clusters based on sequence similarity further comprises:
aligning the sequence reads to create aligned reads;
building similarity graphs using the aligned reads; and
finding maximal cliques using the similarity graphs.

### Claim 30 (depends on 29)

The system of claim 29, wherein finding maximal cliques comprises: non-deterministically partitioning the similarity graphs into non-overlapping maximal cliques.
