Algorithms for sequence determination

• US 8,370,079 B2
• Filed: 11/20/2009
• Issued: 02/05/2013
• Est. Priority Date: 11/20/2008
• Status: Active Grant

• Current Assignee: Pacific Bioscience of California Incorporated (L'Oreal SA)
• Original Assignee: Pacific Bioscience of California Incorporated (L'Oreal SA)
• Inventors: Sorenson, Jon, Tang, Susan, Marks, Patrick, Chin, Chen-Shan
• Primary Examiner(s): Clow, Lori A
• Application Number:
  US12/592,284
• Publication Number:
  US 20100169026A1
• Time in Patent Office: 1,173 Days
• Field of Search: None
• US Class Current: 702/20
• CPC Class Codes: G16B 30/00 ICT specially adapted for sequence analysis involving nucleotides or amino acids
• CPC Class Codes: G16B 30/10 Sequence alignment; Homology search
• CPC Class Codes: G16B 30/20 Sequence assembly

Abstract

The present invention is generally directed to powerful and flexible methods and systems for consensus sequence determination from replicate biomolecule sequence data. It is an object of the present invention to improve the accuracy of consensus biomolecule sequence determination from replicate sequence data by providing methods for assimilating replicate sequence into a final consensus sequence more accurately than any one-pass sequence analysis system.

Claims

1. A method of determining a consensus sequence, comprising:

a) providing a plurality of replicate sequence reads;

b) aligning the plurality of replicate sequence reads to generate a multiple sequence alignment;

c) determining a percent of majority calls for each position in a region of interest in the multiple sequence alignment;

d) based upon the results of step c, identifying a set of sequential positions in the region of interest, wherein all positions in the set of sequential positions have a percent of majority calls below a threshold; and

e) using information from the plurality of replicate sequence reads for the set of sequential positions in the region of interest in a pattern classification algorithm to generate a consensus sequence spanning the set of sequential positions, wherein

a call by the pattern classification algorithm for a first position in the set of sequential positions is dependent upon a call made for a second position in the set of sequential positions that is made by the pattern classification algorithm,

the first position and the second position are adjacent to each other, and

at least steps a), b), and e) are performed using a suitably programmed computer.

2. The method of claim 1, wherein the consensus sequence is a polynucleotide sequence.

3. The method of claim 1, wherein the plurality of replicate sequence reads are provided by repeatedly sequencing a single molecule.

4. The method of claim 1, wherein the plurality of replicate sequence reads are provided by simultaneously or sequentially sequencing multiple molecules, each of which comprises at least a portion of said region of interest.

5. The method of claim 1, wherein the percent of majority calls is determined for each position in the region of interest by dividing a count for a most frequent call at a given position by a total number of replicate sequence reads that comprise the given position.

6. The method of claim 1, further comprising generating a path representation of the multiple sequence alignment.

7. The method of claim 6, wherein the path representation is a directed acyclic graph.

8. The method of claim 6, wherein the path representation is subjected to a pruning heuristic.

9. The method of claim 1, wherein the pattern classification algorithm finds a shortest path for calls across the sequential positions.

10. The method of claim 1, wherein the pattern classification algorithm applies a likelihood model.

11. The method of claim 1, wherein the pattern classification algorithm applies an error model.

12. The method of claim 1, wherein the pattern classification algorithm applies a probabilistic graph model.

13. The method of claim 12, wherein the probabilistic graph model comprises an all path probabilistic alignment.

14. The method of claim 1, wherein the pattern classification algorithm applies both a likelihood model and an error model.

15. The method of claim 1, wherein the pattern classification algorithm applies a likelihood model, an error model, and a probabilistic graph model.

16. The method of claim 1, wherein the pattern classification algorithm generates the consensus sequence by maximizing a likelihood based upon the replicate sequence reads.

17. The method of claim 1, wherein the pattern classification algorithm uses a context dependent alignment model parameter based upon a whole genome multiple sequence alignment to generate the consensus sequence.

18. The method of claim 1, wherein the pattern classification algorithm applies a dynamic Bayesian network.

19. The method of claim 18, wherein the dynamic Bayesian network is a Hidden Markov Model.

20. The method of claim 1, further comprising catenating the consensus sequence generated in step e with majority calls from outside the set of sequential positions but in the region of interest.

21. The method of claim 1, wherein multiple sets of sequential positions are identified in step d and multiple consensus sequences for the multiple sets of sequential positions are generated in step e.

22. The method of claim 21, further comprising catenating the multiple consensus sequences with majority calls from outside the multiple sets of sequential positions but in the region of interest to generate a further consensus sequence for the region of interest.

23. The method of claim 21, wherein a first threshold is used to identify at least a first set of sequential positions in the multiple sets of sequential positions and a second threshold is used to identify at least a second set of sequential positions in the multiple sets of sequential positions.

24. The method of claim 1, wherein a set of consensus sequences for the set of sequential positions is generated in step e, further Wherein the set of consensus sequences includes at least a most probable consensus sequence and a second most probable consensus sequence.

25. The method of claim 1 iteratively applied, wherein in a first iteration only a portion of the replicate sequence reads in the plurality of replicate sequence reads is used, and in a subsequent iteration additional sequence reads in the plurality of replicate sequence reads is used.

26. The method of claim 25, wherein in the first iteration only the portion of the replicate sequence reads are aligned in step b, and in the subsequent iteration the additional sequence reads in the plurality of replicate sequence reads are aligned in step b.

27. The method of claim 1 iteratively applied, wherein in a first iteration a first threshold is used to identify a first set of sequential positions, and in a subsequent iteration a second threshold is used to identify a second set of sequential positions, wherein the second threshold identifies fewer sequential positions than the first threshold, thereby causing the first set of sequential positions to have more sequential positions than the second set of sequential positions.

28. A system for determining a consensus sequence, comprising:

a processor; and

memory storing an application to be executed by the processor, wherein the application comprises instructions for;

a) obtaining a plurality of replicate sequence reads;

b) aligning the plurality of replicate sequence reads to generate a multiple sequence alignment;

c) determining a percent of majority calls for each position in a region of interest in the multiple sequence alignment;

d) based upon the results of the determining c), identifying a set of sequential positions in the region of interest, wherein all positions in the set of sequential positions have a percent of majority calls below a threshold; and

e) using information from the plurality of replicate sequence reads for the set of sequential positions in the region of interest in a pattern classification algorithm to generate a consensus sequence spanning the set of sequential positions, wherein

a call by the pattern classification algorithm for a first position in the set of sequential positions is dependent upon a call made for a second position in the set of sequential positions that is made by the pattern classification algorithm, and

the first position and the second position are adjacent to each other.

29. A non-transitory computer readable storage medium storing an application to be executed by a processor of a computer, wherein the application is for determining a consensus sequence and wherein the application comprises instructions for:

a) obtaining a plurality of replicate sequence reads;

b) aligning the plurality of replicate sequence reads to generate a multiple sequence alignment;

c) determining a percent of majority calls for each position in a region of interest in the multiple sequence alignment;

d) based upon the results of the determining c), identifying a set of sequential positions in the region of interest, wherein all positions in the set of sequential positions have a percent of majority calls below a threshold; and

e) using information from the plurality of replicate sequence reads for the set of sequential positions in the region of interest in a pattern classification algorithm to generate a consensus sequence spanning the set of sequential positions, wherein

a call by the pattern classification algorithm for a first position in the set of sequential positions is dependent upon a call made for a second position in the set of sequential positions that is made by the pattern classification algorithm, and

the first position and the second position are adjacent to each other.