Methods, systems, and computer readable media for making base calls in nucleic acid sequencing

Abstract

A method for nucleic acid sequencing includes receiving a plurality of observed or measured signals indicative of a parameter observed or measured for a plurality of defined spaces; determining, for at least some of the defined spaces, whether the defined space comprises one or more sample nucleic acids; processing, for at least some of the defined spaces, the observed or measured signal to improve a quality of the observed or measured signal; generating, for at least some of the defined spaces, a set of candidate sequences of bases for the defined space using one or more metrics adapted to associate a score or penalty to the candidate sequences of bases; and selecting the candidate sequence leading to a highest score or a lowest penalty as corresponding to the correct sequence for the one or more sample nucleic acids in the defined space.

1 . A method for nucleic acid sequencing, comprising:
 receiving a plurality of observed or measured signals indicative of a parameter observed or measured for a plurality of defined spaces, at least some of the defined spaces comprising one or more sample nucleic acids, the observed or measured signals being responsive to a plurality of nucleotide flows introducing nucleotides to the defined spaces;   determining, for at least some of the defined spaces, whether the defined space comprises one or more sample nucleic acids;   processing, for at least some of the defined spaces determined to comprise one or more sample nucleic acids, the observed or measured signal for the defined space to improve a quality of the observed or measured signal;   generating, for at least some of the defined spaces determined to comprise one or more sample nucleic acids and processed in the processing step, a set of candidate sequences of bases for the defined space using one or more metrics adapted to associate a score or penalty to the candidate sequences of bases; and   selecting from the generated sequences of bases the candidate sequence leading to a highest score or a lowest penalty as corresponding to the correct sequence for the one or more sample nucleic acids in the defined space.   
     
     
         2 . The method of  claim 1 , wherein the parameter observed or measured for the defined spaces comprises a voltage measurement indicative of hydrogen ion concentration for respective defined spaces or a measurement substantially proportional to a light or fluorescent intensity for respective defined spaces. 
     
     
         3 . The method of  claim 1 , wherein generating the set of candidate sequences comprises generating a data structure comprising a set of partial paths corresponding to candidate sequences undergoing expansion in a stepwise manner one base at a time. 
     
     
         4 . The method of  claim 3 , wherein generating the data structure comprises determining a predicted signal for each partial path and evaluating a distance between the predicted signal and an observed or measured signal. 
     
     
         5 . The method of  claim 4 , wherein the one or more metrics comprise a metric that is a function of the distance between the predicted signal and the observed or measured signal. 
     
     
         6 . The method of  claim 4 , wherein the one or more metrics comprise a metric comprising a sum of squared distances between corresponding values of the predicted signal and the observed or measured signal. 
     
     
         7 . The method of  claim 1 , wherein the one or more metrics comprise a path metric comprising a sum of (i) a sum of squared residuals before an active window and (ii) a sum of squared residuals for negative residuals within the active window. 
     
     
         8 . The method of  claim 1 , wherein the one or more metrics comprise a greedy decision metric comprising a sum of (i) a product of an empirical constant and a sum of squared residuals for negative residuals within an active window and (ii) a sum of squared residuals for positive residuals within the active window but only before an in-phase flow. 
     
     
         9 . The method of  claim 1 , wherein the one or more metrics comprise a path metric, a greedy decision metric, and a per-flow metric, and wherein the per-flow metric comprises a weighted sum of (i) the path metric and (ii) the greedy decision metric. 
     
     
         10 . The method of  claim 1 , wherein the one or more metrics comprise a scaled residual comprising a ratio between (i) a difference between an observed or measured value for a current path at a current in-phase flow and a predicted value from a parent path at the current in-phase flow and (ii) a difference between a predicted value of the current path at the current in-phase flow and a predicted value from the parent path at the current in-phase flow. 
     
     
         11 . The method of  claim 1 , wherein the one or more metrics comprise a total residual comprising a sum of squared residuals over all nucleotide flows. 
     
     
         12 . The method of  claim 3 , wherein generating the data structure comprises pruning the data structure using one or more absolute pruning rules selected from the group comprising: (i) discarding paths having a path metric larger than a best total residual metric, (ii) discarding paths having reached a last nucleotide flow, (iii) discarding paths for which a greedy decision metric exceeds a greedy penalty maximal threshold, (iv) discarding paths for which a polymerase activity is below a polymerase activity minimal threshold, (v) discarding paths including more than a threshold number of homopolymers having at least a threshold length in a row, (vi) discarding paths having a scaled residual metric below a first scaled residual minimal threshold, (vii) discarding paths having a scaled residual below a second scaled residual minimal threshold that is larger than the first scaled residual minimal threshold, and (viii) discarding paths having a greedy decision metric that exceeds the greedy decision metric for a best greedy expansion by more than a maximal threshold. 
     
     
         13 . The method of  claim 3 , wherein generating the data structure comprises pruning the data structure using one or more relative pruning rules selected from the group comprising: (i) discarding paths being more than a certain number of base pairs shorter than a longest path in the data structure, and (ii) discarding paths having a highest per-flow metric whenever the number of paths exceeds a certain threshold. 
     
     
         14 . The method of  claim 1 , wherein generating the set of candidate sequences comprises determining a predicted signal for candidate sequences using a simulation framework for simulating possible state transitions for active polymerase present at a K-th base during an N-th nucleotide flow, where K and N denote indices associated with bases and nucleotide flows. 
     
     
         15 . The method of  claim 14 , wherein the simulation framework comprises simulating possible state transitions for situations where the K-th base matches the N-th nucleotide flow by modeling (i) a proportion of polymerase that will remain active and not incorporate base K in flow N by a first expression and (ii) a proportion of polymerase that will remain active and incorporate base K in flow N by a second expression. 
     
     
         16 . The method of  claim 15 , wherein:
 the first expression comprises a product of (i) a measure of a quantity of active polymerase prior to the transition and (ii) a transition factor [IER×(1−DR)], and   the second expression comprises a product of (i) the measure of the quantity of active polymerase prior to the transition and (ii) a transition factor [(1−IER)×(1−DR)],   where IER represents an incomplete extension rate and DR represents a droop rate.   
     
     
         17 . The method of  claim 14 , wherein the simulation framework comprises simulating possible state transitions for situations where the K-th base does not match the N-th flow by modeling (i) a proportion of polymerase that will remain active and not incorporate base K in flow N by a first expression and (ii) a proportion of polymerase that will remain active and incorporate base K in flow N by a second expression. 
     
     
         18 . The method of  claim 17 , wherein:
 the first expression comprises a product of (i) a measure of the quantity of active polymerase prior to the transition and (ii) a transition factor [(1−CFR M )+(CFR M ×IER×(1−DR))], and   the second expression comprises a product of (i) the measure of the quantity of active polymerase prior to the transition and (ii) a transition factor [CFR M ×(1−IER)×(1−DR)],   where IER represents an incomplete extension rate, DR represents a droop rate, CFR represents a carry forward rate, and M is the smallest number such that the (N−M)-th flow matches the K-th base.   
     
     
         19 . A system, comprising:
 a machine-readable memory; and   a processor configured to execute machine-readable instructions, which, when executed by the processor, cause the system to perform steps including:
 receiving a plurality of observed or measured signals indicative of a parameter observed or measured for a plurality of defined spaces, at least some of the defined spaces comprising one or more sample nucleic acids, the observed or measured signals being responsive to a plurality of nucleotide flows introducing nucleotides to the defined spaces; 
 determining, for at least some of the defined spaces, whether the defined space comprises one or more sample nucleic acids; 
 processing, for at least some of the defined spaces determined to comprise one or more sample nucleic acids, the observed or measured signal for the defined space to improve a quality of the observed or measured signal; 
 generating, for at least some of the defined spaces determined to comprise one or more sample nucleic acids and processed in the processing step, a set of candidate sequences of bases for the defined space using one or more metrics adapted to associate a score or penalty to the candidate sequences of bases; and 
 selecting from the generated sequences of bases the candidate sequence leading to a highest score or a lowest penalty as corresponding to the correct sequence for the one or more sample nucleic acids in the defined space. 
   
     
     
         20 . A method for nucleic acid sequence identification, comprising:
 obtaining information corresponding to a plurality of observed or measured nucleotide incorporation events for one or more sample nucleic acid sequences;   developing a plurality of predicted modelings of the observed or measured nucleotide incorporation events;   comparing the plurality of predicted modelings to at least one of the observed or measured nucleotide incorporation events; and   identifying at least a portion of the nucleic acid sequence on the basis of which predicted modeling is most similar to the observed or measured nucleotide incorporation events, the portion covering at least two consecutive bases called together as a whole.