Methods and apparatus for sorting data

• US 9,824,068 B2
• Filed: 12/15/2014
• Issued: 11/21/2017
• Est. Priority Date: 12/16/2013
• Status: Active Grant

• Current Assignee: 10X Genomics Incorporated
• Original Assignee: 10X Genomics Incorporated
• Inventors: Wong, Alexander Y.
• Primary Examiner(s): Peng, Huawen A
• Application Number:
  US14/571,120
• Publication Number:
  US 20150220532A1
• Time in Patent Office: 1,072 Days
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G16B 30/00 ICT specially adapted for sequence analysis involving nucleotides or amino acids
• CPC Class Codes: G16B 30/10 Sequence alignment; Homology search

Abstract

A computer implemented system for genomic data sorting, comprising alignment and position mapping. The system maps each read to a position on the reference genome with which the read is associated, followed by sorting these reads by their mapped positions.

Claims

1. A method for data processing, comprising:

(a) obtaining a particular string data value from among a plurality of string data values, wherein each of the plurality of string data values comprises a portion of a genome sequence, and wherein the plurality of string data values is obtained from a genome sequence machine;

(b) mapping with a programmed computer processor the particular string data value to a particular data container among a plurality of data containers, wherein each of the plurality of string data values is addressable by a position in the genome sequence such that the plurality of data containers is ordered with respect to the genome sequence;

(c) appending a data item comprising the particular string data value to the particular data container in a computer memory;

(d) repeating (b)-(c) with the programmed computer processor for all of the plurality of string data values; and

(e) outputting a continuous output sequence generated from (a)-(d), wherein (a)-(d) are performed in the absence of sorting the plurality of string data values.

2. The method of claim 1, wherein the mapping comprises applying a mapping function to the particular string data value to obtain a position value associated with the particular string data value, and selecting the particular data container based upon the position value.

3. The method of claim 1, further comprising:

applying a non-deterministic mapping function to the particular string data value to obtain a plurality of position values for a subset of two or more data containers from among the plurality of data containers, and a plurality of probability values each associated with the particular string value and with the particular data container among the two or more data containers in the subset;

selecting each of the two or more data containers based upon the position values; and

appending a copy of the particular string value, a particular one of the position values, and a particular one of the probability values, to each of the two or more data containers in the subset.

4. The method of claim 1, further comprising generating an output data set by traversing the containers in linear order and successively outputting each of the data items in the data containers.

5. The method of claim 1, further comprising compacting the continuous output sequence by:

creating a compact data container;

addressing the particular data container among the plurality of data containers;

copying each data item that is in the particular data container to the compact data container;

repeating the addressing and copying for all the data containers among the plurality of data containers, to yield a compacted continuous output sequence; and

outputting the compacted continuous output sequence, wherein the compact data container does not contain any data containers that contain zero data items.

6. The method of claim 1, further comprising associating a probability to the particular data container having the particular string data value mapped thereto.

7. The method of claim 1, wherein the mapping is non-injective to the genome sequence.