METHOD AND SYSTEM FOR CALLING VARIATIONS IN A SAMPLE POLYNUCLEOTIDE SEQUENCE WITH RESPECT TO A REFERENCE POLYNUCLEOTIDE SEQUENCE

• US 20110004413A1
• Filed: 04/29/2010
• Published: 01/06/2011
• Est. Priority Date: 04/29/2009
• Status: Abandoned Application

• Current Assignee: Complete Genomics Incorporated (BGI Genomics Co., Ltd.)
• Original Assignee: Complete Genomics Incorporated (BGI Genomics Co., Ltd.)
• Inventors: Drmanac, Radoje, Halpern, Aaron L., Carnevali, Paolo, Nilsen, Geoffrey, Martin, Bruce, Baccash, Jonathan M., Nazarenko, Igor
• Application Number:
  US12/770,089
• Publication Number:
  US 20110004413A1
• Time in Patent Office: Days
• US Class Current: 702/19
• CPC Class Codes: G16B 20/00 ICT specially adapted for functional genomics or proteomics, e.g. genotype-phenotype associations
• CPC Class Codes: G16B 20/10 Ploidy or copy number detection
• CPC Class Codes: G16B 20/20 Allele or variant detection, e.g. single nucleotide polymorphism [SNP] detection
• CPC Class Codes: G16B 20/50 Mutagenesis
• 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

Embodiments for calling variations in a sample polynucleotide sequence compared to a reference polynucleotide sequence are provided. Aspects of the embodiments include executing an application on at least one computer that locates local areas in the reference polynucleotide sequence where a likelihood exists that one or more bases of the sample polynucleotide sequence are changed from corresponding bases in the reference polynucleotide sequence, where the likelihood is determined at least in part based on mapped mated reads of the sample polynucleotide sequence; generating at least one sequence hypothesis for each of the local areas, and optimizing the at least one sequence hypothesis for at least a portion of the local areas to find one or more optimized sequence hypotheses of high probability for the local areas; and analyzing the optimized sequence hypotheses to identify a series of variation calls in the sample polynucleotide sequence.

Claims

1. A computer-implemented method for calling variations in a sample polynucleotide sequence with respect to a reference polynucleotide sequence, the method comprising:

executing an application on at least one computer that locates local areas in the reference polynucleotide sequence where a likelihood exists that one or more bases of the sample polynucleotide sequence are changed from corresponding bases in the reference polynucleotide sequence, where the likelihood is determined at least in part based on mapped mated reads of the sample polynucleotide sequence;

generating at least one sequence hypothesis for each of the local areas, and optimizing the at least one sequence hypothesis for at least a portion of the local areas to find one or more optimized sequence hypotheses of high probability for the local areas; and

analyzing the optimized sequence hypotheses to identify a series of variation calls in the sample polynucleotide sequence.

2. The method of claim 1 wherein each of the mated reads comprise variably gapped reads.

3. The method of claim 1, wherein each of the mated reads comprise non-gapped reads.

4. The method of claim 1 further comprising storing in a data repository the reference polynucleotide sequence and mapped mated reads obtained from the sample polynucleotide sequence that are mapped to locations in the reference polynucleotide sequence, and performing the method by a variation caller executing in parallel on the plurality of computers in a computer cluster, each of the plurality of computers coupled to the data repository via a network.

5. The method of claim 1, wherein locating the local areas likely to have changed from the reference further comprises computing reference scores using a Bayesian formulation process.

6. The method of claim 5, wherein computing reference scores using the Bayesian formulation process further comprises:

generating a set of initial hypotheses for each base position in the reference polynucleotide sequence by modifying a base value at that position in p alleles by all possible 1-base variations;

determining a set of mapped mated reads that are near the current base position of the reference polynucleotide sequence; and

computing reference scores for each base position by computing for each of the initial hypotheses in the corresponding set, a probability ratio P_V/P_ref, where P_V is a probability of a 1-base variation hypothesis, and P_ref is a probability of the base value in the reference polynucleotide sequence, and where the set of mapped mated reads near each base position are used during calculation of the probability ratio at each base position.

7. The method of claim 6, wherein the sample polynucleotide sequence comprises a genome G, and wherein each of the reference scores comprises as a logarithmic likelihood ratio L(G) for each of the hypothesis, where L(G)=log (P_v/P_Ref).

8. The method of claim 6, wherein the mapped mated reads are generated independently of each other, and probability estimates that take into account all of the mapped mated reads are calculated by

9. The method of claim 6, further comprising representing

