Patent Description:
According to one innovative aspect of the present disclosure, a method for hardware-accelerated generation of a K-mer graph using a programmable logic device is disclosed as defined by claim <NUM>. According to another aspect, there is provided a hardware-accelerated graph generation unit as defined by claim <NUM>. According to another aspect, there is provided a system for hardware-accelerated generation of a K-mer graph using a programmable logic device, as defined by claim <NUM>. Further embodiments are provided as defined by the dependent claims.

These and other aspects of the present disclosure are discussed in more detail in the detailed description below with reference to the accompanying drawings.

Document <CIT> discloses systems and methods for performing bioinformatics analysis on genomic data and in particular, using de Bruijn Graphs for variant calling.

The present disclosure is directed towards hardware-accelerated generation of a K-mer graph. Generation of the K-mer graph using hardware circuits significantly reduces the amount of time required to generate the K-mer graph and offloads the computationally intensive K-mer graph generation process from a software processor to hardware logic of an integrated circuit such as a field programmable gate array or ASIC. This frees up software resources of the software processor that can be used to perform other genomic data processing tasks.

Hardware-accelerated generation of K-mer graphs can be achieved using a control machine that is configured to manage a workflow of operations performed by a plurality of non-pipelined hardware logic units. In particular, the control machine can abstractly achieve high-level pipelined functionality using the plurality of non-pipelined hardware logic units. The control machine can achieve this functionality by storing and updating graph description data that includes (i) a K-mer graph identifier that identifies an instance of a K-mer graph and (ii) K-mer graph state information. The K-mer graph state information can include, for example, data indicating a last hardware logic unit that operated on raw graph data for a particular instance of a K-mer graph, data indicating whether the last hardware logic unit aborted the operation, data indicating a K-mer length, data indicating a K-mer node list, data indicating a list of pointers that can be used to identify the K-mer nodes in a cache, a length of a K-mer node list, data indicating a list of non-unique K-mers, or any subset or combination thereof. The control machine manages K-mer graph generation by calling a particular hardware logic unit that is to perform an operation on a raw graph data and providing an updated set of graph description data to the called hardware logic unit.

This storage and updating of the graph description data enables the control machine to manage parallel processing of the non-pipelined hardware logic units in a manner that enables each of the non-pipelined hardware logic units to operate on data corresponding to a different K-mer graph. Accordingly, in addition to increased speed benefits achieved using hardware logic instead of execution of software instructions to generate K-mer graphs, the present disclosure achieves further accelerated operation by increasing throughput by generating segments of different K-mer graphs at the same time using different hardware logic units managed by the control machine.

<FIG> is an example of a system <NUM> for hardware-accelerated generation of a K-mer graph. In some implementations, the system <NUM> can include a nucleic acid sequencer <NUM>, a reference sequence database <NUM>, a hardware-accelerated graph generation unit <NUM>, a plurality of hardware logic units <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, a control machine <NUM>, a graph hash table cache <NUM>, a DRAM <NUM>, and a variant calling unit <NUM>. In some implementations, the hardware-accelerated graph generation unit <NUM> can be implemented using a programmable logic circuit such as a field programmable gate array (FPGA). In other implementations, the hardware-accelerated graph generation unit <NUM> can be implemented using an Application Specification Integrated Circuit (ASIC). In either scenario, the functionality described with respect to the hardware-accelerated graph generation unit <NUM>, and each of the components implemented thereon, is implemented using hardware logic circuits arranged to realize the functionality described herein without executing software instructions to realize the functionality.

The term "unit" is used in this specification to describe a software module, a hardware module, or a combination of both, that is used to perform a specified function. A determination of whether a particular "unit" described herein is hardware, software, or a combination of both, can be made based on the context of its use. For example, an "input unit" <NUM>, a "graph node unit" <NUM>, a "graph edge unit" <NUM>, or the like, resident in a hardware-accelerated graph generation unit <NUM> that is implemented using an FPGA or ASIC is a hardware unit whose functionality is realized by hardwired digital logic gates or hardwired digital logic blocks that have been arranged to realize the functionality described herein with respect to the particular "unit. " By way of another example, a "variant calling unit" <NUM> that is not implemented using a hardware-accelerated graph generation unit <NUM> in <FIG> is a software module whose functionality is realized by one or more computers executing software instructions defining the functionality of the "variant calling unit" <NUM>. By way of another example, a computer or processing unit can be a hardware device that realizes functionality by processing software instructions, and thus functionality of the computer or processing unit is a combination of hardware and software.

Though examples of one or more components of <FIG> are provided herein as hardware implementations such as the "control machine" <NUM> because the "control machine" is depicted in <FIG> as being implemented in the hardware-accelerated graph generation unit <NUM>, the present disclosure is not limited to such examples. Instead, other implementations can be employed where the "control machine" <NUM> is implemented in software as a software module or a combination of hardware and software with a computer or processing unit executing software instructions to realize the functionality of the "control machine" <NUM> described here. Likewise, there can be implementations of the present disclosure where certain components described as software with respect to <FIG> such as the "variant calling unit" <NUM> are implemented as a hardware implementation.

The nucleic acid sequencer <NUM> is a device that is configured to perform primary analysis. Primary analysis can include receiving, by the nucleic acid sequencer <NUM>, a biological sample <NUM> such as a blood sample, tissue sample, sputum, or nucleic acid and generating, by the nucleic acid sequencer <NUM>, output data such as one or more reads <NUM> that each represent an order of nucleotides of a nucleic acid sequence of the received biological sample. In some implementations, sequencing, by the nucleic acid sequencer <NUM>, can be performed in multiple read cycles, with a first read cycle generating one or more first reads that include a string of base calls representing an order of nucleotides from a first end of a nucleic acid sequence fragment and a second read cycle generating one or more respective second reads that include a string of base calls representing an order of nucleotides from the other ends of one of the nucleic acid sequence fragments. In some implementations, the reads can be generated using clonal amplification. In the example of <FIG>, the one or more reads <NUM> can include a pileup of reads for a particular reference genome location, with the reference genome location being comprised of multiple, sequential reference genome locations.

Thus, each read is data that represents a portion of a nucleic acid genome for an organism such as an animal, insect, plant, or the like. Assuming short nucleic acid sequence fragments of approximately <NUM> base calls, a first read may represent <NUM> ordered nucleotides for the first end of the nucleic acid sequence fragment and a second read may represent <NUM> ordered nucleotides of the other end of the nucleic acid sequence fragment. These numbers, however, are merely examples and any nucleic acid sequencer <NUM> can be configured to generate reads that can be operated on by a hardware-accelerated graph generation unit as described herein using any sequencing methods. Such reads can be of different lengths than those mentioned here. For example, in some implementations, the present disclosure can be used to generate hardware-accelerated K-mer graphs for reads generated by nucleic acid sequence fragments having up to <NUM> nucleotides, or more, with each read having, for example, <NUM> base calls, <NUM> base calls, <NUM> base calls, <NUM> base calls, <NUM> base calls, <NUM> base calls, or more from the end of each fragment. Each base call can correspond to a nucleotide. The present disclosure can also be used to generate hardware-accelerated K-mer graphs for long reads. Accordingly, the hardware-accelerated graph generation unit <NUM> can be used to generate K-mer graphs for any reads generated in any way by any type of nucleic acid sequencer.

