Population clustering through density-based merging

• US 20110029519A1
• Filed: 04/26/2004
• Published: 02/03/2011
• Est. Priority Date: 04/25/2003
• Status: Active Grant

• Current Assignee: Board of Trustees of the Leland Stanford Junior University (Stanford University), Leland Stanford Junior University (Stanford University)
• Original Assignee: Leland Stanford Junior University (Stanford University)
• Inventors: Moore, Wayne, Belitskaya-Levy, IIana, Pan, Jinhui, Walther, Guenther, Parks, David, Herzenberg, Leonore A.
• Granted Patent: US 8,473,215 B2
• Time in Patent Office: Days
• US Class Current: 707/737
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/24564 Applying rules; Deductive queries
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 16/55 Clustering; Classification
• CPC Class Codes: G06F 16/90 Details of database functions independent of the retrieved data types
• CPC Class Codes: G16B 25/10 Gene or protein expression profiling; Expression-ratio estimation or normalisation
• CPC Class Codes: G16B 5/00 ICT specially adapted for modelling or simulations in systems biology, e.g. gene-regulatory networks, protein interaction networks or metabolic networks

Abstract

A method and/or system for analyzing data using population clustering through density based merging.

Claims

1. A method of identifying clusters of data items, wherein a data item is associated with one or more values, said method using an information processing system with a logic processor comprising:

defining using a logic processor a plurality of lattice points in a data space able to contain some of said data items of interest, said lattice points being data reduction points, said lattice points spaced according to a lattice rule, wherein said lattice points provide a rules-based ordering of values and storing said plurality of lattice points in a memory of said information processing system;

calculating weights for said lattice points using one or more of said data items according to a weighting rule by retrieving said plurality of said lattice points from said memory and performing said calculating using said processor;

determining a density at said lattice points relating a weight at a lattice point to weights at nearby lattice points using a density function on said processor;

creating, for each of a plurality of said lattice points, a directional association with at least one other of said lattice points using an association rule using said processor and storing said direction association in said memory;

sequentially following directional associations between lattice points starting at a starting lattice point of said lattice points, thereby defining a lattice point path until a terminal lattice point for said lattice point path is reached wherein a terminal lattice point is identified when there is no surrounding point from which a lattice point can be connected using said processor;

comparing a density of said terminal lattice point of said lattice point path to a density threshold thereby determining if said terminal lattice point indicates a new cluster, an existing cluster, or a default background cluster using said processor; and

labeling lattice points in said lattice point path as background points, points belonging to said existing cluster;

or points belonging to said new cluster based on said determining using said processor and storing said labeling in said memory;

repeating said sequentially following, said comparing, and said labeling until a majority of lattice points are labeled using said processor;

distance merging lattice point paths by comparing pairs of terminal lattice points and if a distance between two terminal lattice points is below a distance threshold, merging points in each lattice point path connected to said terminal lattice points into a single cluster, wherein said distance threshold is expressed as a distance between lattice points;

density merging lattice point paths by comparing pairs of terminal lattice points and if there is a path of consecutive lattice points along which values of said lattice point'"'"'s densities do not fall more than a density threshold below the minimum values of the two roots;

repeating said density merging on initial lattice point paths and merged lattice point paths until no pairs of lattice points meet a density merging criteria;

assigning lattice points to a cluster or to background noise;

assigning data points to clusters by relating data points to lattice points and then using the cluster assignment of the lattice point; and

displaying one or more identified clusters to a user using a graphical user interface display at said system.

3. The method of claim 1 further comprising:

capturing said data items as groups of values from a fluorescence-activated cell sorter (FACS), each associated with an individual cell;

wherein one or more of said values representing fluorescence levels detected on a particular fluorescence channel; and

wherein said clusters each provide an indication to identify separable cell subpopulations analyze by said cell sorter.

5. The method of claim 1 further wherein:

said one or more values are effectively continuous.

6. The method of claim 1 further wherein:

said lattice points or said lattice rule determine a lattice;

said data space has N dimensions, N corresponding to a number of values of interest associated with at least one of said data items;

said lattice defines a plurality of N-dimensional bins; and

said lattice rule examines smallest and largest values of interest in each dimension and determines spacing in that dimension according to a spacing rule.

