Long fragment de novo assembly using short reads

• US 10,726,942 B2
• Filed: 08/25/2014
• Issued: 07/28/2020
• Est. Priority Date: 08/23/2013
• Status: Active Grant

• Current Assignee: MGI Tech Co., Ltd (BGI Genomics Co., Ltd.)
• Original Assignee: Complete Genomics Incorporated (BGI Genomics Co., Ltd.)
• Inventors: Drmanac, Radoje, Kermani, Bahram Ghaffarzadeh
• Primary Examiner(s): Wise, Olivia M.
• Application Number:
  US14/467,797
• Publication Number:
  US 20150057947A1
• Time in Patent Office: 2,164 Days
• Field of Search: None
• 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

Techniques perform de novo assembly. The assembly can use labels that indicate origins of the nucleic acid molecules. For example, a representative set of labels identified from initial reads that overlap with a seed can be used. Mate pair information can be used. A sequence read that aligns to an end of a contig can lead to using the other sequence read of a mate pair, and the other sequence read can be used to determine which branch to use to extend, e.g., in an external cloud or helper contig. A kmer index can include labels indicating an origin of each of the nucleic acid molecules that include each kmer, memory addresses of the reads that correspond to each kmer in the index, and a position in each of the mate pairs that includes the kmer. Haploid seeds can also be determined using polymorphic loci identified in a population.

Claims

1. A method of determining a sequence of a first chromosomal region of an organism, the method comprising:

receiving, at a computer system, sequence data from a sequencing of a plurality of nucleic acid molecules of the organism, wherein the sequence data for each of the plurality of nucleic acid molecules includes;

one or more sequence reads of at least one portion of the nucleic acid molecule, and

a label corresponding to the one or more sequence reads, the label indicating an origin of the nucleic acid molecule, wherein the sequence data includes at least 1,000 sequence reads;

receiving, by the computer system, a first contig of the first chromosomal region;

analyzing the at least 1,000 sequence reads to determine a group of sequence reads of the sequence data that overlap with an end sequence of the first contig, the group including sequence reads with a plurality of different labels indicating different origins of corresponding nucleic acid molecules, the different origins including different haplotypes; and

extending, by the computer system, the first contig using the group of sequence reads of the sequence data that overlap with the end sequence of the first contig.

2. The method of claim 1, wherein extending the first contig includes:

determining that the group of sequence reads has a first number of sequence reads at a next extension position that is less than a threshold number;

forming one or more hypothesis sequences for extending the first contig;

aligning other sequence reads to the one or more hypothesis sequences to identify at least the threshold number of sequence reads that overlap with the next extension position; and

extending the first contig using at least the threshold number of sequence reads that overlap with the next extension position.

3. The method of claim 2, wherein the threshold number of sequence reads correspond to a same hypothesis sequence.

4. The method of claim 3, further comprising:

determining whether at least the threshold number of sequence reads align to a second extension position of the same hypothesis sequence.

5. The method of claim 1, further comprising:

determining an expected range for a number of labels of sequence reads corresponding to a correct branch for extending the first contig; and

selecting, for extending the first contig, sequence reads of the first group that correspond to a first branch having a number of labels within the expected range as the correct branch.

6. The method of claim 1, further comprising:

determining that the group of sequence reads that overlap with the end sequence of the first contig indicate an existence of a first allele and a second allele at a position in the first contig, each allele corresponding to a different branch for extending the first contig;

determining a first number of labels that correspond only to the first allele;

determining a second number of labels that correspond only to the second allele; and

determining whether the position is heterozygous based on the first number and the second number.

7. The method of claim 6, wherein the position is identified as being heterozygous when both the first number and the second number are greater than a threshold.

8. The method of claim 1, further comprising:

identifying sequence reads of the sequence data that align to the first contig and identifying the corresponding labels of the identified sequence reads, the corresponding labels forming a representative set of labels; and

extending the first contig using sequence reads of the sequence data that overlap with the end sequence of the first contig and that have labels corresponding to the representative set of labels.

9. The method of claim 8, further comprising:

identifying a set of sequence reads that overlap with the end sequence of the first contig;

identifying a set of branches of the first contig, wherein a first subset of the overlapped reads correspond to a first branch and have a first set of tags, and wherein a second subset of the overlapped reads correspond to a second branch and have a second set of tags;

determining a first number of tags shared between the representative set and the first set;

determining a second number of tags shared between the representative set the second set; and

using the first number and the second number to determine which branch is correct.

10. The method of claim 9, further comprising:

selecting the first branch when the first number is larger than the second number.

11. The method of claim 9, further comprising:

removing branches from the set of branches that have less than a specified number of corresponding sequence reads.

12. The method of claim 8, wherein the received first contig is a seed sequence, the method further comprising:

determining the seed sequence.

13. The method of claim 12, wherein determining the seed sequence includes comparing a number of sequence reads from the sequence data that include the seed sequence to an expected number of sequence reads.

