Method for identifying clusters of fluorescence-activated cell sorting data points
A method and/or system for analyzing data using population clustering through density based merging.
1. A method executed by a computer processor for identifying clusters of fluorescence-activated cell sorting (FACS) data points associated with one or more light intensity values measured for a particular cell, a group of cells, a sample of cells or a combination thereof comprising:
(A) constructing a normalized lattice L in d dimensions, wherein said lattice has an equal number of intervals in all directions and consists of M intervals in each direction, where M is a positive integer that defines Md lattice points, by
(i) setting size of a d dimensional unit area or volume to be Δ j in accordance with the formula Δ j =(max i x ij −min i x ij )/(M−1), j=1, . . . , d,
(ii) defining jth coordinate of lattice points y (m1, . . . ,md) to be y mj =min i x ij +(m j −1)Δ j , mj=1, . . . , M, and
(iii) defining lattice L as L={y (m1, . . . ,md) :(m 1 , . . . , m d )∈{1, . . . , M} d ;
(B) calculating weights for said lattice points using one or more of said data points according to a weighting rule in accordance with formula:
w
m
=
∑
i
=
1
n
∏
j
=
1
d
max
(
0
,
1
-
x
i
,
j
-
y
mj
/
Δ
j
)
,
where w m is weight, y m is each lattice point and x i is one or more observed data points;
(C) determining a density at said lattice points relating a weight at a lattice point to weights at nearby lattice points using a density function, wherein determining the density includes computing an estimate of a density surface {circumflex over (f)}(y m ) wherein the Gaussian kernel is denoted by φ(b)=1/√{square root over (2)}πexp(−b 2 /2) and the estimated density y m is computed by formula:
f
^
(
y
m
)
=
1
/
n
∑
l
1
=
-
Z
1
Z
1
…
∑
l
d
=
-
Z
d
Z
d
ω
m
-
1
∏
j
=
1
d
ϕ
(
l
j
Δ
j
/
h
j
)
/
h
j
,
where l=(l 1 , . . . , l d ), Z j =min(└4h j /Δ j ┘/, M−1), and h j =SD({x i,j , i=1, . . . , n})n −1/(d+4) , where SD denotes standard deviation;
(D) creating, for a lattice point, a directional association with at least one other lattice point using an association rule by establishing and removing pointers between neighboring lattice points by successively executing a series of evaluations for all lattice points y m , where m is an element of S, in turn:
considering all neighboring lattice points p 1 , . . . , p nm which are defined as the set of all lattice points contained in a s-dimensional rectangular volume, where p is an element of {p 1 , . . . , p nm } such that {circumflex over (f)}(p)=max k=1, . . . ,nm {circumflex over (f)}(p k ), splitting ties in an arbitrary manner; then a pointer is established from y m to p provided:
{circumflex over ( f )}( p )>{circumflex over ( f )}( y m ); and
∂
∂
e
f
^
(
y
m
)
>
λ
m
,
where e=(p−y m )/∥p−y m ∥, ∥•∥ denotes Euclidean norm, and
∂
∂
e
f
^
(
y
m
)
=
e
∂
f
^
(
y
m
)
,
which indicates a gradient of the density estimate,
∂
∂
y
m
a
f
^
(
y
m
)
=
1
n
∑
l
1
=
-
Z
1
Z
1
…
∑
l
d
=
-
Z
d
Z
d
ω
m
-
1
-
l
a
Δ
a
h
a
2
∏
j
=
1
d
ϕ
(
l
j
Δ
j
/
h
j
)
/
h
j
λ
m
=
q
(
0.95
1
/
κ
)
Σ
^
m
2
κ
=
#
S
Σ
m
∈
s
w
m
n
(
2
π
)
d
/
2
∏
j
=
1
d
h
j
Σ
m
∈
s
w
m
f
^
(
y
m
)
Σ
^
m
2
=
1
n
-
1
(
∑
a
,
b
=
1
d
e
a
e
b
[
A
-
∂
∂
y
m
a
f
^
(
y
m
)
∂
∂
y
m
b
f
^
(
y
m
)
]
)
A
=
1
/
n
∑
l
1
=
-
Z
1
Z
1
…
∑
l
d
=
-
Z
d
Z
d
ω
m
-
1
l
a
l
b
Δ
a
Δ
b
h
a
2
h
b
2
∏
φ
=
1
δ
ϕ
2
(
l
j
Δ
j
/
h
j
)
/
h
j
2
,
A being an estimate of
∂
∂
y
m
a
f
(
y
m
)
∂
∂
y
m
b
f
(
y
m
)
and q(x) denotes the 100*xth percentile of the standard normal distribution;
(E) following said directional associations between lattice points to determine terminal states for one or more pointer paths, wherein a terminal state is defined as a lattice point that does not have a surrounding point that meets said association rule in (D);
(F) assigning each data point to a lattice point according to an assignment rule comprising the steps of
(i) assigning each observed data point x i to a lattice point y m that is closest to x i Euclidean norm, and
(ii) assigning x i and lattice point y m that is closest to x i in Euclidean norm to same cluster;
(G) determining a cluster for said FACS data points based on said terminal states of said pointer paths;
(H) selecting a particular cell, a group of cells, a sample of cells or a combination thereof based on said cluster for said FACS data points; and
(I) providing clustering results based on said selecting step (H) in a hierarchical display via a user interface to identify said particular cell, said group of cells, said sample of cells or said combination thereof as belonging to a particular cluster.
2. The method of claim 1 wherein said data items are groups of values each associated with an individual cell and said cluster is a cell subpopulation.
3. The method of claim 1 wherein:
said one or more values are effectively continuous.
4. 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.
5. The method of claim 1 , wherein the formula:
f
^
(
y
m
)
=
1
/
n
∑
l
1
=
-
Z
1
Z
1
…
∑
l
d
=
-
Z
d
Z
d
ω
m
-
1
∏
j
=
1
d
ϕ
(
l
j
Δ
j
/
h
j
)
/
h
j
,
where
l=(l 1 , . . . , l d ), Z j =min(└4h j /Δ j ┘/, M−1), and h j =SD({x i,j , i=1, . . . , n})n −1/(d+4) ) is computed by the Fast Fourier Transform (FFT).
6. The method of claim 1 , wherein the step of determining a density includes calculating an estimate of the standard deviation of the density estimate in accordance with the formula:
σ
^
m
2
=
1
n
(
n
-
1
)
∑
l
1
=
-
Z
1
Z
1
…
∑
l
d
=
-
Z
d
Z
d
w
m
-
1
∏
j
=
1
d
ϕ
2
(
l
j
Δ
j
/
h
j
)
/
h
j
2
-
1
n
-
1
f
^
(
y
m
)
2
and defining an index set S={m∈{1, . . . M} d :{circumflex over (f)}(y m )>4.3*√{square root over ({circumflex over (σ)} m 2 )}}.
7. The method of claim 1 , wherein from each lattice point y m , where m is not an element of S, a pointer is established that points to background noise.
8. The method of claim 7 , wherein the step of following directional associations further includes evaluating all lattice points y m , where m is an element of S, in turn: if a pointer originates at y m , then it will point to a different lattice point, which itself may have a pointer originating from it; following a succession of pointers until a lattice point y z is reached that either (a) does not have any pointer originating from it or (b) has a pointer originating from it that points to a cluster or to background noise; in the event (a) removing all pointers visited in the succession and establishing new pointers originating from each lattice point to the background noise, provided {circumflex over (f)}(y z )<q(0.95 1/κ )√{square root over ({circumflex over (σ)} z 2 )}, otherwise only the pointer originating from y, is removed and a new pointer is established that originates from y z is removed and a new pointer is establishes that originates from y z and points to a new cluster, in the event (b) no pointers are removed or established.
9. The method of claim 8 , wherein the step of following directional associations further includes:
Let letting {y m(1) , . . . , y m(k) } be the set of all lattice points which have a pointer originating from them to a dummy cluster, enumerated such that
{circumflex over ( f )}( y m(1) )≧ . . . ≧{circumflex over ( f )}( y m(k) ) and for i= 1, . . . , k do:
setting A={m(i), and iterate the following loop until no more indices are added to A:
For each index a which is an element of A in turn, adding all the indices p to A that satisfy:
Yp is a neighbor or ya as defined in claim 1 , and
No pointer originates from yp, and
{circumflex over ( f )}( y p )+{circumflex over (σ)} p ≧{circumflex over (f)} ( y m(i) )+{circumflex over (σ)} m(i)
denoting by B the set of indices of lattice points from which a pointer originates to a cluster and that also have some y p , p being an element of as neighbor; if B is not empty, then:
defining q by {circumflex over (f)}(y q )=max r∈B {circumflex over (f)}(y r ), breaking ties arbitrarily;
establishing a pointer from each y p , p an element of A\{m(i)} to y q ;
For each r which is an element of B, if r≠q, removing the pointer from y r to the cluster and establishing a new pointer from y r to y q .
10. The method of claim 9 , wherein the steps recited in claim 9 are repeated until there are no more additions or deletions of pointers to the cluster.
11. The method of claim 10 , wherein from each lattice point that does not have a pointer originating from it, establishing a pointer pointing to the background noise.