Customized integrated circuit for serial comparison of nucleotide sequences

Patent metadata

Field	Value
Publication number	US-10566076-B2
Application number	US-201615349725-A
Country	US
Kind code	B2
Filing date	Nov 11, 2016
Priority date	Nov 11, 2016
Publication date	Feb 18, 2020
Grant date	Feb 18, 2020

Abstract

Comparisons between two nucleotide sequences can be performed by customized integrated circuitry that can implement a Smith Waterman analysis in series, as opposed to the parallel implementations known in the art. Series performance enables such customized integrated circuitry to take advantage of optimizations, including enveloping thresholds that demarcate between cells of a two-dimensional matrix for which nucleotide comparisons are to be performed, and cells of the two-dimensional matrix for which no such comparison need be performed, and, instead, a value of zero can simply be entered. Additionally, such customized integrated circuitry facilitates the combination of multiple control units, each directing the comparison of a unique pair of nucleotides, with a single calculation engine that can generate values for individual cells of the two-dimensional matrices by which such pairs of nucleotides are compared.

First claim

We claim:

1. A customized integrated circuit comprising:
a calculation engine comprising circuitry that, during operation of the customized integrated circuit, enables the customized integrated circuit to
generate a score of a single cell of a two-dimensional matrix based on: generated scores of vertically prior cells in a column, of the two-dimensional matrix, comprising the single cell, generated scores of horizontally prior cells in a row, of the two-dimensional matrix, comprising the single cell, a nucleotide, from one nucleotide sequence, that corresponds with the selected cell, and a nucleotide from, another nucleotide sequence, that corresponds with the selected cell; and
a first control unit comprising circuitry that, during operation of the customized integrated circuit, enables the customized integrated circuit to:
select a cell of a first two-dimensional matrix, a first dimension of which is delineated by nucleotides of a first nucleotide sequence and a second dimension of which is delineated by nucleotides of a second nucleotide sequence, wherein a nucleotide from the first nucleotide sequence corresponds with the selected cell and a nucleotide from the second nucleotide sequence also corresponds with the selected cell;
determine whether to instruct the calculation engine to generate a score of the selected cell based on a pre-determined threshold that demarcates between a first set of cells of the two-dimensional matrix for which scores are to be generated and a second set of cells of the two-dimensional matrix for which scores are not to be generated;
instruct the calculation engine to generate the score of the selected cell, based on the selected cell being within the first set of cells, the instructing comprising providing, to the calculation engine, previously generated scores of prior cells, the nucleotide from the first nucleotide sequence that corresponds with the selected cell and the nucleotide from the second nucleotide sequence that corresponds with the selected cell;
enter a zero score for the selected cell based on the selected cell being within the second set of cells; and
repeat the selecting, the determining, the instructing and the entering for subsequent cells, in series, of the two-dimensional matrix.

2. The customized integrated circuit of claim 1 , wherein the pre-determined threshold extends diagonally through the two-dimensional matrix such that the second set of cells for which scores are not to be generated comprises a contiguous grouping of cells in a corner of the two-dimensional matrix.

3. The customized integrated circuit of claim 1 , wherein the pre-determined threshold is one of a first pre-determined threshold or a second pre-determined threshold, the first pre-determined threshold and the second pre-determined threshold extending diagonally through the two-dimensional matrix parallel to one another such that the first set of cells for which scores are to be generated comprises a contiguous grouping of cells extending diagonally from one corner of the two-dimensional matrix to an opposite corner of the two-dimensional matrix.

4. The customized integrated circuit of claim 1 , wherein the pre-determined threshold extends diagonally through a first portion of the two-dimensional matrix at a first angle and then extends diagonally through a second portion of the two-dimensional matrix at a second angle differing from the first angle.

5. The customized integrated circuit of claim 1 , further comprising a second control unit comprising circuitry that, during operation of the customized integrated circuit, enables the customized integrated circuit to:
select a cell of a second, different two-dimensional matrix, a first dimension of which is delineated by nucleotides of a third nucleotide sequence and a second dimension of which is delineated by nucleotides of a fourth nucleotide sequence, wherein a nucleotide from the third nucleotide sequence corresponds with the selected cell and a nucleotide from the fourth nucleotide sequence also corresponds with the selected cell;
determine whether to instruct the calculation engine to generate a score of the selected cell of the second two-dimensional matrix based on a second pre-determined threshold that demarcates between a first set of cells of the second two-dimensional matrix for which scores are to be generated and a second set of cells of the second two-dimensional matrix for which scores are not to be generated;
instruct the calculation engine to generate the score of the selected cell of the second two-dimensional matrix, based on the selected cell of the second two-dimensional matrix being within the first set of cells of the second two-dimensional matrix, the instructing comprising providing, to the calculation engine, previously generated scores of prior cells of the second two-dimensional matrix, the nucleotide from the third nucleotide sequence that corresponds with the selected cell of the second two-dimensional matrix and the nucleotide from the fourth nucleotide sequence that corresponds with the selected cell of the second two-dimensional matrix;
enter a zero score for the selected cell of the second two-dimensional matrix based on the selected cell being within the second set of cells of the second two-dimensional matrix; and
repeat the selecting, the determining, the instructing and the entering for subsequent cells of the second two-dimensional matrix.

6. The customized integrated circuit of claim 5 , wherein the calculation engine generates scores for the first and second control units in an alternating manner including generating the score of the selected cell, as instructed by the first control unit, during a first processing cycle, and then generating the score of the selected cell of the second two-dimensional matrix, as instructed by the second control unit, during a second processing cycle immediately following the first processing cycle.

7. The customized integrated circuit of claim 1 , further comprising an input store unit, wherein the calculation engine obtains nucleotides of the first and second nucleotide sequences from the input store unit.

8. The customized integrated circuit of claim 7 , wherein the calculation engine generates the score of the single cell based on generated scores of prior cells as incremented by a gap-scoring factor, and wherein further the calculation engine obtains the gap-scoring factor from the input store unit.

9. The customized integrated circuit of claim 7 , wherein the first control unit obtains the pre-determined threshold from the input store unit.

10. The customized integrated circuit of claim 1 , further comprising a score aggregation unit comprising circuitry that, during operation of the customized integrated circuit, enables the customized integrated circuit to:
receive the score of the single cell as generated by the calculation engine; and
retain the score of the single cell if it is larger in value than a previously retained score of a prior cell.

11. The customized integrated circuit of claim 1 , wherein the first control unit retains a quantity of immediately previously generated scores of immediately prior cells that is one greater than a quantity of nucleotides in one of the first or second nucleotide sequences, and wherein further the previously generated scores of prior cells that are provided, by the first control unit, to the calculation engine, are from the immediately previously generated scores of the immediately prior cells that are retained by the first control unit.

12. The customized integrated circuit of claim 1 , further comprising a dispatching unit comprising circuitry that, during operation of the customiz

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Lo Daniel
• Chung Eric
• Ovtcharov Kalin
• Pandya Ravindra
• Heckerman David

Classifications

• G06F17/10

  Complex mathematical operations {(function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544)} · CPC title

• G06F7/02

  Comparing digital values (G06F7/06, {G06F7/22,} G06F7/38 take precedence) · CPC title

• G16B30/00 Primary

  ICT specially adapted for sequence analysis involving nucleotides or amino acids · CPC title

• G16B30/10 Primary

  Sequence alignment; Homology search · CPC title