10. The method of claim 6 further comprising controlling an amount of contribution a single mated read can give to L(G) by considering only the mappings of the mated read that have a small number of mismatches in a summation of the mated reads during calculation of L(G), and representing the mappings with large numbers of mismatches with a constant that is assumed to be the same for all polynucleotide sequence and independent of G.

11. The method of claim 1, wherein locating the local areas likely to have changed from the reference further comprises computing local de novo intervals using the partial de Bruijn graph to find variations beyond single base changes.

12. The method of claim 11 further comprising:

initializing a partial de Bruijn graph with reference vertices created from base sequences from the reference polynucleotide sequence;

for each of the reference vertices, determining a set of mapped mated reads that map to the reference vertex and that include a base extension extending beyond either end of the reference vertex by any possible 1-base value;

calculating for each of the base extensions an extension strength representing an amount of support for extending the reference vertex by each 1-base value based at least in part on a number of mapped mated reads that have the same extension and the number of matches and mismatches of those mapped mated reads with the sequence of the vertex being processed;

using the base extensions having a highest the extension strength that are incompatible with the reference vertices as a branch vertices in the partial de Bruijn graph;

computing the extension strength in the direction of the extension for each branch vertex in a depth-first manner in one direction, and creating a new edge and a branch new vertex after each computation from the base extensions having extension strength above a threshold;

if there are no base extensions having the extension strength above the threshold in a path, returning a failure for the path; and

if a new branch vertex is created that is equal to the base sequence of one of the reference vertices and that is consistent with a SNP or short indel, ending the computation and returning the path.

13. The method of claim 1, wherein locating the local areas likely to have changed from the reference further comprises finding optimization intervals by combining individual local areas of likely change represented by the reference scores and the local de novo intervals.

14. The method of claim 13 further comprising:

considering as candidate optimization intervals the local de novo intervals and the reference scores associated with a high probability ratio P_V/P_ref, where P_V is a probability of a 1-base variation hypothesis, and P_ref is a probability of the base value in the reference polynucleotide sequence; and

combining the candidate optimization intervals that overlap or are less than a threshold base distance apart into the optimization intervals.

15. The method of claim 14, wherein the sample polynucleotide sequence comprises a genome G, and wherein each of the reference scores comprises as a logarithmic likelihood ratio L(G) for each of the hypothesis, where L(G)=log(P_v/P_Ref).

16. The method of claim 1 wherein the optimizing a sequence hypothesis for a local area further comprises:

traversing each base position in an initial hypotheses in the local area and iteratively changing the base with every possible alternative base values including inserted and deleted bases, computing a second probability ratio for each change; and

applying changes to the local area that maximize the second probability ratio.

17. The method of claim 16 further comprising performing the optimization on the local areas separately from one another with an assumption that the sample polynucleotide sequence equals the reference polynucleotide sequence outside of the current local area being optimized, such that the sample polynucleotide sequence is optimized only in the current local area.

18. The method of claim 17 further comprising calculating the second probability ratio as P_H/P_ref, where P_H is a probability of the sequence hypothesis in a current local area and P_ref is a probability of the reference.

19. The method of claim 18, wherein the sample polynucleotide sequence comprises a genome G, and wherein each of the reference scores comprises as a logarithmic likelihood ratio L(G) for each of the hypothesis, where L(G)=log (P_H/P_Ref).

20. The method of claim 17 further comprising performing the optimization using a combination of a Bayesian formulation and a de Bruijn graph, wherein the de Bruijn graph is used to generate additional starting sequence hypotheses for the Bayesian formation to drive the optimization process towards a global optimum.

21. The method of claim 20 further comprising using a de Bruijn graph that is modified to process variably gapped reads.

22. The method of claim 17 further comprising requiring that a size of the current local area is kept smaller than a minimum possible mate pair length.

23. The method of claim 1, wherein the analyzing each of the sets of sequence hypotheses further comprises inferring variations in the bases of the mapped mated reads of the sample polynucleotide sequence in relation to the reference polynucleotide sequence at a specific location.

24. The method of claim 23 further comprising:

examining for each of the local areas, all hypotheses within a variation score threshold of a most likely hypothesis listed for the local area, producing a set of most likely hypotheses;

finding common features that are present in each of the hypotheses in the set of most likely hypotheses; and

storing the common features as respective variation calls.

25. The method of claim 23 further comprising:

finding inconsistencies between each of the hypotheses in the set of most likely hypotheses; and

storing the inconsistencies as respective no-call regions.

26. The method of claim 1 wherein the sample polynucleotide sequence comprises a genome (G), the method further comprising reassembling the sample polynucleotide sequence by iteratively maximizing the genome'"'"'s a posteriori probability P(G/MatedRreads), which accounts for all mapped mated reads.

