Processes and systems for nucleic acid sequence assembly
Methods, processes, and particularly computer implemented processes and computer program products are provided for use in the analysis of genetic sequence data. The processes and products are employed in the assembly of shorter nucleic acid sequence data into longer linked and preferably contiguous genetic constructs, including large contigs, chromosomes and whole genomes.
1. A method of determining a sequence of a larger contiguous nucleic acid comprising, at a computer system having one or more processors, and memory storing one or more programs for execution by the one or more processors:
(A) obtaining a plurality of oligonucleotide sequence reads of the larger contiguous nucleic acid, wherein
the plurality of oligonucleotide sequence reads comprises a plurality of sets of oligonucleotide sequence reads,
the larger contiguous nucleic acid is greater than 1 million base pairs in length,
each oligonucleotide sequence read in the plurality of oligonucleotide sequence reads has a sequence length of less than 1000 bases,
the plurality of sets of oligonucleotide sequence reads comprises more than 1×10 6 sets of oligonucleotide sequence reads,
each respective oligonucleotide sequence read in each respective set of oligonucleotide sequence reads includes (i) a first portion that corresponds to a subset of the larger contiguous nucleic acid and (ii) a common second portion that forms an identifier that is independent of the oligonucleotide sequence of the larger contiguous nucleic acid and that identifies a reaction vessel partition, in a plurality of reaction vessel partitions, in which the respective oligonucleotide sequence read was formed, and
each respective set of oligonucleotide sequence reads in the plurality of sets of oligonucleotide sequence reads is formed in a reaction vessel partition in the plurality of reaction vessel partitions and each reaction vessel partition includes one or more fragments of the larger contiguous nucleic acid that is used as the template for each respective oligonucleotide sequence read in the reaction vessel partition;
(B) creating a respective set of k-mers for each oligonucleotide sequence read in the plurality of oligonucleotide sequence reads, wherein
the sets of k-mers collectively comprise a plurality of k-mers,
k is an integer between 5 and 100,
the identifiers of the oligonucleotide sequence reads for each k-mer in the plurality of k-mers is retained,
k is less than the average length of the oligonucleotide sequence reads in the plurality of oligonucleotide sequence reads, and
each respective set of k-mers includes at least eighty percent of the possible k-mers of length k of the first portion of the corresponding oligonucleotide sequence read;
(C) tracking, for each respective k-mer in the plurality of k-mers, an identity of each oligonucleotide sequence read in the plurality of oligonucleotide sequence reads that contains the respective k-mer and the identifier of the set of oligonucleotide sequence reads that contains the oligonucleotide sequence read;
(D) graphing the plurality k-mers as a graph comprising a plurality of nodes connected by a plurality of directed arcs, wherein
each node comprises an uninterrupted set of k-mers in the plurality of k-mers of length k with k−1 overlap,
each arc connects an origin node to a destination node in the plurality of nodes,
a final k-mer of an origin node has k−1 overlap with an initial k-mer of a destination node, and
a first origin node has a first directed arc with both a first destination node and a second destination node in the plurality of nodes;
(E) merging the origin node with the first destination node or the second destination node in order to derive a contig oligonucleotide sequence that is more likely to be representative of a portion of the larger contiguous nucleic acid, wherein the contig oligonucleotide sequence comprises (i) the origin node and (ii) one of the first destination node and the second destination node, wherein the determining uses at least the identifiers of the oligonucleotide sequence reads for k-mers in the first origin node, the first destination node, and the second destination node; and
(F) using the graph, after the determining (E), to assemble the sequence of the larger contiguous nucleic acid.
2. The sequencing method of claim 1 , wherein,
the first origin node and the first destination node are part of a first path in the graph that includes one or more additional nodes other than the origin node and the first destination node,
the first origin node and the second destination node are part of a second path in the graph that includes one or more additional nodes other than the origin node and the second destination node, and
the determining (E) comprises determining whether the first path is more likely representative of the larger contiguous nucleic acid than the second path by evaluating a number of identifiers shared between the k-mers of the nodes of a first portion of the first path and the k-mers of the nodes of a second portion of the first path versus a number of identifiers shared between the k-mers of the nodes of a first portion of the second path and the k-mers of the nodes of a second portion of the second path.
3. The sequencing method of claim 1 , wherein
the first origin node and the first destination node are part of a first path in the graph that includes one or more additional nodes other than the origin node and the first destination node,
the first origin node and the second destination node are part of a second path in the graph that includes one or more additional nodes other than the origin node and the second destination node, and
the determining (E) up-weights the first path relative to the second path when the first path has higher average coverage than the second path.
4. The sequencing method of claim 1 , wherein the
the first origin node and the first destination node are part of a first path in the graph that includes one or more additional nodes other than the origin node and the first destination node,
the first origin node and the second destination node are part of a second path in the graph that includes one or more additional nodes other than the origin node and the second destination node, and
the determining (E) up-weights the first path relative to the second path when the first path represents a longer contiguous portion of the larger contiguous nucleic acid sequence than the second path.
5. The sequencing method of claim 1 , wherein a first k-mer in the first node is present in a sub-plurality of the plurality of oligonucleotide sequence reads and the identity of each oligonucleotide sequence read in the sub-plurality of oligonucleotide sequence reads is retained for the first k-mer and used by the determining (E) to determine whether the first path is more likely representative of the larger contiguous nucleic acid oligonucleotide sequence than the second path.
6. The sequencing method of claim 1 , wherein
a reaction vessel partition in the plurality of reaction vessel partitions comprises at least 1000 molecules with the common second portion, and
each molecule in the at least 1000 molecules further comprises a primer oligonucleotide sequence complementary to at least a portion of the larger contiguous nucleic acid.
7. The sequencing method of claim 1 , wherein
a reaction vessel partition in the plurality of reaction vessel partitions comprises at least 1000 molecules with the common second portion, and
each molecule in the at least 1000 molecules further comprises a primer site and a semi-random N-mer priming oligonucleotide sequence that is complementary to part of the larger contiguous nucleic acid.
8. The sequencing method of claim 1 , wherein the one or more fragments of the larger contiguous nucleic acid in a reaction vessel partition in the plurality of reaction vessel partitions are greater than 50 kilobases in length.
9. The sequencing method of claim 1 , wherein the one or more fragments of the larger contiguous nucleic acid in a reaction vessel partition in the plurality of reaction vessel partitions are between 20 kilobases and 200 kilobases in length.
10. The sequencing method of claim 1 , wherein the one or more fragments of the larger contiguous nucleic acid in a reaction vessel partition in the plurality of reaction vessel partitions consists of between 1 and 500 different fragments of the larger contiguous nucleic acid.
11. The sequencing method of claim 1 , wherein the one or more fragments of the larger contiguous nucleic acid in a reaction vessel partition in the plurality of reaction vessel partitions consists of between 5 and 100 fragments of the larger contiguous nucleic acid.
12. The sequencing method of claim 1 , wherein the plurality of oligonucleotide sequence reads is obtained from less than 5 nanograms of nucleic or ribonucleic acid.
13. The sequencing method of claim 1 , wherein the identifier in the second portion of each respective oligonucleotide sequence read in the set of oligonucleotide sequence reads encodes a common value selected from the set {1, . . . , 1024}, the set {1, . . . , 4096}, the set {1, . . . , 16384}, the set {1, . . . , 65536}, the set {1, . . . , 262144}, the set {1, . . . , 1048576}, the set {1, . . . , 4194304}, the set {1, . . . , 16777216}, the set {1, . . . , 67108864}, or the set {1, . . . , 1×10 12 }.
14. The sequencing method of claim 1 , wherein the identifier is an N-mer, and N is an integer selected from the set {4, . . . , 20}.
15. The sequencing method of claim 1 , wherein an average oligonucleotide sequence read length of the plurality of oligonucleotide sequence reads is between 40 bases and 200 bases.
16. The sequencing method of claim 1 , wherein an average oligonucleotide sequence read length of the plurality of oligonucleotide sequence reads is between 60 bases and 140 bases.
17. The sequencing method of claim 1 , wherein
the plurality of oligonucleotide sequence reads collectively provide at least 15× coverage for the larger contiguous nucleic acid,
more than ten percent of the k-mers in the plurality of k-mers are from more than one oligonucleotide sequence read in the plurality oligonucleotide sequence reads, and
the identifier of each oligonucleotide sequence read for each k-mer represented by more than one oligonucleotide sequence read is retained.
18. The sequencing method of claim 1 , wherein
the plurality of oligonucleotide sequence reads collectively provide at least 25× coverage for the larger contiguous nucleic acid,
more than thirty percent of the plurality of k-mers are from more than one oligonucleotide sequence read in the plurality oligonucleotide sequence reads, and
the identifier of each oligonucleotide sequence read for each k-mer represented by more than one source oligonucleotide sequence read is retained.
19. The sequencing method of claim 1 , wherein the oligonucleotide sequence reads in the plurality of oligonucleotide sequence reads encode between 75 and 125 bases of the larger contiguous nucleic acid and the value k is an odd integer between 5 and 73.
20. The sequencing method of claim 1 , wherein a set of oligonucleotide sequence reads in the plurality of oligonucleotide sequence reads comprises more than 100 oligonucleotide sequence reads, and each oligonucleotide sequence read of the more than 100 oligonucleotide sequence reads includes the same common second portion.
21. The sequencing method of claim 1 , wherein the larger contiguous nucleic acid is a chromosome.
22. The sequencing method of claim 1 , wherein the larger contiguous nucleic acid is greater than 40 million base pairs in length.
23. The sequencing method of claim 1 , wherein creating the respective set of k-mers comprises hashing each oligonucleotide sequence read in the plurality of oligonucleotide sequence reads according to a predetermined k-mer length thereby creating a respective set of k-mers for each oligonucleotide sequence read in the plurality of oligonucleotide sequence reads.