Back to results
US 12,586,661 B2Granted
Hardware accelerated K-mer graph generation
AssigneeIllumina, Inc.
InventorMichael Ruehle
Life of this patent
Estimating the term…
Abstract
Methods, systems, and apparatus for hardware-accelerated generation of a K-mer graph using a programmable logic device. In one aspect, a method includes actions of obtaining a first set of nucleic acid sequences, generating a K-mer graph using the obtained first set of nucleic acid sequences and using a plurality of non-pipelined hardware logic units of a programmable logic device, and periodically updating, with a control machine, graph description data for the K-mer graph after performance of the one or more operations by each hardware logic unit.
Claims20
A method for hardware-accelerated generation of a K-mer graph using a programmable logic device, the method comprising:
- obtaining a first set of nucleic acid sequences, wherein the first set of nucleic acid sequences includes (i) a plurality of reads corresponding to a region of a reference sequence and (ii) a portion of the reference sequence;
- generating, using a plurality of non-pipelined hardware logic units of a programmable logic device a K-mer graph using the obtained first set of nucleic acid sequences, wherein each hardware logic unit comprises a different hardware logic circuit configured to perform one or more operations, wherein each node of the K-mer graph represents a K-mer, each edge of the K-mer graph represents a link between a pair of K-mers, and each weight of each edge of the K-mer graph represents a number of occurrences of a K-mer sequence represented by a pair of K-mers;
- and
- during generation of the K-mer graph:
- periodically updating, with a control machine, graph description data for the K-mer graph after performance of the one or more operations by each hardware logic unit that is used to generate at least a portion of the K-mer graph, wherein the graph description data represents (i) a K-mer graph identifier and (ii) K-mer graph state information, wherein the control machine creates a workflow of operations using the plurality of non-pipelined hardware logic units by triggering performance of the one or more operations of each respective hardware logic unit during generation of the K-mer graph.
2 more elements
A system for hardware-accelerated generation of a K-mer graph using a programmable logic device, the system comprising:
- a hardware-accelerated graph generation unit that includes hardware digital logic circuits that have been arranged to perform operations, the operations comprising:
- obtaining a first set of nucleic acid sequences, wherein the first set of nucleic acid sequences includes (i) a plurality of reads corresponding to a region of a reference sequence and (ii) a portion of the reference sequence;
- generating, using a plurality of non-pipelined hardware logic units of a programmable logic device a K-mer graph using the obtained first set of nucleic acid sequences, wherein each hardware logic unit comprises a different hardware logic circuit configured to perform one or more operations, wherein each node of the K-mer graph represents a K-mer, each edge of the K-mer graph represents a link between a pair of K-mers, and each weight of each edge of the K-mer graph represents a number of occurrences of a K-mer sequence represented by a pair of K-mers;
- and
- during generation of the K-mer graph:
- periodically updating, with a control machine, graph description data for the K-mer graph after performance of the one or more operations by each hardware logic unit that is used to generate at least a portion of the K-mer graph, wherein the graph description data represents (i) a K-mer graph identifier and (ii) K-mer graph state information, wherein the control machine creates a workflow of operations using the plurality of non-pipelined hardware logic units by triggering performance of the one or more operations of each respective hardware logic unit during generation of the K-mer graph.
3 more elements
A hardware-accelerated graph generation unit that includes hardware digital logic circuits that have been arranged to perform operations, the operations comprising:
- obtaining a first set of nucleic acid sequences, wherein the first set of nucleic acid sequences includes (i) a plurality of reads corresponding to a region of a reference sequence and (ii) a portion of the reference sequence;
- generating, using a plurality of non-pipelined hardware logic units of a programmable logic device a K-mer graph using the obtained first set of nucleic acid sequences, wherein each hardware logic unit comprises a different hardware logic circuit configured to perform one or more operations, wherein each node of the K-mer graph represents a K-mer, each edge of the K-mer graph represents a link between a pair of K-mers, and each weight of each edge of the K-mer graph represents a number of occurrences of a K-mer sequence represented by a pair of K-mers;
- and
- during generation of the K-mer graph:
- periodically updating, with a control machine, graph description data for the K-mer graph after performance of the one or more operations by each hardware logic unit that is used to generate at least a portion of the K-mer graph, wherein the graph description data represents (i) a K-mer graph identifier and (ii) K-mer graph state information, wherein the control machine creates a workflow of operations using the plurality of non-pipelined hardware logic units by triggering performance of the one or more operations of each respective hardware logic unit during generation of the K-mer graph.
2 more elements
A method for hardware-accelerated generation of a K-mer graph using a programmable logic device, the method comprising:
- obtaining a first set of nucleic acid sequences, wherein the first set of nucleic acid sequences includes (i) a plurality of reads corresponding to a region of a reference sequence and (ii) a portion of the reference sequence;
- generating, using a plurality of non-pipelined hardware logic units of a programmable logic device a K-mer graph using the obtained first set of nucleic acid sequences, wherein each hardware logic unit comprises a different hardware logic circuit configured to perform one or more operations, wherein each node of the K-mer graph represents a K-mer, each edge of the K-mer graph represents a link between a pair of K-mers, and each weight of each edge of the K-mer graph represents a number of occurrences of a K-mer sequence represented by a pair of K-mers;
- and
- during generation of the K-mer graph:
- performing at least one of activating and configuring, using a control machine, a hardware logic unit of the plurality of non-pipelined hardware logic units to be used to generate at least a portion of the K-mer graph, the hardware logic unit to perform the one or more operations defined to be performed by the hardware logic unit;
- updating, using the control machine, graph description data for the K-mer graph based on performance of the one or more operations by the hardware logic unit, wherein the graph description data represents at least one of (i) a K-mer graph identifier and (ii) K-mer graph state information;
- and
- performing at least one of activating and configuring, using the control machine, another hardware logic unit of the plurality of non-pipelined hardware logic units, based on the updating the graph description data, wherein the control machine creates a workflow of operations using the plurality of non-pipelined hardware logic units by triggering performance of the one or more operations of each respective hardware logic unit during generation of the K-mer graph.
5 more elements
A system for hardware-accelerated generation of a K-mer graph using a programmable logic device, the system comprising:
- a hardware-accelerated graph generation unit that includes hardware digital logic circuits that have been arranged to perform operations, the operations comprising:
- obtaining a first set of nucleic acid sequences, wherein the first set of nucleic acid sequences includes (i) a plurality of reads corresponding to a region of a reference sequence and (ii) a portion of the reference sequence;
- generating, using a plurality of non-pipelined hardware logic units of a programmable logic device a K-mer graph using the obtained first set of nucleic acid sequences, wherein each hardware logic unit comprises a different hardware logic circuit configured to perform one or more operations, wherein each node of the K-mer graph represents a K-mer, each edge of the K-mer graph represents a link between a pair of K-mers, and each weight of each edge of the K-mer graph represents a number of occurrences of a K-mer sequence represented by a pair of K-mers;
- and
- during generation of the K-mer graph:
- performing at least one of activating and configuring, using a control machine, a hardware logic unit of the plurality of non-pipelined hardware logic units to be used to generate at least a portion of the K-mer graph, the hardware logic unit to perform the one or more operations defined to be performed by the hardware logic unit;
- updating, using the control machine, graph description data for the K-mer graph based on performance of the one or more operations by the hardware logic unit, wherein the graph description data represents at least one of (i) a K-mer graph identifier and (ii) K-mer graph state information;
- and
- performing at least one of activating and configuring, using the control machine, another hardware logic unit of the plurality of non-pipelined hardware logic units, based on the updating the graph description data, wherein the control machine creates a workflow of operations using the plurality of non-pipelined hardware logic units by triggering performance of the one or more operations of each respective hardware logic unit during generation of the K-mer graph.
6 more elements
A hardware-accelerated graph generation unit that includes hardware digital logic circuits that have been arranged to perform operations, the operations comprising:
- obtaining a first set of nucleic acid sequences, wherein the first set of nucleic acid sequences includes (i) a plurality of reads corresponding to a region of a reference sequence and (ii) a portion of the reference sequence;
- generating, using a plurality of non-pipelined hardware logic units of a programmable logic device a K-mer graph using the obtained first set of nucleic acid sequences, wherein each hardware logic unit comprises a different hardware logic circuit configured to perform one or more operations, wherein each node of the K-mer graph represents a K-mer, each edge of the K-mer graph represents a link between a pair of K-mers, and each weight of each edge of the K-mer graph represents a number of occurrences of a K-mer sequence represented by a pair of K-mers;
- and
- during generation of the K-mer graph:
- performing at least one of activating and configuring, using a control machine, a hardware logic unit of the plurality of non-pipelined hardware logic units to be used to generate at least a portion of the K-mer graph, the hardware logic unit to perform the one or more operations defined to be performed by the hardware logic unit;
- updating, using the control machine, graph description data for the K-mer graph based on performance of the one or more operations by the hardware logic unit, wherein the graph description data represents at least one of (i) a K-mer graph identifier and (ii) K-mer graph state information;
- and
- performing at least one of activating and configuring, using the control machine, another hardware logic unit of the plurality of non-pipelined hardware logic units, based on the updating the graph description data, wherein the control machine creates a workflow of operations using the plurality of non-pipelined hardware logic units by triggering performance of the one or more operations of each respective hardware logic unit during generation of the K-mer graph.
5 more elements
Dependencies are inferred from the claim text.