27. The method of claim 1, wherein analyzing each of the sets of sequence hypotheses further comprises generating a no call for any part of the hypotheses in the set of sequence hypotheses in which an inconsistency is found.

28. A system, comprising:

a data repository that stores a reference polynucleotide sequence and mapped mated reads obtained from a sample polynucleotide sequence that are mapped to locations in the reference polynucleotide sequence;

a computer cluster comprising a plurality of computers coupled to the data repository via a network; and

a variation caller executing in parallel on the plurality of computers, the variation caller configured to;

locate local areas in the sample polynucleotide sequence based on the mapped mated reads where one or more bases are likely to have changed from corresponding bases in the reference polynucleotide sequence;

optimize a sequence hypothesis for each of the local areas to find a set of sequence hypotheses of high probability for each of the local areas; and

analyze each of the sets of sequence hypotheses to identify a series of variation calls in the sample polynucleotide sequence.

29. An executable software product stored on a computer-readable medium containing program instructions for calling variations in mapped mated reads obtained from a sample polynucleotide sequence compared to a reference polynucleotide sequence, the program instructions for:

locating local areas in the sample polynucleotide sequence based on the mapped mated reads where one or more bases are likely to have changed from corresponding bases in the reference polynucleotide sequence;

optimizing a sequence hypothesis for each of the local areas to find a set of sequence hypotheses of high probability for each of the local areas; and

analyzing each of the sets of sequence hypotheses to statistically identify a series of variation calls in the sample polynucleotide sequence and storing the variation calls in a memory.

30. A system, comprising:

a data repository that stores a reference polynucleotide sequence and mapped mated reads obtained from a sample polynucleotide sequence that are mapped to locations in the reference polynucleotide sequence;

a computer cluster comprising a plurality of computers coupled to the data repository via a network; and

a variation caller executing in parallel on the plurality of computers, the variation caller configured to;

perform statistical probability analysis on the reference polynucleotide sequence and on the mapped mated reads based in part on a combination of evidential reasoning performed by a Bayesian formulation and de Bruijn graph based algorithms;

use the statistical probability analysis to identify and call variations detected in the mapped mated reads in relation to the reference polynucleotide sequence; and

output a list of the variations, each describing a manner in which the mapped mated reads are observed to differ from the reference polynucleotide sequence at or near a specific location.

31. The system of claim 30 wherein the variations file further includes a list of no-called regions for which variations cannot be called due to computational uncertainties.

32. The system of claim 30 wherein the variations include sequences of deletions, insertions, mutations, polymorphisms, and duplications or rearrangements of one or more bases.

33. The system of claim 32 wherein the variation caller is further configured to use the probability analysis to assemble the sample polynucleotide sequence from the mapped mated reads, where an assembled polynucleotide sequence is based substantially on the reference polynucleotide sequence, but includes the identified variations.

34. The system of claim 30 wherein the computer cluster is configured such that instances of the variation caller executing on different ones of the plurality of computers operate on different portions of the reference polynucleotide sequence and the mapped mated reads in parallel.

35. A computer-implemented method for calling variations in mapped mated reads obtained from a sample polynucleotide sequence compared to a reference polynucleotide sequence, the method comprising:

performing statistical probability analysis on the reference polynucleotide sequence and on the mapped mated reads based in part on a combination of evidential reasoning performed by a Bayesian formulation and de Bruijn graph based algorithms;

using the statistical probability analysis to identify and call variations detected in the mapped mated reads in relation to the reference polynucleotide sequence; and

outputting a list of the variations, each describing a manner in which the mapped mated reads are observed to differ from the reference polynucleotide sequence at or near a specific location and storing the variation calls in a memory.

36. The method of claim 35 further comprising storing in a data repository the reference polynucleotide sequence and mapped mated reads obtained from the sample polynucleotide sequence that are mapped to locations in the reference polynucleotide sequence, and performing the method by a variation caller executing in parallel on the plurality of computers in a computer cluster, each of the plurality of computers coupled to the data repository via a network.

37. An executable software product stored on a computer-readable medium containing program instructions for calling variations in mapped mated reads obtained from a sample polynucleotide sequence compared to a reference polynucleotide sequence, the program instructions for:

performing statistical probability analysis on the reference polynucleotide sequence and on the mapped mated reads based in part on a combination of evidential reasoning performed by a Bayesian formulation and de Bruijn graph based algorithms;

using the statistical probability analysis to identify and call variations detected in the mapped mated reads in relation to the reference polynucleotide sequence; and

outputting a list of the variations, each describing a manner in which the mapped mated reads are observed to differ from the reference polynucleotide sequence at or near a specific location.