Patent Application

App. No. 15/452,963

Abstract

Claims (71)

1 . A system, comprising:

at least one computer hardware processor; and

at least one non-transitory computer-readable storage medium storing processor-executable instructions that, when executed by the at least one computer hardware processor, cause the at least one computer hardware processor to perform:

accessing a biological sequence;

accessing a graph reference construct representing a graph through which there are multiple paths including a first path and a second path, the graph comprising a plurality of nodes including first, second, and third nodes, the first node preceding the third node along the first path, and the second node preceding the third node along the second path;

aligning the biological sequence to the graph reference construct, the aligning comprising:

accessing first state data indicating an extent to which each of multiple subsequences of the biological sequence matches the graph reference construct when aligned to the graph reference construct so as to end at a last position of a sequence represented by the first node;

accessing second state data indicating an extent to which each of the multiple subsequences of the biological sequence matches the graph reference construct when aligned to the graph reference construct so as to end at a last position of a sequence represented by the second node;

generating third state data using the first state data and the second state data, the third state data indicating an extent to which each of the multiple subsequences of the biological sequence matches the graph reference construct when aligned to the graph reference construct so as to end at a first position of a sequence represented by the third node; and

storing the third state data.

2 . The system of claim 1 , wherein the multiple subsequences of the biological sequence include a first subsequence, and wherein generating the third state data comprises:

determining a number of errors between the first subsequence and the graph reference construct, when the first subsequence is aligned to the graph reference construct so as to end at the first position of the sequence represented by the third node; and

including a value indicating the determined number of errors in the third state data.

3 . The system of claim 2 , wherein determining the number of errors comprises:

determining a first number of errors between the first subsequence and the graph reference construct, when the first subsequence is aligned to the graph reference construct so as to end at the last position of the sequence represented by first node;

determining a second number of errors between the first subsequence and the graph reference construct, when the first subsequence is aligned to the graph reference construct so as to end at the last position of the sequence represented by the second node; and

determining the number of errors based on a minimum of the first number of errors and the second number of errors.

4 . The system of claim 1 , wherein the multiple subsequences of the biological sequence include a first subsequence, and wherein generating the third state data comprises:

determining whether the first subsequence matches the graph reference construct exactly when aligned to the graph reference construct so as to end at the first position of the sequence represented by the third node; and

including a value indicating a result of the determination in the third state data.

5 . The system of claim 2 , wherein the value is a 0 or a 1.

6 . The system of claim 1 , wherein the first state data includes first binary data, the second state data includes second binary data, and the third state data includes third binary data, and wherein generating the third state data comprises:

generating the third binary data by applying at least one bitwise operation to the first binary data and the second binary data.

7 . The system of claim 6 , wherein the at least one bitwise operation comprises a bitwise OR operation.

8 . The system of claim 6 , wherein the at least one bitwise operation comprises a bitwise AND operation.

9 . The system of claim 1 , wherein generating the third state data comprises:

for each one of the multiple subsequences,

generating a respective binary value indicating whether the each one multiple subsequence exactly matches the graph reference construct when aligned to the graph reference construct so as to end at the first position of the sequence represented by third node; and

including the respective binary value in the third state data.

10 . The system of claim 1 , wherein the sequence represented by the third node consists of a single nucleotide, wherein the plurality of nodes includes a fourth node following the third node in the graph, and wherein the aligning further comprises:

accessing the third state data;

generating fourth state data using the third state data, the fourth state data indicating an extent to which each of the multiple subsequences of the biological sequence matches the graph reference construct when aligned to the graph reference construct so as to end at the fourth node; and

storing the fourth state data.

11 . The system of claim 1 , wherein the sequence represented by the third node consists of multiple nucleotides including, and wherein the aligning further comprises:

accessing the third state data;

generating fourth state data using the third state data, the fourth state data indicating an extent to which each of the multiple subsequences of the biological sequence matches the graph reference construct when aligned to the graph reference construct so as to end at a second position of the sequence represented by the third node; and

