MULTI-SCALE SHORT READ ASSEMBLY
The invention generally provides methods for analyzing and constructing nucleic acid sequences and more specifically for assembling a collection of short read nucleic acid sequences to construct longer nucleic acid sequences.
1 . A method for constructing a target nucleic acid sequence, comprising:
a) obtaining a plurality of subsequences of a target nucleic acid, wherein the plurality of subsequences are segments of and together form substantially a complete sequence of the target nucleic acid;
b) selecting an initial subsequence from the plurality of subsequences and an end base thereof and analyzing the sequence information of the plurality of subsequences to obtain a statistical probability value for the base position next to the selected end base of the initial subsequence;
c) analyzing the sequence information of the plurality of subsequences to obtain a statistical probability value for the base position next to the analyzed base position in b); and
d) repeating step c) for the subsequent end positions to construct substantially a full sequence of the target nucleic acid.
2 . The method of claim 1 , wherein in said analyzing step comprises constructing a multi-scale de Bruijn graph.
3 . The method of claim 2 , wherein the de Bruijn graph utilizes a single weighted matrix.
4 . The method of claim 2 , wherein the de Bruijn graph utilizes a multiple weighted matrix.
5 . The method of claim 1 , wherein the sequence information for the plurality of subsequence is obtained using a sequencing-by-synthesis process.
6 . The method of claim 5 , wherein the sequencing-by-synthesis process is a single molecule sequencing-by-synthesis process.
7 . The method of claim 1 , wherein the sequence information for the plurality of subsequence is obtained using a sequencing-by-ligation process.
8 . The method of claim 1 , further comprising constructing a second target nucleic acid.
9 . The method of claim 8 , further comprising constructing a third or more target nucleic acid.
10 . The method of claim 1 , wherein the target nucleic sequence is from a sample obtained from a single subject.
11 . The method of claim 1 , wherein the target nucleic sequences are from a sample obtained from a single subject.
12 . The method of claim 1 , wherein the target nucleic sequences are from samples obtained from more than one subject.
13 . The method of claim 1 , wherein the subsequences are sequences having 35 or fewer base pairs.
14 . The method of claim 1 , wherein the target nucleic acid sequence is 1,000 base pairs or longer.
15 . A method for assembling the sequence of a target nucleic acid having known subsequences, comprising:
a) selecting an initial subsequence from known subsequences and an end base thereof and analyzing the sequence information of the known subsequences to obtain a statistical probability value for the base position next to the selected end base of the initial subsequence;
b) analyzing the sequence information of the known subsequences to obtain a statistical probability value for the base position next to the base position in a); and
c) repeating step b) for the next base positions to construct the full sequence of the target nucleic acid.
16 . The method of claim 15 , wherein b)-c) utilize a single-weighted matrix process.
17 . The method of claim 15 , wherein b)-c) utilize a multiple-weighted matrix process.
18 . The method of claim 15 , wherein the subsequences are sequences having 35 or fewer base pairs.
19 . The method of claim 15 , wherein the target nucleic acid is 1,000 base pairs or longer.
20 . The method of claim 15 , further comprising assembling the sequence of a second target nucleic acid.
21 . The method of claim 20 , further comprising constructing a third or more target nucleic acid.
22 . A method for sequencing a target nucleic acid, comprising:
a) sequencing a plurality of subsequences of a target nucleic acid, wherein the plurality of subsequences are segments of and together form a substantially complete sequence of the target nucleic acid sequence; and
b) assembling the subsequences via a de Bruijn graph process.
23 . The method of claim 22 , wherein b) utilizes a single-weighted matrix process.
24 . The method of claim 22 , wherein b) utilizes a multiple-weighted matrix process.
25 . The method of claim 22 , wherein the subsequences are sequences having 35 or fewer base pairs.
26 . The method of claim 22 , wherein the target nucleic acid is 1,000 base pairs or longer.