In some implementations, the biological sample <NUM> can include a DNA sample and the nucleic acid sequencer <NUM> can include a DNA sequencer. In such implementations, the order of sequenced nucleotides in a read generated by the nucleic acid sequencer can include one or more of guanine (G), cytosine (C), adenine (A), and thymine (T) in any combination. In some implementations, the nucleic acid sequencer <NUM> can be used to sequence RNA samples. In some implementations, this can occur using RNA-seq protocols. By way of example, an RNA sample can be preprocessed using reverse-transcription to form complementary DNA (cDNA) using a reverse transcriptase enzyme. In other implementations, the nucleic acid sequencer <NUM> can include an RNA sequencer, and the biological sample can include an RNA sample. Accordingly, though the example of <FIG> describes a nucleic acid sequencer that produces reads comprised of Gs, Cs, As, and Ts that is generated by a DNA sequencer based on a DNA sample, the present disclosure is not so limited. Instead, other implementations can process reads comprised of Cs, Gs, As, and Us that are generated by an RNA sequencer based on an RNA sample. In some implementations, the DNA reads or RNA reads generated by the nucleic acid sequencer can include a base call N, with N being indicative of an unknown base call being generated by the nucleic acid sequencer.

In some implementations, the nucleic acid sequencer <NUM> can include a next generation sequencer (NGS) that is configured to generate sequence reads such as reads <NUM> for a given sample in a manner that achieves ultra-high throughput, scalability, and speed through the use of massively parallel sequencing technology. The NGS enables rapid sequencing of whole genomes, the ability to zoom into deeply sequenced target regions, utilize RNA sequencing (RNA-Seq) to discover novel RNA variants and splice sites, or quantify mRNAs for gene expression analysis, analysis of epigenetic factors such as genome-wide DNA methylation and DNA-protein interactions, sequencing of cancer samples to study rare somatic variants and tumor subclones, and studying of microbial diversity in humans or in the environment.

The nucleic acid sequencer <NUM> can obtain a reference genome <NUM> from the reference genome database <NUM>. In some implementations, only a portion of the reference genome <NUM> is obtained. The portion of the reference genome <NUM> that is obtained can correspond to the reference locations of the reference genome <NUM> that the pileup of reads <NUM> are mapped and aligned thereto. The reference genome database <NUM> can include data storage that organizes storage for a plurality of different reference genomes. In some implementations, the particular reference genome <NUM> selected from the reference genome database can be based on the type of DNA sample <NUM>. In some implementations, the type of reference genome selected <NUM> selected form the reference genome database <NUM> can be selected based on input from a user of the nucleic acid sequencer <NUM>. In such implementations, the user can, for example, select a reference genome <NUM> identifier that can be used, by the nucleic acid sequencer <NUM>, to select a particular reference genome <NUM> from the reference genome database <NUM>. The reference genome <NUM> can include, for example, a nucleic acid sequence assembled as a representative example of a set of genes for a particular species.

The combination of the pileup of reads <NUM> generated by the nucleic acid sequencer <NUM> and the obtained reference genome <NUM> can be provided as inputs to the hardware-accelerated graph generation unit <NUM>. These inputs can be processed by one or more of the hardware logic units <NUM> to <NUM> of the hardware-accelerated graph generation unit <NUM> to generate an instance of a K-mer graph. For example, each hardware logic unit of the hardware logic units <NUM> to <NUM> can be configured to perform their respective operations for each read of the pileup of reads <NUM> included as an input to the hardware-accelerated graph generation unit <NUM>.

The system <NUM> of <FIG> is described herein as including a nucleic acid sequencer. In some implementations, such as that described with reference to <FIG>, the system can include a sequencer <NUM> and the hardware-accelerated graph generation unit <NUM>, and other components of system <NUM>, can be integrated within the nucleic acid sequencer <NUM>. However, the present disclosure is not limited to being integrated within the nucleic acid sequencer <NUM>. Instead, in some implementations, the hardware-accelerated graph generation unit <NUM> can be implemented in a programmable logic device or ASIC integrated or housed within a computer that is remote from the nucleic acid sequencer <NUM> and communicably coupled to the nucleic acid sequencer <NUM> such as by using one or more wired or wireless networks. Similarly, the database <NUM>, variant calling unit <NUM>, or both, may be implemented outside the nucleic acid sequencer. Likewise, there is no requirement that the system <NUM> include a nucleic acid sequencer <NUM> at all. Instead, in some implementations, the hardware-accelerated graph generation unit <NUM>, and other components of <FIG>, can be implemented in a computer system that does not include a nucleic acid sequencer <NUM>. In such implementations, the hardware-accelerated graph generation unit can obtain the pileup of reads <NUM>, the reference sequence <NUM>, or both, via a network, from a storage location(s) of one or more memory devices, or like. Accordingly, the system <NUM> depicts an example of the present disclosure but does not limit the present disclosure to any one particular configuration of system components.

The one or more hardware logic units of the hardware-accelerated graph generation unit <NUM> can include an input unit <NUM>, a graph node unit <NUM>, a graph edge unit <NUM>, a back propagation unit <NUM>, a cycle unit <NUM>, a pruning unit <NUM>, the graph output unit <NUM>, and an erase unit <NUM>. In some implementations, generation of a K-mer graph by the hardware-accelerated graph generation unit <NUM> can include the control machine <NUM> activating and configuring each of the hardware logic units <NUM> to <NUM> to execute their respective hardware logic operations on a set of data stored in the cache <NUM> or the DRAM <NUM>. In other implementations, the control machine <NUM> may only activate and configure a subset of the hardware logic units <NUM> to <NUM> to execute their respective hardware logic operation on a set of raw graph data stored in the cache <NUM> or the DRAM <NUM>.

By way of example, in some implementations, the hardware-accelerated graph generation unit <NUM> can be used to generate a specialized form of a De Bruijn graph. This specialized form of a De Bruijn graph can be optimized so that non-unique K-mers are represented using multiple respective nodes in a graph each with a single edge rather than being represented by a single node with multiple edges. This can be achieved, in part, by using a graph unit <NUM> to identify non-unique K-mers and flag the non-unique K-mers for further processing. A non-unique K-mer may be defined as a K-mer sequence which occurs at least twice in any single read, or at least twice in the reference sequence. A unique K-mer do not occur more than once in the same read, but may still occur in multiple reads.

However, in other implementations, De Bruijn graphs can be generated without distinguishing between unique or non-unique K-mers. Thus, in some implementations a graph node unit <NUM> that can identify non-unique K-mers need not be implemented. In yet another example, the back propagation unit <NUM> need not be used to generate all K-mer graphs. Instead, the back propagation unit <NUM> may be limited to implementations where it can improve performance. By way of example, the back propagation unit <NUM> can be used to improve the quality of edge weights when later transformation of a generated K-mer graph into a sequence graph is anticipated.

