Reduced memory nucleotide sequence comparison
US10241970B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Nov 14, 2016 |
| Grant date | Mar 26, 2019 |
| Priority date | — |
| Expiry date | Mar 12, 2037 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG16B30/10
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Comparisons between two nucleotide sequences can be performed by customized integrated circuitry that can implement a Smith Waterman analysis in a reduced memory footprint, storing and referencing only individual portions, or subsections, of a two-dimensional matrix that is representative of the comparison between the two nucleotide sequences. As the backtracking proceeds, backtracking metadata corresponding to a cell from a subsection that is not currently retained in memory can be required. Such a subsection can be regenerated from previously generated scores associated with checkpoint cells of the two-dimensional matrix that comprise two edges of the subsection being regenerated. Moreover, to further reduce memory consumption, the backtracking metadata stored for each cell can comprise four binary digits: two indicative of a directional assignment, one indicative of whether the corresponding cell is part of a deletion stretching across multiple contiguous cells, and one analogously indicative of insertions stretching across multiple contiguous cells.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.