Micron Technology Incorporated

Corey B Olson

Gregory Edvenson

Paul T Draghicescu

A scalable FPGA-based solution to the short read mapping problem in DNA sequencing is disclosed which greatly accelerates the task of aligning short length reads to a known reference genome. A representative system comprises one or more memory circuits storing a plurality of short reads and a reference genome sequence; and one or more field programmable gate arrays configured to select a short read; to extract a plurality of seeds from the short read, each seed comprising a genetic subsequence of the short read; for each seed, to determine at least one candidate alignment location (CAL) in the reference genome sequence to form a plurality of CALs; for each CAL, to determine a likelihood of the short read matching the reference genome sequence in the vicinity of the CAL; and to select one or more CALs having the currently greater likelihood of the short read matching the reference genome sequence.

Hardware acceleration of short read mapping for genomic and other types of analyses

Representative embodiments are disclosed for data transfer between field programmable gate arrays (FPGAs). A representative system includes: a PCIe communication network comprising a PCIe switch and a plurality of PCIe communication lines; a host computing system coupled to the PCIe communication network; a nonblocking crossbar switch; a plurality of memory circuits; and a plurality of field programmable gate arrays, each field programmable gate array configurable for a plurality of data transfers to and from the host computing system and any other field programmable gate array of the plurality of field programmable gate arrays, with each data transfer including a designation of a first memory address, a file size, and a stream number. Once base DMA registers have been initialized for a selected application, no further involvement by the host computing system is involved for the duration of the selected application.

System and method for independent, direct and parallel communication among multiple field programmable gate arrays

A system and method are disclosed for inexact search acceleration using reference data. A representative system includes one or more memory circuits storing a plurality of queries and a FM-index of the reference data; and one or more FPGAs configured to select a query; select a substring of the selected query; read a section of the FM-index and calculate a plurality of suffix array intervals for the sub string with a corresponding plurality of prepended characters in a first or next position; read a first or next character in the first or next position of the query and select a suffix array interval for the read first character; determine whether the suffix array interval is valid and whether a beginning of the query has been reached; returning a first search result when the suffix array interval is valid and the beginning of the query has been reached; and returning a second search result that no match of the query with the reference data was found when the suffix array interval is not valid.

Inexact search acceleration

A system and method are disclosed for inexact search acceleration using reference data. A representative system includes one or more memory circuits storing a plurality of queries and a FM-index of the reference data; and one or more FPGAs configured to select a query; select a substring of the selected query; read a section of the FM-index and calculate a plurality of suffix array intervals for the substring with a corresponding plurality of prepended characters in a first or next position; read a first or next character in the first or next position of the query and select a suffix array interval for the read first character; determine whether the suffix array interval is valid and whether a beginning of the query has been reached; returning a first search result when the suffix array interval is valid and the beginning of the query has been reached; and returning a second search result that no match of the query with the reference data was found when the suffix array interval is not valid.

Growing community of inventors

Madison, WI, United States of America

Corey B Olson