The K-mer graph generation example described with respect to the example of <FIG> shows each hardware logic unit <NUM> to <NUM> that can be activated and configured by the control machine <NUM>. In this description, each hardware logic unit <NUM> to <NUM> is generally described as activated by the control machine <NUM>, configured by the control machine <NUM> using, for example, graph description data stored by the control machine <NUM>, obtaining raw graph data, performing one or more specific processing operations on the obtained raw graph data or other data, and then updating the raw graph data, the graph description data, or both, the present disclosure is not so limited. However, the present disclosure is not limited to such implementations. Instead, in some implementations, each hardware logic units <NUM> to <NUM> can be configured to execute multiple instances of its respective functionality. For example, graph node unit <NUM> can be configured to accept up to <NUM> distinct sets of raw graph data and simultaneously perform its operations thereon, the cycle hardware logic unit <NUM> can be configured to accept up to <NUM> distinct sets of raw graph data and simultaneously perform its operations thereon, and PRU can be configured to accept up to <NUM> distinct sets of raw graph data and simultaneously perform its operations thereon. The number of distinct sets or raw graph data that each correspond to different K-mer graphs can be received and processed by a particular hardware logic unit <NUM> to <NUM> is only limited by available hardware resources for a system <NUM>. For example, assuming sufficient levels of DRAM and FPGA logic units are available for use, the number of distinct sets of raw graph data that can be received and simultaneously processed by a hardware logic unit <NUM> to <NUM> can be greater than <NUM>. Likewise, one or more hardware logic units <NUM> to <NUM> can be configured to receive and simultaneously process lower numbers of sets of raw graph data if such resources are not readily available or if a particular hardware logic unit is not expected to be heavily used.

In yet other implementations, there is no requirement for there to be only one instance of each hardware logic unit <NUM> to <NUM> that are each capable of simultaneously processing distinct sets of raw graph data that each correspond to different K-mer graphs. Instead, in some implementations, multiple instances of each hardware-accelerated graph generation unit <NUM> can be configured to include multiple instances of one or more of the hardware logic units <NUM> to <NUM>. In such instances, the control machine <NUM> can be configured to monitor the status and availability of each hardware logic unit <NUM> to <NUM>, and then activate and configure each hardware logic unit in a manner that load balances processing operations across each respective hardware logic unit. For example, in some implementations, a hardware-accelerated graph generation unit <NUM> can be configured to have <NUM> instances of a graph node unit <NUM> that are each capable of receiving up to <NUM> distinct sets of raw graph data and simultaneously perform its operations on them, <NUM> instances of a graph edge unit <NUM> that are each capable of receiving up to <NUM> distinct sets of raw graph data and simultaneously performing its operations on them, <NUM> back propagation units <NUM> that are each capable of receiving up to <NUM> distinct sets of raw graph data and simultaneously performing its operations on them, and <NUM> cycle units <NUM> that are each capable of receiving up to <NUM> distinct sets of raw graph data and simultaneously perform its operations on them. Activation / deactivation of each hardware logic unit, configuration of each hardware logic unit, inputs to each hardware logic unit, outputs from each hardware logic unit, and updating of graph description data by each hardware logic unit is managed and directed by the control machine <NUM>.

The input unit <NUM> can receive input data that includes the generated pileup of reads <NUM> and the selected reference genome <NUM>, which can be referred to herein as being raw graph data. The selected reference genome <NUM> can include a portion of a reference genome. Raw graph data can include, for example, data that is processed by one or more hardware logic units <NUM> to <NUM> during generation of an instance of a K-mer graph. While raw graph data includes, for example, the generated reads <NUM> and the selected reference genome <NUM>, raw graph data can also include, for example, K-mer nodes generated by the graph node unit <NUM>, edges generated by the graph edge unit <NUM>, and the like. The input unit <NUM> can format the generated reads <NUM> and the obtained reference genome <NUM> for storage in the DRAM <NUM>. Formatting the generated reads can include, for example, encoding the reads for storage in the DRAM <NUM>. In some implementations, encoding the read can include encoding each base call corresponding to a nucleotide of the read into <NUM>-bit values. For example, an A can be encoded as <NUM>, a C can be encoded as <NUM>, a G can be encoded as <NUM>, a T can be encoded as <NUM>, and an N can be encoded as <NUM>, where N is an unknown base call. In some implementations, the encoded data can also include data that represents a MAPQ score, a read number, a sequence length, SAM flags, the base calls or nucleotides of the read, one or more quality indicators for the read other than the MAPQ score, or any combination thereof. The encoded read data can range from a <NUM>-bit value to a <NUM>-bit value, or more, that describes the read. The input unit <NUM> can write the generate reads to the DRAM <NUM>.

The control machine <NUM> can detect receipt of the raw input data, activate the input unit <NUM>, and initialize graph description data that corresponds to an instance of a K-mer graph that is to be generated based on the raw input data. Activating the input unit <NUM> can include the control machine <NUM> sending one or more control messages to the input unit <NUM> that instruct the input unit <NUM> to perform operations defined by the input unit's <NUM> hardware logic circuity on the raw data provided as an input to the input unit <NUM>. In some implementations, activating a hardware logic unit such as input unit <NUM> can also include the control machine providing, to the hardware logic unit, graph description data that can be used to configure the hardware logic unit for performance of its operations. Configuring the hardware logic unit can include, for example, providing pointers to cache storage locations storing K-mers, K-mer nodes, providing information describing K-mer length, or the like that the hardware logic unit needs to operate on.

Initializing the graph description data can include, for example, the control machine <NUM> generating a K-mer graph identifier for the raw input data, generation of a graph state information data structure, or a combination thereof. The K-mer graph identifier includes a data string of one or more characters, one or more numbers, or a combination thereof, that can be used to identify an instance of a K-mer graph throughout the K-mer graph generation process from the time that the raw graph data is received by the input unit <NUM> to at least the time that the erase unit <NUM> is used to remove data related to the K-mer graph identifier from the cache <NUM>, DRAM <NUM>, or both, following complete generation of the K-mer graph for a particular set of raw graph data. In some implementations, the K-mer graph identifier can include a number such as a <NUM>-bit number having a value between <NUM>-<NUM>. In some implementations, the K-mer graph identifier can even be used to refer to the K-mer graph after the erase unit is used to remove the aforementioned data from the cache <NUM>, DRAM <NUM>, or both. The graph state information data structure is a data structure having one or more fields that store data describing the current state of an instance of a K-mer graph that is to be generated for a particular set of raw input data. The state information can include, for example, data indicating a last hardware logic unit that operated on raw graph data for a particular instance of a K-mer graph, data indicating whether the last hardware logic unit aborted the operation, data indicating a K-mer length, data indicating a K-mer node list, data indicating a list of pointers that can be used to identify the K-mer nodes in a cache, a length of a K-mer node list, data indicating a list of non-unique K-mers, data indicating the locations of raw input data in the cache or DRAM, data indicating a base address in DRAM for nodes of the instance of a K-mer graph, or any subset or combination thereof.