14. The method of claim 12, wherein determining the seed sequence includes comparing a number of labels corresponding to sequence reads of the sequence data including the seed sequence to an expected number of labels, wherein the expected number of labels is derived from a number of cells in a sample from which the plurality of nucleic acid molecules of the organism are sequenced.

15. The method of claim 8, further comprising:

identifying a first het at which overlapping sequence reads corresponding to the representative set of labels have two alleles;

unzipping the first contig to form a first haplotype sequence and a second haplotype sequence of the first contig;

identifying a first subset of the representative set of labels, the first subset corresponding to sequence reads having a first allele at the first het;

identifying a second subset of the representative set of labels, the second subset corresponding to sequence reads having a second allele at the first het;

using sequence reads having the first subset of labels to extend the first haplotype sequence; and

using sequence reads having the second subset of labels to extend the second haplotype sequence, wherein the method is performed by the computer system.

16. The method of claim 15, wherein the first subset of labels is greater than a specified number, and the second subset of labels is greater than the specified number.

17. The method of claim 15, further comprising:

identifying a first subset of a second set of labels corresponding to sequence reads having a first allele of a second het of the first contig; and

using sequence reads having the first subset of the second set of labels to extend the first haplotype sequence.

18. The method of claim 15, wherein the sequence reads of the sequence data correspond to both ends of a nucleic acid molecule, thereby forming a mate pair, the method further comprising:

extending the first haplotype sequence of the first contig using the mate pairs corresponding to the overlapping sequence reads having the first subset of the representative set of labels.

19. The method of claim 18, wherein extending the first haplotype sequence using the mate pairs includes:

extending the first haplotype sequence using a first sequence read of a mate pair; and

adding a second sequence read of the mate pair to an external cloud.

20. The method of claim 19, further comprising:

identifying a second set of labels corresponding to sequence reads of the sequence data that align to a reference sequence within a specified distance of the first contig; and

adding at least a portion of the sequence reads corresponding to the second set of labels to the external cloud.

21. The method of claim 19, further comprising:

adding the first sequence read to an internal cloud; and

extending the first haplotype sequence using the second sequence read by comparing a k-mer of the second sequence reads to k-mers of sequence reads of the internal cloud.

22. The method of claim 21, wherein comparing a k-mer of the second sequence reads to k-mers of sequence reads of the internal cloud includes:

comparing an index of k-mers of the second sequence to an index of k-mers of the internal cloud.

23. The method of claim 21, wherein the external cloud includes a plurality of k-mers for each sequence read added to the external cloud, the method further comprising:

removing a k-mer from the external cloud when the k-mer is used to extend the first haplotype sequence.

24. The method of claim 21, further comprising:

removing the first sequence read from the internal cloud when an end of the second sequence read is used to extend the first haplotype sequence.

25. The method of claim 21, further comprising:

removing the first sequence read from the internal cloud when an end of the first haplotype sequence extends a predetermined number of bases from a location that the first sequence read was used to extend the first haplotype sequence.

26. The method of claim 8, wherein each nucleic acid molecule includes a tag sequence indicating the origin of the nucleic acid molecule, wherein a same tag sequence on two nucleic acid molecules indicates a same origin for the two nucleic acid molecules, and wherein the label of the one or more sequence reads of a nucleic acid molecule corresponds to the tag sequence.

27. The method of claim 26, wherein the origin indicated by the tag sequence is an aliquot of a sample of the organism, the aliquot having less than a specified percentage of a genome of the organism.

28. The method of claim 26, wherein the origin indicated by a tag of a nucleic acid molecule is a non-cloned chromosomal fragment that is longer than the nucleic acid molecule and that includes the nucleic acid molecule.

29. The method of claim 1, wherein a number of bases that the first contig is extended is based on an amount of overhang of the overlapped reads of the group.

30. The method of claim 1, further comprising:

repeating extending the first contig using a new group of sequence reads that overlap with the end sequence of the first contig determined in a previous iteration.

31. The method of claim 1, wherein the plurality of nucleic acid molecules are fragments derived from longer molecules, the method further comprising:

adding the labels to the plurality of nucleic acid molecules such that at least a portion of the labels of nucleic acid molecules that are derived from a same longer molecule is shared.

32. A computer product comprising a non-transitory computer readable medium storing a plurality of instructions that when executed control a computer system to determine a sequence of a first chromosomal region of an organism, the instructions comprising:

receiving sequence data from a sequencing of a plurality of nucleic acid molecules of the organism, wherein the sequence data for each of the plurality of nucleic acid molecules includes;

one or more sequence reads of at least one portion of the nucleic acid molecule, and

a label corresponding to the one or more sequence reads, the label indicating an origin of the nucleic acid molecule, wherein the sequence data includes at least 1,000 sequence reads;

receiving a first contig of the first chromosomal region;

analyzing the at least 1,000 sequence reads to determine a group of sequence reads of the sequence data that overlap with an end sequence of the first contig, the group including sequence reads with a plurality of different labels indicating different origins of corresponding nucleic acid molecules, the different origins including different haplotypes; and

extending, by the computer system, the first contig using the group of sequence reads of the sequence data that overlap with the end sequence of the first contig.