storing the fourth state data.

12 . The system of claim 1 , wherein the aligning further comprises:

for each position of each subsequence represented by a respective node in the plurality of nodes,

generating respective state data indicating an extent to which each of the multiple subsequences of the biological sequence matches the graph reference construct when aligned to the graph reference construct so as to end at the position.

13 . A method, comprising:

using at least one computer hardware processor to perform:

accessing a biological sequence;

accessing a graph reference construct representing a graph through which there are multiple paths including a first path and a second path, the graph comprising a plurality of nodes including first, second, and third nodes, the first node preceding the third node along the first path, and the second node preceding the third node along the second path;

aligning the biological sequence to the graph reference construct, the aligning comprising:

accessing first state data indicating an extent to which each of multiple subsequences of the biological sequence matches the graph reference construct when aligned to the graph reference construct so as to end at a last position of a sequence represented by the first node;

accessing second state data indicating an extent to which each of the multiple subsequences of the biological sequence matches the graph reference construct when aligned to the graph reference construct so as to end at a last position of a sequence represented by the second node;

generating third state data using the first state data and the second state data, the third state data indicating an extent to which each of the multiple subsequences of the biological sequence matches the graph reference construct when aligned to the graph reference construct so as to end at a first position of a sequence represented by the third node; and

storing the third state data.

14 . The method of claim 13 , wherein the multiple subsequences of the biological sequence include a first subsequence, and wherein generating the third state data comprises:

determining whether the first subsequence matches the graph reference construct exactly when aligned to the graph reference construct so as to end at the first position of the sequence represented by the third node; and

including a value indicating a result of the determination in the third state data,

wherein the value is a 0 or a 1.

15 . The method of claim 13 , wherein the first state data includes first binary data, the second state data includes second binary data, and the third state data includes third binary data, and wherein generating the third state data comprises:

generating the third binary data by applying at least one bitwise operation to the first binary data and the second binary data.

16 . The method of claim 15 , wherein the at least one bitwise operation comprises a bitwise OR operation.

17 . The method of claim 15 , wherein the at least one bitwise operation comprises a bitwise AND operation.

18 . At least one non-transitory computer-readable storage medium storing processor-executable instructions that, when executed by at least one computer hardware processor, cause the at least one computer hardware processor to perform:

accessing a biological sequence;

accessing a graph reference construct representing a graph through which there are multiple paths including a first path and a second path, the graph comprising a plurality of nodes including first, second, and third nodes, the first node preceding the third node along the first path, and the second node preceding the third node along the second path;

aligning the biological sequence to the graph reference construct, the aligning comprising:

accessing first state data indicating an extent to which each of multiple subsequences of the biological sequence matches the graph reference construct when aligned to the graph reference construct so as to end at the first node;

accessing second state data indicating an extent to which each of the multiple subsequences of the biological sequence matches the graph reference construct when aligned to the graph reference construct so as to end at the second node;

generating third state data using the first state data and the second state data, the third state data indicating an extent to which each of the multiple subsequences of the biological sequence matches the graph reference construct when aligned to the graph reference construct so as to end at the third node; and

storing the third state data.

19 . The at least one non-transitory computer-readable storage medium of claim 18 , wherein the multiple subsequences of the biological sequence include a first subsequence, and wherein generating the third state data comprises:

determining whether the first subsequence matches the graph reference construct exactly when aligned to the graph reference construct so as to end at the first position of the sequence represented by the third node; and

including a value indicating a result of the determination in the third state data,

wherein the value is a 0 or a 1.

20 . The at least one non-transitory computer-readable storage medium of claim 18 , wherein the first state data includes first binary data, the second state data includes second binary data, and the third state data includes third binary data, and wherein generating the third state data comprises:

generating the third binary data by applying at least one bitwise operation to the first binary data and the second binary data.

Assignments (8)