The input unit <NUM> can format the input reads <NUM> and the reference genome <NUM> and write the input reads <NUM> and the reference genome to the DRAM <NUM>. The control machine <NUM> can detect when the input unit <NUM> has completed formatting and writing of the input reads <NUM> and the reference genome <NUM> to the DRAM <NUM>. Upon detection, by the control machine <NUM>, of the completion of the formatting and writing of the input reads <NUM> and the reference genome <NUM> to the DRAM, the control machine <NUM> can update the graph state information to indicate that the input unit <NUM> has completed its operations on first raw graph data for a first instance of a K-mer graph.

Once the first raw graph data has been input, formatted, and stored in the DRAM <NUM>, the control machine <NUM> can determine a next hardware logic unit that is to be activated and configured next. For example, the control machine <NUM> can activate and configure a graph node unit <NUM> to generate K-mer nodes based on the portion of the reference genome <NUM> and pileup of reads formatted and stored in the DRAM <NUM>.

The control machine <NUM> can activate and configure the graph node unit <NUM> to continue generation of the first instance of a K-mer graph by processing the formatted reads <NUM> and the reference genome <NUM> stored in the DRAM. This can include, for example, sending a control signal to the graph node unit <NUM>, providing graph description data to the graph node unit <NUM>, or a combination thereof. The graph description data can be used to configure the graph node unit <NUM> for operation. For example, providing the graph description data to the graph node unit <NUM> and from the control machine <NUM> can configure the graph node unit <NUM> to identify K-mers of particular size that is defined by the graph description data. Other fields of the graph description data described herein can be used to configure a hardware logic unit such as the graph node unit <NUM> in a similar manner.

In addition, in a substantially parallel manner, the control machine <NUM> can detect that the input unit <NUM> received second raw graph data as an input. The control machine <NUM> can then activate the input unit <NUM>, instruct the unit <NUM> to format the reads and reference genome of the second raw graph data, and generate second graph description data for a second instance of a K-mer graph that is to be generated based on the second raw graph data. Thus, the control machine <NUM> can achieve high levels of throughput by simultaneously managing performance of different hardware logic units <NUM>, <NUM> that are performing K-mer graph generation processes on different sets of raw graph data at different processing stages. The control machine <NUM> is configured to manage this parallel functionality across each of the hardware logic unit <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> such at any particular point in time there may be as many as eight hardware logic units operating on eight different sets of raw graph data, with the hardware-accelerated graph generation unit <NUM> working towards generating eight different K-mer graphs simultaneously. The control machine <NUM>, using the graph description data, manages this process throughout by activating and configuring each respect hardware logic unit to achieve abstractly high-level pipelined functionality out of the non-pipelined hardware logic units <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, which do not have a direct and physical input/output connection between each respective hardware logic unit. Though an example of eight simultaneous K-mer graph generations being performed at the same time is illustrated, the present disclosure can be configured to achieve many more simultaneous K-mer graph generations such as by implementing multiple hardware-accelerated graph generation units <NUM> at a time, multiple instances of multiple hardware logic units on one or more hardware-accelerated graph generation units <NUM>, or a combination thereof.

The graph node unit <NUM> can analyze each read of a pileup of reads <NUM> to identify each of the K-mers of the read. This can include, for example, sliding a K-mer access window along each position of each read to identify each particular K-mer of the respective read. The graph node unit <NUM> can store data representing a node of a K-mer graph, for each identified K-mer of each read, in the cache <NUM>. Likewise, the graph node unit <NUM> can also generate and store, in DRAM, a list of node pointers in a data structure of node pointers, with each node pointer pointing to a K-mer node cache location. The graph node unit <NUM> can also generate and store information indicating the location and length of the list of node pointers for each K-mer graph in graph description data maintained by the control machine. These pointers can be used as graph state information, by the control machine <NUM>, to configure another hardware logic unit during a subsequent portion of the K-mer graph generation process. The cache <NUM> can employ one or more cache coherency policies such as an LRU cache coherency policy that is configured to evict the oldest objects of the cache <NUM>, with the oldest objects being determined based on the time the object was written to the cache <NUM>.

An example of data generated by the graph node unit <NUM> and stored in the cache <NUM>, the DRAM <NUM>, or both is shown with reference to <FIG> shows a portion of a reference genome <NUM>, a read <NUM>, and a De Bruijn graph <NUM> is provided. The De Bruijn graph <NUM>, which is described in more detail below, includes a node for each K-mer in the portion of the genome <NUM> and the read <NUM> and an edge between each pair of K-mer nodes that links a pair of nodes having k-<NUM> overlapping nucleotides.

With reference to the example of <FIG>, the graph node unit <NUM> can generate, based on receipt of a portion of the reference genome <NUM> and the read <NUM>, data representing the nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> of a first path <NUM> of the DeBruijn graph <NUM> and nodes <NUM>, <NUM>, <NUM>, <NUM> can be generated. First, the graph node unit <NUM> can align the overlapping portions of the reference genome 410a, 410b and the overlapping portions of the read 420a, 420b to identify overlapping regions as shown in <FIG>. The graph node unit <NUM> can identify each of the K-mers of the portion of the genome <NUM> and the read <NUM>. This can be achieved by using an access window of length k, which equals <NUM> in this example, at a first position of the portion of the reference genome <NUM> capturing the K-mer identified by the access window, generating data representing a node of the graph that includes the captured K-mer, storing the data representing the node in cache <NUM>, advancing the access window by one nucleotide, and then iteratively repeating this process. In this example, the graph node unit <NUM> can identify the K-mers ATCG, TCGC, CGCC, GCCT, CCTA, CTAG, TAGA, and AGAA for the portion of the reference genome <NUM> and generate a respective node <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, with one of these nodes corresponding to a respective K-mer. Each node is created to have a length of k, which is <NUM> in this example, and have an overlapping number of k-<NUM>-mers with the next adjacent node. The graph node unit <NUM> can store the generated nodes in the cache <NUM>, the DRAM <NUM>, or both. In some implementations, cache can include a hash table cache. In such implementations, the nodes can be stored as keys of a hash table. The graph node unit <NUM> can store data describing pointers to K-mer node locations in the graph description data maintained by the control machine <NUM>.

The graph node unit <NUM> can perform the same operations for the read <NUM>. With respect to the read <NUM>, the graph node unit <NUM> can identify the K-mers ATCG, TCGC, CGCG, GCGT, CGTA, GTAG, TAGA, and AGAA. This can be similarly achieved by using an access window of length k, which is equal to <NUM> in this example, at a first positon of the portion of the read <NUM> capturing the K-mer identified by the access window, and then advancing the access window and repeating the process. The graph node unit <NUM> can begin by identifying each K-mer for portion of the genome <NUM>. In some implementations, the graph node unit <NUM> can generate a corresponding node for each of the K-mers. In other implementations, the graph node unit <NUM> may only generate <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> corresponding to the identified K-mers that differ from the K-mer nodes of the portion of the reference genome <NUM>. In each scenario, each node is created to have a length of k, which is <NUM> in this example, and have an overlapping number of k-<NUM>-mers with the next adjacent node. This can continue until a node for each K-mer of the portion of the reference genome <NUM> is created and stored in the cache <NUM> or DRAM <NUM>.

