Methods and systems for detecting sequence variants
The invention provides methods for identifying rare variants near a structural variation in a genetic sequence, for example, in a nucleic acid sample taken from a subject. The invention additionally includes methods for aligning reads (e.g., nucleic acid reads) to a reference sequence construct accounting for the structural variation, methods for building a reference sequence construct accounting for the structural variation or the structural variation and the rare variant, and systems that use the alignment methods to identify rare variants. The method is scalable, and can be used to align millions of reads to a construct thousands of bases long, or longer.
1. A method for aligning one or more sequence reads to a genomic reference graph, the one or more sequence reads having been previously obtained from a biological sample from a subject, the method comprising:
using at least one processor to perform:
accessing at least one data structure representing the genomic reference graph, the genomic reference graph representing at least 1,000,000 nucleic acids and comprising nodes and edges connecting the nodes, the nodes including a first node and one or more parent nodes of the first node, the first node representing a first nucleotide sequence stored as a first string of symbols, wherein the at least one data structure stores data specifying the nodes and edges;
aligning the one or more sequence reads to the genomic reference graph using the at least one data structure and a dynamic programming algorithm, the aligning comprising, for each particular sequence read of the one or more sequence reads:
determining scores for entries in a first matrix associated with the first node, the first matrix representing a comparison between the particular sequence read and the first string of symbols, the determining comprising:
determining whether a symbol of the particular sequence read matches a first symbol of the first string of symbols;
accessing a score from one or more matrices associated with the one or more parent nodes of the first node; and
determining a score for an entry in the first matrix based on: (i) a result of determining whether the symbol of the particular sequence read matches the first symbol of the first string of symbols and (ii) the score accessed from the one or more matrices associated with the one or more parent nodes; and
aligning the particular sequence read to the genomic reference graph based on the determined scores; and
generating output indicative of results of aligning the one or more sequence reads to the genomic reference graph.
2. The method of claim 1 , further comprising:
identifying, using the results of the aligning, a presence of a first genomic variant in the biological sample.
3. The method of claim 2 , wherein the first genomic variant is a deletion, a duplication, a copy-number variation, an insertion, a translocation, or any combination thereof.
4. The method of claim 2 , wherein the first node represents the first genomic variant, and wherein identifying the presence of the first genomic variant in the biological sample comprises:
determining, using the results of the aligning, whether at least one sequence read of the one or more sequence reads aligns, at least partially, to the first node.
5. The method of claim 2 , further comprising: identifying, using the results of the aligning and based on the presence of the first genomic variant in the biological sample, a presence of a second genomic variant in the biological sample.
6. The method of claim 1 , further comprising:
sequencing the biological sample to obtain the one or more sequence reads.
7. The method of claim 1 , wherein the genomic reference graph represents at least a portion of a genome of an organism and genetic variation of at least the portion of the genome of the organism.
8. At least one non-transitory storage medium storing processor-executable instructions that, when executed by at least one processor, cause the at least one processor to perform a method for aligning one or more sequence reads to a genomic reference graph, the one or more sequence reads having been previously obtained from a biological sample from a subject, the method comprising:
accessing at least one data structure representing the genomic reference graph, the genomic reference graph representing at least 1,000,000 nucleic acids and comprising nodes and edges connecting the nodes, the nodes including a first node and one or more parent nodes of the first node, the first node representing a first nucleotide sequence stored as a first string of symbols, wherein the at least one data structure stores data specifying the nodes and edges;
aligning the one or more sequence reads to the genomic reference graph using the at least one data structure and a dynamic programming algorithm, the aligning comprising, for each particular sequence read of the one or more sequence reads:
determining scores for entries in a first matrix associated with the first node, the first matrix representing a comparison between the particular sequence read and the first string of symbols, the determining comprising:
determining whether a symbol of the particular sequence read matches a first symbol of the first string of symbols;
accessing a score from one or more matrices associated with the one or more parent nodes of the first node; and
determining a score for an entry in the first matrix based on: (i) a result of determining whether the symbol of the particular sequence read matches the first symbol of the first string of symbols and (ii) the score accessed from the one or more matrices associated with the one or more parent nodes; and
aligning the particular sequence read to the genomic reference graph based on the determined scores; and
generating output indicative of results of aligning the one or more sequence reads to the genomic reference graph.
9. The at least one non-transitory storage medium of claim 8 , further comprising:
identifying, using the results of the aligning, a presence of a first genomic variant in the biological sample.
10. The at least one non-transitory storage medium of claim 9 , wherein the first genomic variant is a deletion, a duplication, a copy-number variation, an insertion, a translocation, or any combination thereof.
11. The at least one non-transitory storage medium of claim 9 , wherein the first node represents the first genomic variant, and wherein identifying the presence of the first genomic variant in the biological sample comprises:
determining, using the results of the aligning, whether at least one sequence read of the one or more sequence reads aligns, at least partially, to the first node.
12. The at least one non-transitory storage medium of claim 9 , further comprising: identifying, using the results of the aligning and based on the presence of the first genomic variant in the biological sample, a presence of a second genomic variant in the biological sample.
13. The at least one non-transitory storage medium of claim 8 , further comprising:
sequencing the biological sample to obtain the one or more sequence reads.
14. The at least one non-transitory storage medium of claim 8 , wherein the genomic reference graph represents at least a portion of a genome of an organism and genetic variation of at least the portion of the genome of the organism.
15. A system, comprising:
at least one processor; and
at least one non-transitory storage medium storing processor-executable instructions that, when executed by the at least one processor, cause the at least one processor to perform a method for aligning one or more sequence reads to a genomic reference graph, the one or more sequence reads having been previously obtained from a biological sample from a subject, the method comprising:
accessing at least one data structure representing the genomic reference graph, the genomic reference graph representing at least 1,000,000 nucleic acids and comprising nodes and edges connecting the nodes, the nodes including a first node and one or more parent nodes of the first node, the first node representing a first nucleotide sequence stored as a first string of symbols, wherein the at least one data structure stores data specifying the nodes and edges;
aligning the one or more sequence reads to the genomic reference graph using the at least one data structure and a dynamic programming algorithm, the aligning comprising, for each particular sequence read of the one or more sequence reads:
determining scores for entries in a first matrix associated with the first node, the first matrix representing a comparison between the particular sequence read and the first string of symbols, the determining comprising:
determining whether a symbol of the particular sequence read matches a first symbol of the first string of symbols;
accessing a score from one or more matrices associated with the one or more parent nodes of the first node; and
determining a score for an entry in the first matrix based on: (i) a result of determining whether the symbol of the particular sequence read matches the first symbol of the first string of symbols and (ii) the score accessed from the one or more matrices associated with the one or more parent nodes; and
aligning the particular sequence read to the genomic reference graph based on the determined scores; and
generating output indicative of results of aligning the one or more sequence reads to the genomic reference graph.
16. The system of claim 15 , further comprising:
identifying, using the results of the aligning, a presence of a first genomic variant in the biological sample.
17. The system of claim 16 , wherein the first genomic variant is a deletion, a duplication, a copy-number variation, an insertion, a translocation, or any combination thereof.
18. The system of claim 16 , wherein the first node represents the first genomic variant, and wherein identifying the presence of the first genomic variant in the biological sample comprises:
determining, using the results of the aligning, whether at least one sequence read of the one or more sequence reads aligns, at least partially, to the first node.
19. The system of claim 16 , further comprising: identifying, using the results of the aligning and based on the presence of the first genomic variant in the biological sample, a presence of a second genomic variant in the biological sample.
20. The system of claim 15 , further comprising:
sequencing the biological sample to obtain the one or more sequence reads.