The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Nov. 23, 2021
Filed:
Dec. 07, 2017
International Business Machines Corporation, Armonk, NY (US);
Romeo Kienzler, Allschwil, CH;
Jenny Li, Cary, NC (US);
Stefan Mueck, Cologne, DE;
Stefan Ravizza, Wallisellen, CH;
International Business Machines Corporation, Armonk, NY (US);
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.