In some implementations, the graph node unit <NUM> can also be configured to identify non-unique K-mers. In such implementations, the graph node unit <NUM> can for each particular read of a first pileup of reads, determine whether an identified K-mer is a unique K-mer or a non-unique K-mer. If the graph node unit <NUM> determines that a particular K-mer is a unique K-mer, then the graph node unit <NUM> can advance the access window by a single nucleotide to evaluate the next K-mer. Alternatively, if the graph node unit <NUM> determines that a particular K-mer is a non-unique K-mer, then the graph node unit <NUM> can store data indicating that the particular K-mer is a non-unique K-mer. For example, the graph node unit <NUM> can store a data flag in the graph description data maintained by the control machine for the particular instance of a K-mer graph indicating that the K-mer is a non-unique K-mer. However, such data can be stored by any other component of the hardware-accelerated graph generation unit <NUM>, stored in any other memory unit of the hardware-accelerated graph generation unit <NUM>, or a combination thereof. Then, subsequent hardware logic units can perform operations that address the non-unique K-mer in order to reduce or eliminate cycles in the instance of the K-mer graph.

At this point in the process, the graph node unit <NUM> stores the data representing a node of a K-mer graph for each K-mer in the cache <NUM>, DRAM <NUM>, or both. That is, the hardware-accelerated graph generation unit <NUM> has not yet generated the graph edges 431a, 432a 433a, 434a, 435a, 436a, 437a, 432b, 441a, 442a, 443a, 444a, graph edge weights, or the like. These features of this instance of a K-mer graph can be generated by one or more other hardware logic units of the hardware-accelerated graph generation unit <NUM>.

The control machine <NUM> can monitor the operation of the graph node unit <NUM>. Once the graph node unit <NUM> generates data representing a K-mer node for each K-mer of each read of the first raw graph data for this first instance of a K-mer graph, the control machine can update the graph description data to indicate that hardware-accelerated graph generation unit <NUM> has completed the graph node unit <NUM>'s operations on the first raw graph data. In addition, the control machine <NUM> can also store graph description data that includes, for example, a flag identifying each of the non-unique K-mers, storage locations for the K-mer graph nodes, and data indicating that the graph node unit <NUM> has completed its operations.

Once the K-mer graph nodes have been generated and stored in the cache <NUM>, the control machine <NUM> can determine a next hardware logic unit that is to be activated and configured next. For example, the control machine <NUM> can activate and configure a graph edge unit <NUM> to generate, weight, or both, graph edges between pairs of nodes.

The graph edge unit <NUM> can generate graph edges between pairs of K-mer nodes generated by the graph node unit <NUM>. The control machine <NUM> can activate the graph edge unit <NUM> once it is determined that the graph node unit <NUM> for the first K-mer graph instance is complete and that the graph edge unit <NUM> is available. In some implementations, the control machine <NUM> can provide, or otherwise make accessible to, the graph edge unit <NUM> locations storing K-mer graph nodes generated by the graph node unit <NUM> for a particular instance of a K-mer graph. For example, the control machine <NUM> can access K-mer graph description data generated and stored by the graph node unit <NUM> during generation of K-mer nodes for an instance of a K-mer graph. The accessed K-mer graph description data can indicate, or otherwise describe, a list of K-mers.

Once graph edge unit <NUM> has obtained the location of the K-mer graph nodes for the first instance of the K-mer graph, the graph edge unit can begin generating one or more graph edges between data representing the K-mer nodes. In some implementations, the graph edge unit <NUM> can access the data representing the graph node for each of the K-mers of the particular read from the hash table cache. The graph edge unit <NUM> can generate, for storage in the hash table cache, data representing a graph edge between the graph nodes for the K-mers. For example, the data representing the graph edge can be stored in the hash table cache as part of a graph node record for the edge's source node. In some implementations, the graph edge unit <NUM> can assign an edge weight to each edge of the K-mer graph. For example, the graph edge unit <NUM> can add a +<NUM>, or other weight, for each occurrence of the graph edge linking the respective K-mer pair.

By way of example, the graph edge unit <NUM> can identify nodes, using graph description data obtained from the control machine <NUM>, that are adjacent nodes. The nodes can be determined to be adjacent nodes based on a variety of factors including a determination that the nodes share k-<NUM> overlapping nucleotides and that the nodes are observed in two consecutive positions of the sliding K-mer access window. For example, graph edge unit <NUM> can slide a K-mer access window along each position of each read of the raw graph data. In some implementations, the graph edge unit <NUM> can create an edge or increment an edge weight upon a determination that two successive K-mers, which overlap by all but one base, are observed in a read. The graph node <NUM> creates an edge or increments an edge weight in such a scenario because this scenario implies an edge between the graph nodes corresponding to those two successive K-mers.

In some implementations, data representing the graph nodes can be stored as hash keys of a hash table. In such implementations, the graph edge unit <NUM> can generate an edge from a first node (or hash key) to a second node (or hash key) by accessing a hash location that the first node (or hash key) is mapped to and generating a pointer for stored in the hash location that points to the second node (or hash key). Subsequent edges can be generated in the same manner, which creates a path <NUM> or <NUM> through a graph that can be walked using one or more graph walking algorithms.

With reference to the example of <FIG>, the graph edge unit <NUM> can generate data representing the one or more edges between pairs of nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> of a first path <NUM>, pairs of nodes <NUM>, <NUM>, <NUM>, <NUM> of a second path <NUM>, or one or more pairs of nodes in the first path <NUM> and the second path <NUM>. An example of these edges are shown in <FIG> as edges 431a, 432a, 433a, 434a, 435a, 436a, 437a, 432b, 441a, 442a, 443a, 444a.

In this example, the sequence of nucleotides <NUM> are referred to as a read. However, in some implementations, low quality base removal can occur such that the sequence of nucleotides <NUM> is a contig, or portion of a read. In such implementations, the graph edges linking a pair nodes will only create a path of one or more links within a particular contig and not from K-mer node of a first contig to a K-mer node of a second config. A contig can include a sequence of nucleotides occurring after a low quality base is removed.

The hardware-accelerated graph generation unit <NUM> can include a back-propagation unit <NUM>. However, the control machine <NUM> may only activate and configure the back-propagation unit <NUM> in certain implementations. For example, the control machine <NUM> may activate the back-propagation unit <NUM> when it is determined, by the control machine <NUM>, that the K-mer graph being generated by a current set of raw graph data will be later transformed into a sequence graph. When activated, the back-propagation module <NUM> can receive graph description data from the control machine <NUM>. In such implementation, adjustments to graph edge weights can make the weights more reliable when inherited by the sequence graph.

