Next generation sequencing sorting in time and space complexity using location integers
US11183270B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Dec 7, 2017 |
| Grant date | Nov 23, 2021 |
| Priority date | — |
| Expiry date | Feb 8, 2040 |
Classification
- Technology area (CPC C)Chemistry; Metallurgy
- CPC primaryC12Q2535/122
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A system and machine-implemented method for sorting Next-Generation Sequencing (NGS) reads in O(n) time and space complexity that makes use low sparsity and nearly uniform distribution of the input array. The genome position field in the input array is used to determine the target position of the output array. Duplicate target positions due to n-fold coverage are handled by assigning either overflow buckets to each position or anterior assigning multiple target slots in the output array for each genome position depending on the distribution of reads over the genome and the resulting probability of hitting an already occupied slot. Once every tuple in the input array has been written to the output array, the output array in read through ascending order and each tuple is appended to the end of a final result array.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.