# US 10,319,465 B2 · Systems and methods for aligning sequences to graph references

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,319,465 B2
- Document ID: US10319465B2
- Status: Granted
- Kind: B2
- Application number: 15/353,105
- Filed: 2016-11-16
- Published: 2018-05-17
- Granted: 2019-06-11
- Earliest claimed: 2016-11-16
- Assignees: Seven Bridges Genomics Inc.
- Applicants: Seven Bridges Genomics Inc.
- Inventors: Wan-Ping Lee; Alyssa Dayan
- Web page: https://patentgrep.com/patent/US10319465B2

## CPC

- G16B 45/00: ICT specially adapted for bioinformatics-related data visualisation, e.g. displaying of maps or networks
- G06V 20/693: {Acquisition}
- G06V 20/698: {Matching; Classification}
- G06V 30/1988: {Graph matching (graphical image representation G06V30/18181)}
- G06V 2201/04: Recognition of patterns in DNA microarrays
- G16B 30/20: Sequence assembly
- G16B: BIOINFORMATICS, i.e. INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR GENETIC OR PROTEIN-RELATED DATA PROCESSING IN COMPUTATIONAL MOLECULAR BIOLOGY
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING

## Abstract

Various embodiments of the disclosure relate to systems and methods for aligning a sequence read to a graph reference. In one embodiment, the method comprises selecting a first node from a graph reference, the graph reference comprising a plurality of nodes connected by a plurality of directed edges, at least one node of the plurality of nodes having a nucleotide sequence. The method further comprises traversing the graph reference according to a depth-first search, and comparing a sequence read to nucleotide sequences generated from the traversal of the graph reference. The traversal of the graph is then modified in response to a determination that each and every node associated with a given nucleotide sequence was previously evaluated.

## Claims

### Claim 1

A system for aligning a sequence read to a graph reference, the system comprising:
at least one computer hardware processor; and
at least one non-transitory computer-readable storage medium storing: a graph reference, the graph reference comprising a plurality of nodes connected by a plurality of edges, at least one node of the plurality of nodes having an associated nucleotide sequence; a plurality of sequence reads; and processor-executable instructions that, when executed by the at least one computer hardware processor, cause the at least one computer hardware processor to perform:
selecting a first node of the plurality of nodes;
identifying a first path by traversing the graph reference, the first path starting from the first node and comprising at least one child node of the first node;
comparing at least one first nucleotide sequence generated from the first path with the sequence read, wherein the at least one first nucleotide sequence is generated at least in part by concatenating associated nucleotide sequences from nodes in the first path into the at least one first nucleotide sequence;
identifying a second path by traversing the graph reference, the second path starting from the first node and comprising at least one node not considered by the first path;
comparing at least one second nucleotide sequence generated from the second path with the sequence read, the comparing comprising determining whether the at least one second nucleotide sequence generated from the second path was previously generated by the first path, and removing one or more nodes from the identified second path based on the determination;
determining a best-fit position of the sequence read on the graph reference; and
reporting the best-fit position of the sequence read as the aligned position of the sequence read on the graph reference.

### Claim 2 (depends on 1)

The system of claim 1, wherein traversing the graph reference comprises performing a depth-first search.

### Claim 3 (depends on 1)

The system of claim 1, wherein a path comprises one or more nodes.

### Claim 4 (depends on 1)

The system of claim 1, wherein identifying a first path by traversing the graph reference comprises following outgoing edges of successive nodes until reaching a last node having no outgoing edges.

### Claim 5 (depends on 4)

The system of claim 4, wherein identifying a second path by traversing the graph reference comprises backtracking from the last node having no outgoing edges.

### Claim 6 (depends on 5)

The system of claim 5, wherein backtracking from the last node having no outgoing edges further comprises identifying a node having a previously unfollowed outgoing edge, following the previously unfollowed outgoing edge, and following outgoing edges of successive nodes until reaching a last node having no outgoing edges.

### Claim 7 (depends on 1)

The system of claim 1, wherein each node further comprises a followed indicator that indicates which of its outgoing directed edges have been traversed, and traversing the graph reference further comprises updating the followed indicator when following an outgoing edge from that node.

### Claim 8 (depends on 7)