The graph edge unit <NUM> can build edges between K-mer nodes of contigs by identifying corresponding K-mer nodes in the cash <NUM>, generating an edge that links the K-mer nodes, and then incrementing a weight for the edge +<NUM> for each occurrence. In some implementations, after the K-mer nodes of a contig have been added to a K-mer graph and weighted using the graph edge unit <NUM>, the back-propagation unit <NUM> can be used to back propagate a +<NUM> edge weight increments k-<NUM> stages through a linear chain of graph edges "left" of the contig's starting node in the K-mer graph. In this context, "left" of the contig's starting node in the K-mer graph is a direction of a K-mer graph that is opposed the directed edge of the K-mer graph. To illustrate this concept, "left" of a node <NUM> in the De Bruijn graph <NUM> would be nodes <NUM>, <NUM>, and <NUM>.

For example, in some implementations, the back propagation module <NUM> can access, in the hash table cache, the data representing the K-mer graph including its K-mer nodes, corresponding graph edges, or the like and then adjust edge weights for K-<NUM> nodes that occur before a start of a new config. The back-propagation unit <NUM> can locate the appropriate K-mer nodes and edges to adjust based on graph description data received from the control machine <NUM> that includes pointers to cache locations storing this information. The graph description data can be updated with any changes that occur during back-propagation.

In some implementations, it can be advantageous to perform the aforementioned back-propagation because an N-base contig may only increment a series of (N-K) edge weights. However, if this K-mer graph is later transformed into a sequence graph with (N-<NUM>) internal edges corresponding to this contig, then the first (K-<NUM>) edge weights will not inherit properly incremented edge weights. The aforementioned back-propagation addresses most instances of this problem. Thus, back-propagation can be used to address this problem in order to increase the reliability of the inherited edge weights when the K-mer graph is transformed into a sequence graph.

The hardware-accelerated graph generation unit <NUM> can include a cycle unit <NUM>. In some implementations, the cycle unit <NUM> can be activated and configured by the control machine <NUM> to detect cycles in an instance of a K-mer graph. For example, the cycle unit <NUM> can evaluate the K-mer nodes and K-mer edges of raw graph data of an instance of K-mer graph that has been generated by one or more of the input unit <NUM>, graph node unit <NUM>, graph edge unit <NUM>, and back-propagation unit <NUM>. The cycle unit <NUM> is configured to receive graph description data from the control machine <NUM>. The cycle unit <NUM> can iteratively flag head nodes for deletion. A head node can include a node that does not include any in-edges. Where an in-edge is an edge that points to from a first node to the first node itself. After each head node is flagged for deletion, the cycle unit <NUM> can determine whether any nodes pointed to by outedges have become head nodes as a results of a deleted node. If such nodes are determined, they are flagged for deletion. An out-edge is a graph edge that points from a first node to another node. The cycle unit <NUM> can continue performance of this process until there are no head nodes left.

Upon a determination that there are no head nodes left, the cycle unit <NUM> can determine whether the graph is empty, with an empty graph meaning that all nodes of the graph are flagged for deletion. If the headless graph is empty, then there was no cycle. Alternatively, if the headless graph is not empty, then the graph must contain a cycle. Cycles are resistant to this kind of deletion, because no node in a cycle becomes a head node by deleting nodes outside the cycle.

Upon making either one of these determinations, the cycle unit <NUM> can provide an indication to the control machine <NUM> as to whether or not a cycle was detected. Then, based on the provided indication from the cycle unit <NUM>, the control machine <NUM> can determine which hardware logic unit should next be activated and configured. For example, if a cycle was detected and generation of the instance of the K-mer graph should be aborted, then the control machine <NUM> can activate and configure the erase unit <NUM>. In such instances, the erase unit can delete raw graph data from the cache <NUM> and the DRAM <NUM> corresponding to the instance of the aborted K-mer graph. If, alternatively, generation of the instance of the K-mer graph is to continue, then control machine <NUM> can activate and configure another hardware logic unit to perform subsequent operations on the raw graph data to generate the instance of the K-mer graph. For example, if K-mer graph generation is to continue, the control machine <NUM> can either activate and configure the pruning unit <NUM> or the graph output unit <NUM>.

Though the cycle unit <NUM> can be used by the hardware-accelerated graph generation unit <NUM> to detect cycles in an instance of a K-mer graph that is being generated, the cycle unit <NUM> can be selectively activated and configured like the back-propagation unit <NUM>. This is because it is foreseeable some kinds of K-mer graphs can include cycles. However, for certain types of K-mer graphs, it may be beneficial to not have graphs with cycles. Accordingly, the hardware-accelerated graph generation unit <NUM> can be configured, for example, for the control machine <NUM> to receive input indicating whether or not the cycle unit <NUM> should be performed for a particular instance of a graph.

The hardware-accelerated graph generation unit <NUM> can include a pruning unit <NUM>. Like the back-propagation unit <NUM> and the cycle unit <NUM>, the pruning unit <NUM> can be selectively activated and configured by the control machine <NUM>. If activated and configured, the pruning unit <NUM> can evaluate a weight of each graph edge in raw graph data for an instance of a K-mer graph that has been generated to this point by the hardware-accelerated graph generation unit <NUM>. In some implementations, if the pruning unit <NUM> determines that the weight value of a graph edge fails to satisfy a predetermined threshold, then the pruning unit <NUM> can delete graph edge and any K-mer node that occurs after the identified graph edges. Alternatively, if the pruning unit <NUM> determines that the weight value of a graph edge satisfies the predetermined threshold, then the pruning unit <NUM> will leave the graph edge intact.

In other implementations, the pruning unit <NUM> can identify linear chains, where linear chains are maximal paths through the graph wherein all internal nodes between the start node and end node have exactly one in-edge and one out-edge. In such implementations, the pruning unit <NUM> can determine if every internal edge of the linear chain fails to satisfy the pruning threshold. If such a scenario occurs, the pruning unit <NUM> can delete the entire linear chain, including all internal edges and all internal nodes, except the chain's start node and/or end node, which the pruning unit <NUM> can retain if they have any non-interior edges.

The hardware-accelerated graph generation unit <NUM> can include a graph output unit <NUM>. The graph output unit <NUM> can be used, by the hardware-accelerated graph generation unit <NUM> to generate a final version <NUM> of the instance of the K-mer graph, as the instance of the K-mer graph is described by the graph description data and cached data. For example, the graph output unit <NUM> can obtain data representing the K-mer graph from the hash table cache <NUM> using the graph description data that includes, for example, pointers to locations in the hash table cache storing the K-mer graph data. Then, the graph output unit <NUM> can provide the data obtained from the hash table cache <NUM> describing the final version of the K-mer graph <NUM> to a variant calling unit <NUM>. The variant calling unit <NUM> can perform variant calling analysis on the final version of the K-mer graph <NUM> to produce a set of variants <NUM>. A set of variants <NUM> can include one or more candidate variants. A variant is an alteration in genomic data of an organism. A candidate variant is a determination by a variant calling unit that is inferred by the variant calling unit based on processing a K-mer graph <NUM>. In some implementations, the candidate variant may have a threshold level of error in the variant determination.