7. The method of claim 6 further wherein:

said spacing rule comprises;

in each dimension, taking the difference between smallest and largest values of interest and defining a regular spacing of M units, where M is selected to provide the desired granularity.

8. The method of claim 1 further wherein:

said lattice rule comprises;

assigning a data item to a nearest lattice point.

9. The method of claim 1 wherein said association rule comprises:

determining density values of a plurality of lattice points by;

using a kernel density estimate of weights on a lattice point to determine a density estimate at each of said plurality of lattice points; and

at a lattice point, determining for a plurality of surrounding lattice points whether to make a directional association.

10. The method of claim 1 wherein said association rule comprises:

determining a density surface for said lattice points;

making a directional association if a slope of said density surface from a first lattice point to a second lattice point is significantly positive.

11. The method of claim 1 wherein said identifying one or more clusters uses directional associations of a plurality of lattice points and a density estimated at each lattice point.

12. The method of claim 1 wherein said identifying one or more clusters uses directional associations of a plurality of lattice points and a density estimated at each lattice point and does not use weights assigned to lattice points or original data values.

13. The method of claim 1 wherein said creating further comprises

creating clusterings of lattice points based on the associations of the lattice points.

14. The method of claim 1 wherein said creating further comprises:

creating clusterings of lattice points based on the associations and weightings of the lattice points.

15. The method of claim 1 wherein said creating further comprises:

breaking spurious path terminations prior to said clustering.

2. (canceled)

4. (canceled)

16. An apparatus for creating groupings from data comprising:

logic processing means for assigning each piece of data from said set of data to a point on a lattice;

logic processing means for assigning weights to each lattice point based on the data near said lattice point;

logic processing means for determining for each of said lattice points if each of said lattice points should be associated with one of its surrounding lattice points and if so creating a pointer from the individual lattice point to the surrounding lattice point it is associated with; and

logic processing means for creating clusterings of the lattice points.

17-20. -20. (canceled)

21. A method of identifying clusters of data items using an information processing system with a logic processor comprising:

defining using a logic processor a plurality of data reduction lattice points in a data space able to contain some of said data items, said lattice points spaced according to a lattice rule providing a rules-based ordering of values;

storing said plurality of lattice points in a memory of said information processing system;

calculating weights for said lattice points using one or more of said data items according to a weighting rule by retrieving said plurality of said lattice points from said memory and performing said calculating using said processor;

wherein said weighting rule determines a weight at a lattice point by a weighted summing of nearby data values up to all data values;

determining a density at said lattice points relating a weight at a lattice point to weights at nearby lattice points using a density function on said processor;

creating, for each of a plurality of said lattice points, a directional association with at least one other of said lattice points using an association rule using said processor and storing said direction association in said memory;

sequentially following directional associations between lattice points starting at a starting lattice point of said lattice points, thereby defining a lattice point path until a terminal lattice point for said lattice point path is reached wherein a terminal lattice point is identified when there is no surrounding point from which a lattice point can be connected using said processor;

comparing a density of said terminal lattice point of said lattice point path to a density threshold thereby determining if said terminal lattice point indicates a new cluster, an existing cluster, or a default background cluster using said processor; and

labeling lattice points in said lattice point path as background points, points belonging to said existing cluster;

or points belonging to said new cluster based on said determining using said processor and storing said labeling in said memory;

repeating said sequentially following, said comparing, and said labeling until a majority of lattice points are labeled using said processor;

distance merging lattice point paths by comparing pairs of terminal lattice points and if a distance between two terminal lattice points is below a distance threshold, merging points in each lattice point path connected to said terminal lattice points into a single cluster, wherein said distance threshold is expressed as a distance between lattice points;

density merging lattice point paths by comparing pairs of terminal lattice points and if there is a path of consecutive lattice points along which values of said lattice point'"'"'s densities do not fall more than a density threshold below the minimum values of the two roots;

repeating said density merging on initial lattice point paths and merged lattice point paths until no pairs of lattice points meet a density merging criteria;

assigning lattice points to a cluster or to background noise;

assigning data points to clusters by relating data points to lattice points and then using the cluster assignment of the lattice point; and

displaying one or more identified clusters to a user using a graphical user interface display at said system.