US 11,600,360 B2Granted

Trace reconstruction from reads with indeterminant errors

AssigneeMicrosoft Technology Licensing, LLC

InventorsSergey Mikhailovich Yekhanin, Miklos Zoltan Racz

Life of this patent

Estimating the term…

Loading patent…

Abstract

Polynucleotide sequencing generates multiple reads of a polynucleotide molecule. Many or all of the reads contain errors. Trace reconstruction takes multiple reads generated by a polynucleotide sequencer and uses those multiple reads to reconstruct accurately the nucleotide sequence of the polynucleotide molecule. Some reads may contain errors that cannot be corrected. Thus, there may be reads that can be used throughout their entire length and other reads that have indeterminant errors which cannot be corrected. Rather than discarding the entire read when an indeterminant error is found, the portion of the read with the error is skipped and the sequence of the read following the error is used to reconstruct the trace. The amount of the read skipped is determined by the location of subsequence after the error that matches a consensus sequence of the other reads. Analysis resumes at a location determined by the location of the match.

Claims20

Dependent claims

A method to improve sequencing accuracy of a polynucleotide sequencer comprising:

sequencing polynucleotide molecules with the polynucleotide sequencer thereby generating a plurality of sequence reads;
generating a first consensus output sequence for a first portion of the plurality of sequence reads from the polynucleotide sequencer, the first portion located before an indeterminant error;
identifying, in a read of the plurality of sequence reads, the indeterminant error relative to a plurality consensus base call of the plurality of sequence reads at a first position, wherein the indeterminant error is a base call that does not match the plurality consensus base call at the first position and cannot be identified as an insertion, deletion, or substitution;
defining a search window that includes a second position in the read, the second position located at least a delay past the first position, wherein the delay has a predetermined length;
calculating edit distances for subsequences in the search window from a comparison sequence, the comparison sequence including a match-backwards sequence that is a consensus output sequence for a predetermined number of positions before the second position;
identifying a subsequence in the search window that has an edit distance equal to or less than a threshold value;
selecting a candidate position within the subsequence and outside of the match-backwards sequence;
determining a second consensus output sequence for a second portion of the plurality of sequence reads after the candidate position;
and
generating a single consensus output sequence from the first consensus output sequence and the second consensus output sequence, the single consensus output sequence representing a nucleotide sequence of the polynucleotide molecules.

7 more elements

A system for improving sequencing accuracy of a polynucleotide sequencer, the system comprising:

a polynucleotide sequencer configured to generate a plurality of sequence reads by sequencing polynucleotides;
one or more processing units;
a memory coupled to the one or more processing units;
a variant read identification module stored in the memory and implemented by the one or more processing units to identify an error in a read of the plurality of sequence reads, wherein the error is a base call that does not match a plurality consensus base call at a first position in an alignment of the plurality of sequence reads;
an error classification module stored in the memory and implemented by the one or more processing units to determine that the error is an indeterminant error that cannot be identified as an insertion, deletion, or substitution;
a consensus output sequence generator stored in the memory and implemented by the one or more processing units to:
generate a first consensus output sequence for a first portion of the plurality of sequence reads that is located before the first position containing the indeterminant error;
define a search window that includes a second position in the read, the second position located at least a delay past the first position, wherein the delay has a predetermined length;
calculate edit distances for subsequences in the search window from a comparison sequence, the comparison sequence including a match-backwards sequence that is a consensus output sequence for a predetermined number of positions before the second position;
identify a subsequence in the search window that has an edit distance equal to or less than a threshold value;
select a candidate position within the subsequence and outside of the match-backwards sequence;
determine a second consensus output sequence for a second portion of the plurality of sequence reads after the candidate position;
and
generate a single consensus output sequence from the first consensus output sequence and the second consensus output sequence, the single consensus output sequence representing a nucleotide sequence of the polynucleotide molecules.

11 more elements

Dependencies are inferred from the claim text.

Facts

Application: 16/105,349Filed 20 Aug 2018
Published: US 2020/0057838 A120 Feb 2020
Granted: 7 Mar 2023
Term ends: Not estimatedThe source records don’t support an estimate.

Classification10 codes

G16B 30/00
Ict specially adapted for sequence analysis involving nucleotides or amino acids
G16B 30/10
ICT specially adapted for sequence analysis involving nucleotides or amino acids: sequence alignment; Homology search
G06F 40/166
Text processing: editing, e.g. inserting or deleting
G06F 40/279
Natural language analysis: recognition of textual entities