The variant calling unit <NUM> can identify candidate variants by processing the K-mer graph <NUM>. In some implementations, for example, the variant calling unit <NUM> can identify a candidate variant when a base call or nucleotide one or more reads in the pileup of reads and a nucleotide of a reference genome at a particular location of the reference genome are different. Data describing the set of variants <NUM> can be generated or determined in any number of ways. For example, in some implementations, variant calling operations can be performed as described in more detail in, for example, <CIT>, <CIT>, and <CIT>. Data describing the set of variants <NUM> can be provided for output in a number of different ways. For example, data describing the set of variants <NUM> can be displayed on a display of the nucleic acid sequencer <NUM>, displayed on a display of a different computer, audibly output via one or more speakers of a computing device, output via a printer, or any combination thereof.

The erase unit <NUM> can be used to perform memory reclamation tasks upon completion and output of an instance of a K-mer graph by the hardware-accelerated graph generation unit <NUM>. For example, the erase unit can delete all raw graph data related to the particular instance of a K-mer graph that is completed and output by the hardware-accelerated graph generation unit <NUM>. Alternatively, or in addition, the erase unit <NUM> can delete all data related to the particular instance of the graphical unit <NUM> that is stored by the control machine, delete all data related to the particular instance of the graphical unit <NUM> that is stored in DRAM <NUM>, or the like. Accordingly, the erase unit <NUM> can selectively delete data representing graph nodes and data representing graph edges of the K-mer graph from the hash table cache. Such deletion is selective because only a portion of the contents of the cache, control machine, or DRAM needs to be removed. Moreover, when the graph is stored as a hash table, the hash table may often be sparsely populated, and it is faster for the erase unit <NUM> to selectively erase only the occupied hash table entries than to clear the entire hash table, thus resulting in performance improvements.

However, in some implementations, non-hash-table data associated with a graph does not need to be erased item by item. In such implementations, the erase unit <NUM> can set list lengths to zero in the graph description data or allocated memory space can just be freed for reuse without erasing the content.

<FIG> is a flowchart of an example of a process <NUM> for hardware-accelerated generation of a K-mer graph. In general, the process <NUM> can include obtaining a first set of nucleic acid sequences, wherein the first set of nucleic acid sequences includes (i) a plurality of reads corresponding to an active region of a reference sequence and (ii) a portion of the reference sequence (<NUM>), 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, 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 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 (<NUM>), 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 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 (<NUM>), and providing the K-mer graph to a variant calling module, wherein the variant calling unit processes the K-mer graph to determine one or more candidate variants between one or more of the plurality of reads and the reference sequence.

<FIG> is a flowchart of another example of a process <NUM> for hardware-accelerated generation of a K-mer graph. In general, the process <NUM> can include obtaining a first set of nucleic acid sequences, wherein the first set of nucleic acid sequences include (i) a plurality of reads corresponding to an active region of a reference sequence and (ii) a portion of the reference sequence (<NUM>), for each particular nucleic acid sequence of the first set of nucleic acid sequences: generating, for storage in a hash table cache and by a first hardware logic unit, data representing a graph node for each K-mer of the particular nucleic acid sequence (<NUM>), detecting, by a control machine, that the first hardware logic unit has completed generation of a graph node for each K-mer of the particular nucleic acid sequence (<NUM>), configuring, by the control machine, a second hardware logic unit to perform graph edge generation for the generated graph nodes (<NUM>), and for one or more pairs of the generated graph nodes: generating, by the second hardware logic units and for storage in the graph hash table, data representing graph edges between one or more pairs of the generated graph nodes generated by the first hardware logic unit, wherein the data representing the graph node for each K-mer stored in the hash table cache and the data representing graph edges stored in the hash table cache represents a K-mer graph of the first set of nucleic acid sequences (<NUM>).

<FIG> is an example of a K-mer graph <NUM>. In this example, the K-mer graph is <NUM> is generated based on at least a portion of a reference genome <NUM> and a read <NUM>. In this example, the K-mer graph <NUM> is a De Bruijn graph.

The K-mer graph <NUM> is generated using a plurality of nodes and one or more edges between pairs of nodes. Each node represents a K-mer of length k, wherein in this example k=<NUM>. Each edge provides an indication that there is an overlap of k-<NUM> nucleotides of the K-mers linked by the edge. In the K-mer graph <NUM>, the path <NUM> includes a plurality of nodes and edges that represent each K-mer of the portion of the reference sequence <NUM>. Then, the path <NUM> includes a plurality of nodes and edges representing portions of a read <NUM> that differ from the portion of the reference genome <NUM>.

<FIG> is a block diagram of an example of system <NUM> components that can be used for hardware-accelerated K-mer graph.

Computing device <NUM> is intended to represent various forms of digital computers, such as laptops, desktops, workstations, personal digital assistants, servers, blade servers, mainframes, and other appropriate computers. Computing device <NUM> is intended to represent various forms of mobile devices, such as personal digital assistants, cellular telephones, smartphones, and other similar computing devices. Additionally, computing device <NUM> or <NUM> can include Universal Serial Bus (USB) flash drives. The USB flash drives can store operating systems and other applications. The USB flash drives can include input/output components, such as a wireless transmitter or USB connector that can be inserted into a USB port of another computing device. The components shown here, their connections and relationships, and their functions, are meant to be examples only, and are not meant to limit implementations of the inventions described and/or claimed in this document.

Each of the components <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM>, are interconnected using various busses, and can be mounted on a common motherboard or in other manners as appropriate. In other implementations, multiple processors and/or multiple buses can be used, as appropriate, along with multiple memories and types of memory. Also, multiple computing devices <NUM> can be connected, with each device providing portions of the necessary operations, e.g., as a server bank, a group of blade servers, or a multi-processor system.

The memory <NUM> can also be another form of computer-readable medium, such as a magnetic or optical disk.

In one implementation, the storage device <NUM> can be or contain a computer-readable medium, such as a floppy disk device, a hard disk device, an optical disk device, or a tape device, a flash memory or other similar solid-state memory device, or an array of devices, including devices in a storage area network or other configurations. The computer program product can also contain instructions that, when executed, perform one or more methods, such as those described above.