The system of claim 7, wherein each node further comprises a visited indicator that indicates whether all of its outgoing directed edges have been traversed, wherein traversing the graph reference further comprises:
determining whether a node's followed indicator indicates that all of its outgoing directed edges have been traversed;
updating the node's visited indicator to indicate that all of the outgoing directed edges have been traversed;
resetting the node's followed indicator to indicate that all of the outgoing directed edges have not been traversed; and
backtracking from the node.

### Claim 9 (depends on 8)

The system of claim 8, wherein comparing at least one second nucleotide sequence generated from the second path with the sequence read further comprises considering whether the at least one second nucleotide sequence is generated entirely from nodes having visited indicators that indicate all of the outgoing directed edges of those nodes have been traversed.

### Claim 10 (depends on 1)

The system of claim 1, wherein comparing at least one first nucleotide sequence generated from the first path with the sequence read further comprises:
identifying a first set of substrings of the at least one first nucleotide sequence; and
comparing the first set of substrings to the sequence read.

### Claim 11 (depends on 10)

The system of claim 10, wherein comparing at least one second nucleotide sequence generated from the second path with the sequence read comprises:
concatenating nucleotide sequences associated with the nodes in the second path into a second concatenated nucleotide sequence;
identifying a second set of substrings of the second concatenated nucleotide sequence;
comparing each substring of the second set of substrings to the sequence read if and only if a substring is not within the first set of substrings.

### Claim 12 (depends on 11)

The system of claim 11, wherein comparing each substring of the second set of substrings to the sequence read if and only if a substring is not within the first set of substrings comprises considering whether a substring is generated from at least one node that was not present in the first path.

### Claim 13 (depends on 12)

The system of claim 12, wherein each node further comprises a visited indicator that indicates whether all of that node's outgoing directed edges have been traversed, and comparing each substring of the second set of substrings further comprises:
determining whether each of the nodes associated with a substring have visited indicators that indicate all of the outgoing directed edges of those nodes have been traversed;
if each of the nodes associated with the substring have visited indicators that indicate all of the outgoing directed edges of those nodes have been traversed, removing the most recently added node from the second path and considering whether any remaining nodes in the second path have an unfollowed outgoing edge; and
if any of the nodes associated with the substring have visited indicators that indicate all of the outgoing directed edges of those nodes have not been traversed, comparing the substring with the sequence read.

### Claim 14 (depends on 13)

The system of claim 13, wherein comparing the substring with the sequence read further comprises generating the substring from those nodes.

### Claim 15 (depends on 1)

The system of claim 1, wherein identifying a second path by traversing the graph reference comprises:
identifying a quantity of nodes within the graph reference;
traversing a portion of the graph reference; and
modifying traversal of the graph in response to a determination that a region of the graph has been previously considered by the first path.

### Claim 16 (depends on 1)

The system of claim 1, wherein identifying a first path by traversing the graph reference comprises:
considering whether the first node has an unfollowed child node;
if the first node has an unfollowed child node, adding the unfollowed child node to the first path.

### Claim 17 (depends on 1)

The system of claim 1, wherein the sequence read comprises a k-mer of the sequence read, wherein comparing nucleotide sequences generated from a path with the sequence read comprises comparing a k-mer of the sequence read with the nucleotide sequences.

### Claim 18 (depends on 17)

The system of claim 17, wherein the k-mer begins from the first base of the sequence read.

### Claim 19 (depends on 17)

The system of claim 17, wherein the length of the k-mer is between 5 and 30 base pairs.

### Claim 20 (depends on 17)

The system of claim 17, further comprising determining one or more best-fit positions of the k-mer of the sequence read.

### Claim 21 (depends on 20)

The system of claim 20, further comprising determining a best-fit position of the sequence read by considering additional nucleotides adjacent to the best-fit positions of the kmer of the sequence read.

### Claim 22 (depends on 1)

The system of claim 1, wherein determining a best-fit position of the sequence read on the graph reference further comprises:
aligning the sequence read to the graph reference using a second alignment algorithm.

### Claim 23 (depends on 22)

The system of claim 22, wherein the second alignment algorithm is selected from the group consisting of: the Smith-Waterman algorithm and a graph-aware Smith-Waterman algorithm.