Methods and systems for aligning sequences
The invention includes methods for aligning reads (e.g., nucleic acid reads, amino acid reads) to a reference sequence construct, methods for building the reference sequence construct, and systems that use the alignment methods and constructs to produce sequences. The method is scalable, and can be used to align millions of reads to a construct thousands of bases or amino acids long. The invention additionally includes methods for identifying a disease or a genotype based upon alignment of nucleic acid reads to a location in the construct.
1. A system for aligning a plurality of sequence reads, the system comprising:
a processor; and
a tangible, non-transitory memory storing a plurality of sequence reads from a subject, and a reference directed acyclic graph (DAG) representing a reference sequence and genetic variation of the reference sequence, wherein the reference DAG comprises a plurality of nodes, wherein each node is stored in the memory as a string of one or more symbols and a set of parent nodes, the string representing a sequence and the set of parent nodes defining the node's position with respect to other nodes in the reference DAG;
wherein the plurality of nodes further comprises a first node, a second node, and a third node, the third node having the first node and the second node as parent nodes, and wherein each of the first node, second node, and third node comprise different strings comprising a plurality of symbols;
wherein the memory further comprises instructions that, when executed, cause the processor to align a sequence read of the plurality of sequence reads to the reference DAG by:
creating, in the memory, a matrix for each respective node of the reference DAG, the creating comprising creating for each of the first node, the second node, and the third node, a matrix representing a comparison between the sequence read and a string associated with its respective node;
for each created matrix, scoring overlaps between the sequence read and the string associated with its respective node, the scoring comprising calculating a score for each entry of the matrix based at least in part on whether a symbol of the sequence read matches a corresponding symbol of the string associated with its respective node;
wherein calculating a score further comprises determining highest scores from matrices from parent nodes if and only if a matrix entry comprises the first symbol of the string associated with its node, such that scores for matrix entries for the first symbol of the string associated with the third node comprise a highest score from the matrix of the first node and the matrix of the second node;
identifying a highest overall score in the calculated scores, the highest overall score having a position in one of the created matrices;
backtracking from the position of the highest overall score to produce an actual match for the sequence read to the reference DAG, thereby aligning the sequence read to the reference DAG; and
writing a file to the memory corresponding to the actual match for the sequence read.
2. The system of claim 1 , wherein the sequence reads are nucleic acid sequence reads.
3. The system of claim 1 , wherein the instructions further comprise aligning the plurality of sequence reads to the reference and assembling the plurality of sequence reads into an assembled sequence based upon the aligned location of each sequence read, wherein the assembled sequence is a genetic sequence of the subject.
4. The system of claim 3 , wherein the genetic sequence is a chromosome or a genome.
5. The system of claim 1 , further comprising assigning a genotype to the subject based upon the location of one or more aligned sequence reads.
6. The system of claim 5 , further comprising correlating the assigned genotype with a risk of disease for the subject.
7. The system of claim 6 , wherein the disease is cancer.
8. The system of claim 1 , wherein the reference DAG comprises a database of positions and symbols stored on a non-transitory computer-readable medium.
9. The system of claim 1 , wherein the system comprises a plurality of processors, and wherein each processor is configured to compare and score a portion of the plurality of sequence reads against the reference DAG.
10. The system of claim 1 , wherein the memory additionally comprises instructions that cause a first processor to instruct a second processor to create, score, identify, backtrack, and align, and then send the aligned location to the first processor.
11. The system of claim 1 , wherein each node further comprises a position that corresponds to a nucleic acid in a reference sequence.
12. The system of claim 1 , wherein the first node and the second node of the reference DAG correspond to the same gene in a reference sequence.
13. The system of claim 1 , wherein a path through the reference DAG represents a chromosome of an organism.
14. The system of claim 1 , wherein the reference DAG further comprises a fourth node and a fifth node that correspond to nucleic acid sequences differing from each other by a base insertion or a base deletion.
15. The system of claim 1 , wherein the reference DAG comprises greater than 1,000 symbols.
16. The system of claim 15 , wherein the reference DAG comprises greater than 1,000,000 symbols.
17. The system of claim 16 , wherein the plurality of sequence reads comprises greater than 1000 sequence reads.
18. The system of claim 1 , wherein the plurality of sequence reads are output files of a next-generation sequencing method.
19. The system of claim 1 , wherein the reference DAG further includes diagnostic information correlated with the nucleotide sequence.
20. The system of claim 19 , wherein for at least one node the diagnostic information is breast cancer.
21. The system of claim 1 , wherein the second node has the first node as a parent node.
22. The system of claim 1 , wherein backtracking from the highest overall score to produce an actual match for the sequence read to the reference DAG comprises backtracking from the matrix for the third node to the matrix for either the second node or the first node.
23. The system of claim 1 , wherein the second node represents a structural variation.
24. The system of claim 1 , wherein the sequence reads are amino acid sequence reads.
25. The system of claim 1 , wherein each position on the reference DAG corresponds to an amino acid in a reference sequence.
26. The system of claim 1 , wherein a path through the reference DAG represents a genome of an organism.
27. The system of claim 1 , wherein a path through the reference DAG represents a protein.