The high-speed controller <NUM> manages bandwidth-intensive operations for the computing device <NUM>, while the low speed controller <NUM> manages lower bandwidth intensive operations. Such allocation of functions is only an example. In one implementation, the high-speed controller <NUM> is coupled to memory <NUM>, display <NUM>, e.g., through a graphics processor or accelerator, and to high-speed expansion ports <NUM>, which can accept various expansion cards (not shown). The low-speed expansion port, which can include various communication ports, e.g., USB, Bluetooth, Ethernet, wireless Ethernet can be coupled to one or more input/output devices, such as a keyboard, a pointing device, microphone/speaker pair, a scanner, or a networking device such as a switch or router, e.g., through a network adapter. The computing device <NUM> can be implemented in a number of different forms, as shown in the figure. For example, it can be implemented as a standard server <NUM>, or multiple times in a group of such servers. It can also be implemented as part of a rack server system <NUM>. In addition, it can be implemented in a personal computer such as a laptop computer <NUM>. Alternatively, components from computing device <NUM> can be combined with other components in a mobile device (not shown), such as device <NUM>. Each of such devices can contain one or more of computing device <NUM>, <NUM>, and an entire system can be made up of multiple computing devices <NUM>, <NUM> communicating with each other.

The computing device <NUM> can be implemented in a number of different forms, as shown in the figure. For example, it can be implemented as a standard server <NUM>, or multiple times in a group of such servers. It can also be implemented as part of a rack server system <NUM>. In addition, it can be implemented in a personal computer such as a laptop computer <NUM>. Alternatively, components from computing device <NUM> can be combined with other components in a mobile device (not shown), such as device <NUM>. Each of such devices can contain one or more of computing device <NUM>, <NUM>, and an entire system can be made up of multiple computing devices <NUM>, <NUM> communicating with each other.

Computing device <NUM> includes a processor <NUM>, memory <NUM>, and an input/output device such as a display <NUM>, a communication interface <NUM>, and a transceiver <NUM>, among other components. The device <NUM> can also be provided with a storage device, such as a micro-drive or other device, to provide additional storage. Each of the components <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM>, are interconnected using various buses, and several of the components can be mounted on a common motherboard or in other manners as appropriate.

The processor can be implemented as a chipset of chips that include separate and multiple analog and digital processors. Additionally, the processor can be implemented using any of a number of architectures. For example, the processor <NUM> can be a CISC (Complex Instruction Set Computers) processor, a RISC (Reduced Instruction Set Computer) processor, or a MISC (Minimal Instruction Set Computer) processor. The processor can provide, for example, for coordination of the other components of the device <NUM>, such as control of user interfaces, applications run by device <NUM>, and wireless communication by device <NUM>.

Processor <NUM> can communicate with a user through control interface <NUM> and display interface <NUM> coupled to a display <NUM>. The display <NUM> can be, for example, a TFT (Thin-Film-Transistor Liquid Crystal Display) display or an OLED (Organic Light Emitting Diode) display, or other appropriate display technology. The display interface <NUM> can comprise appropriate circuitry for driving the display <NUM> to present graphical and other information to a user. The control interface <NUM> can receive commands from a user and convert them for submission to the processor <NUM>. In addition, an external interface <NUM> can be provided in communication with processor <NUM>, so as to enable near area communication of device <NUM> with other devices. External interface <NUM> can provide, for example, for wired communication in some implementations, or for wireless communication in other implementations, and multiple interfaces can also be used.

Expansion memory <NUM> can also be provided and connected to device <NUM> through expansion interface <NUM>, which can include, for example, a SIMM (Single In Line Memory Module) card interface. Such expansion memory <NUM> can provide extra storage space for device <NUM>, or can also store applications or other information for device <NUM>. Specifically, expansion memory <NUM> can include instructions to carry out or supplement the processes described above, and can also include secure information. Thus, for example, expansion memory <NUM> can be provided as a security module for device <NUM>, and can be programmed with instructions that permit secure use of device <NUM>. In addition, secure applications can be provided via the SIMM cards, along with additional information, such as placing identifying information on the SIMM card in a non-hackable manner.

The memory can include, for example, flash memory and/or NVRAM memory, as discussed below. The information carrier is a computer- or machine-readable medium, such as the memory <NUM>, expansion memory <NUM>, or memory on processor <NUM> that can be received, for example, over transceiver <NUM> or external interface <NUM>.

Device <NUM> can communicate wirelessly through communication interface <NUM>, which can include digital signal processing circuitry where necessary. Communication interface <NUM> can provide for communications under various modes or protocols, such as GSM voice calls, SMS, EMS, or MMS messaging, CDMA, TDMA, PDC, WCDMA, CDMA2000, or GPRS, among others. Such communication can occur, for example, through radio-frequency transceiver <NUM>. In addition, short-range communication can occur, such as using a Bluetooth, Wi-Fi, or other such transceiver (not shown). In addition, GPS (Global Positioning System) receiver module <NUM> can provide additional navigation- and location-related wireless data to device <NUM>, which can be used as appropriate by applications running on device <NUM>.

Device <NUM> can also communicate audibly using audio codec <NUM>, which can receive spoken information from a user and convert it to usable digital information. Audio codec <NUM> can likewise generate audible sound for a user, such as through a speaker, e.g., in a handset of device <NUM>. Such sound can include sound from voice telephone calls, can include recorded sound, e.g., voice messages, music files, etc. and can also include sound generated by applications operating on device <NUM>.

The computing device <NUM> can be implemented in a number of different forms, as shown in the figure. For example, it can be implemented as a cellular telephone <NUM>. It can also be implemented as part of a smartphone <NUM>, personal digital assistant, or other similar mobile device.

Various implementations of the systems and methods described here can be realized in digital electronic circuitry, integrated circuitry, specially designed ASICs (application specific integrated circuits), computer hardware, firmware, software, and/or combinations of such implementations. These various implementations can include implementation in one or more computer programs that are executable and/or interpretable on a programmable system including at least one programmable processor, which can be special or general purpose, coupled to receive data and instructions from, and to transmit data and instructions to, a storage system, at least one input device, and at least one output device.

As used herein, the terms "machine-readable medium" "computer-readable medium" refers to any computer program product, apparatus and/or device, e.g., magnetic discs, optical disks, memory, Programmable Logic Devices (PLDs), used to provide machine instructions and/or data to a programmable processor, including a machine-readable medium that receives machine instructions as a machine-readable signal.

To provide for interaction with a user, the systems and techniques described here can be implemented on a computer having a display device, e.g., a CRT (cathode ray tube) or LCD (liquid crystal display) monitor for displaying information to the user and a keyboard and a pointing device, e.g., a mouse or a trackball by which the user can provide input to the computer.

The systems and techniques described here can be implemented in a computing system that includes a back end component, e.g., as a data server, or that includes a middleware component, e.g., an application server, or that includes a front end component, e.g., a client computer having a graphical user interface or a Web browser through which a user can interact with an implementation of the systems and techniques described here, or any combination of such back end, middleware, or front end components.

Claim 1:
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 (<NUM>) corresponding to a region of a reference sequence (<NUM>) and (ii) a portion of the reference sequence;
generating, using a plurality of non-pipelined hardware logic units (<NUM>-<NUM>) of a programmable logic device a K-mer graph (<NUM>) 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 (<NUM>-<NUM>, <NUM>-<NUM>) of the K-mer graph represents a K-mer, each edge (431a-437a, 432b, 441a-444a) 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 (<NUM>), 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 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.