Interval pattern concepts are a particular case of pattern structures. They can be used to clusterize rows of a numerical formal context (data matrix): two rows are close to each other if their entries at the corresponding positions fall within a given interval. The problem of mining interval pattern concepts has much in common with the known problem related to computational geometry: given a nite set of points in the Euclidean space, position a box of a given size in such a way that it encloses as many points as possible. This problem and its variations have been thoroughly studied in the case of a plane; however, the authors are not aware of the existence of algorithms which in a reasonable time produce an exact solution in the space of an arbitrary dimension. There exists an approximate greedy algorithm for solving this problem. It produces a solution with time which is linear in the number of points and polynomial in dimension. We apply a clustering approach based on that algorithm to the gene expression table from the dataset \The Cancer Cell Line Encyclopedia". The resulting partition well agrees with a priori known biological factors.
In our days researchers frequently need to investigate various biological and medical data represented as numerical contexts (data tables). Rows of tables correspond to objects; columns correspond to attributes. It is often necessary to nd clusters that are composed of objects featuring similar attributes. One of the most convenient tools that can be used for clustering this kind of data is Formal Concept Analysis. ? The research was supported by the Russian Science Foundation (project 16-11-00058 \The development of methods and algorithms for automated analysis of medical tactile information and classi cation of tactile images").
Formal concept analysis (FCA) is a data analysis method based on applied
lattice theory and order theory. Within the framework of this theory a formal
concept is de ned as a pair (extent, intent) obeying the Galois connection (see
the monograph [
One of the variations of FCA is known as the theory of pattern structures, which was elaborated by B. Ganter and S. Kuznetsov in [2]. An important particular case of pattern structures is interval pattern structure with the operation of interval intersection, which allows one to apply cluster analysis to rows of numerical contexts [3]. In this case similarity means that all the di erences between the values of the corresponding attributes fall into given intervals.
It is easily seen that the problem of detecting similar objects can be reformulated in geometrical terms, namely, as the problem of optimal positioning of a d-dimensional box with given edge lengths for the set P of points, i.e. nding a position of the box that maximizes the number of points of the set P enclosed by the box (here d 2 N is the number of attributes in the numerical context considered, P is the set generated by the rows of the numerical context).
In practice, biomedical data often involve thousands of entries, and each entry is described by hundreds of attributes. The existing algorithms that solve the problem of nding an optimal position of a box do not allow one to obtain an exact solution for high-dimensional data within a reasonable time. In [4] the authors introduced a fast approximate greedy algorithm for solving this problem and applied the corresponding clustering approach to the dataset of tactile images registered by the Medical Tactile Endosurgical Complex (MTEC, [5]). The experiment results demonstrated signi cant advantage of the proposed algorithm over the conventional k-means method in clustering quality.
In this paper we apply this clustering algorithm to the dataset \The Cancer Cell Line Encyclopedia" [6]. This dataset includes an expression table for about 20000 genes in 917 cancer cell lines. The cell lines were derived from tissues of 23 di erent organs. The aim of the study is to check if cancers from close organs have close gene expression values.
The rest of the paper is organised as follows. In Section 2 we introduce de nitions from the formal concepts theory. In Section 3 we overview the clustering algorithm from [4]. In Section 4 we describe the procedure and present the results of application of the algorithm to the gene expression data, and in Section 5 we make concluding remarks. 2
In this section we brie y recall the main de nitions of the theory of formal concepts and give a geometrical interpretation of the problem of nding an interval pattern concept of maximum extent size.
De nition 1. A semilattice operation on the partially ordered set (M; ) is a binary operation u : M M that features the following properties for a certain e 2 M and any elements x; y; z 2 M : { x u x = x (idempotency); { x u y = y u x (commutativity); { (x u y) u z = x u (y u z) (associativity); { e u x = e.
De nition 2. Let (P; P ) and (Q; Q) be partially ordered sets. A Galois connection between these sets is a pair of maps ' : P ! Q and : Q ! P (each of them is referred to as a Galois operator) such that the following relations hold for any p1; p2 2 P and q1; q2 2 Q: { p1 { q1 { p1
P p2 ) '(p1) Q q2 ) (q1) P P ('(p1)) and q1
Applying the Galois operator twice, namely, ('(p)) and '( (q)), de nes a closure operator.
De nition 3. A closure operator ( ) on M is a map that assigns a closure X M to each subset X M under the following conditions: { X Y ) X Y (monotony); { X X (extensity); { X = X (idempotency).
De nition 4. A pattern structure is a triple (G; (D; u); ), where G is a set of objects, (D; u) is a meet-semilattice of potential object descriptions, and : G ! D is a function that associates descriptions with objects.
The Galois connection between the subsets of the set of objects and the set of descriptions for the pattern structure (G; (D; u); ) is de ned as follows: A := ug2A (g); d := fg 2 G j d v (g)g; where A where A
G; G: De nition 5. A pattern concept of the pattern structure (G; (D; u); ) is a pair (A; d), where A G is a subset of the set of objects and d 2 D is one of the descriptions in the semilattice, such that A = d and d = A; A is called the pattern extent of the concept and d is the pattern intent.
A particular case of a pattern concept is the interval pattern concept. The set D consists of rows of a numerical context which are treated as tuples of intervals of zero length. An interval pattern concept is a pair (A; d), where A is a subset of the set of objects and d is a tuple of intervals with ends determined by the smallest and the largest values of the corresponding component in the descriptions of all objects in A.
Since interval pattern concepts are determined by objects that have similarly \distributed" attributes, these concepts are convenitent to use in data clustering. The interval width can be either the same for all components (in such case it is denoted by ), or di erent for di erent components (in such case the widths are denoted by 1; 2; : : : ; d).
Let P be a set of n points in Rd (d 2 N), 1; 2; : : : ; d be positive real numbers.
De nition 6. A d-orthotope (also called a box) with center x = (x1; : : : ; xd) 2 Rd and edge lengths 1; 2; : : : ; d is the Cartesian product of the intervals x1 1 ; x1 + 2
It can be easily seen that the problem of identi cation of a maximum interval concept can be reformulated in terms of nding an optimal position of the box with the edge lengths 1; 2; : : : ; d, that is, maximizing the number of points of the set P enclosed by the box. This formulation can be generalized to the problem of nding an optimal position of a ball in an arbitrary metric space, since any box can be treated as a ball in the stretched L1 metric in which the distance (x; y) between the points x = (x1; : : : ; xd) and y = (y1; : : : ; yd) is de ned as (x; y) = 1miaxd ijxi yij: 3
The Greedy Clustering Algorithm Based on Interval Pattern Concepts In this section we brie y overview the greedy clustering algorithm which was introduced in [4]. Given the set P = fpigin=1 Rd, the algorithm splits it into mutually disjoint clusters C1; : : : ; Ck. The splitting procedure is based on optimal box positioning and uses a standard greedy approach. Namely, at each step an optimal position Di of the box for the set P n(C1; : : : ; Ci 1) is determined, and Ci is assigned to be equal to (P n (C1; : : : ; Ci 1)) T Di. In order to avoid producing a big number of small clusters consisting of outliers, the algorithm uses a restriction on the number of points in the resulting clusters | they must include at least cmin objects. With this restriction some points can be considered unclustered.
The clustering procedure uses the approximate greedy iterative algorithm for solving the problem of an optimal box positioning. The parameters of that algorithm are the box edge lengths 1; 2; : : : ; d, the positive real numbers s; smin; < 1 and the function f : N N ! N. The parameters s, smin, and regulate the duration of one iteration, while the function f returns the number of iterations for the given values n and d. Greater number of iterations and greater duration of each iteration provide better approximation.
Now we will brie y describe the greedy algorithm for nding an approximately optimal position of a box. After a short preprocessing procedure the box with the edge lengths 1; 2; : : : ; d is transformed into the d-dimensional unit cube, and the algorithm locates the base unit cube, i.e. the optimal unit cube with integer vertice coordinates. The main idea of the algorithm consists in constructing f (n; d) sequences of unit cubes in such a way that each sequence starts from a random point in the base unit cube and satis es the condition that the next cube contains more points than the previous one. After that the algorithm returns a locally optimal cube C. Each sequence is constucted iteratively. Suppose that m cubes from a sequence are already constructed. There are two possible cases. 1. If the current cube can be translated with the current step by one of the axes (the initial step size is equal to s) with an increase in the number of enclosed points, then the current cube is moved to this position. 2. Otherwise, the current step size is decreased by a factor of < 1. If the step size threshold sminis reached then the procedure is terminated.
Under additional technical restrictions the authors of [4] proved the following precision and complexity bounds.
Theorem 1. Let Dalg be an optimal cube produced by the algorithm and Dopt be a globally optimal cube. Then 1 2d jDalg T P j jDopt T P j 1 and this estimate is sharp.
Theorem 2. The algorithm for nding an approximately optimal position of the box has
O dn log(n) +
f (n; d) d3n1 d1 smin ! worst-case time complexity and O(dn) space complexity.
O dn log(n) + d3n1 d1 smin f (n; d) !
n ! cmin worst-case time complexity and O(dn) space complexity. 4
Applying the Clustering Algorithm to \The Cancer Cell Line Encyclopedia" We consulted biologists and selected 432 columns of the expression table associated with genes encoding receptors, channels and transcription factors. First, we applied the clustering algorithm to the whole table. Thus, in our notation we have n equal to 917 and d equal to 432. For tuning algorithm parameters we used the following procedure. Let D denote the maximal pairwise distance t h g i e H 0.15 0.10 ) % 2 2 . 0 2 ( 2C 0.05 P 0.00 −0.05 −0.08 −0.04
0.00 PC1 (59.96%) 0.04 Fig. 2. Plot of the rst two principal components for the clusters; 29 outlying samples are removed from this gure. 1 r e t s u l C 266 21 0 2 r e t s u l C 0 0 0 6 r e t s u l C
between the points considered. By the Pythagoras theorem, all points can be placed in a cube with edge length Dpd. Then, a simple grid search approach on the interval 0; Dpd was utilized for nding an acceptable cube edge length. The remaining parameters were manually tuned in order to reach acceptable (accuracy) / (running time) ratio.
We seleceted the cube edge length equal to 6.7 (i.e. 1 = 2 = ::: = 432 = 6:7); cmin; s; smin and were set equal to 10, 0.5, 0.3, 0.9, respectively, and the function f (n; d) was taken as [log(dn)], where [x] denotes the integer part of x. Despite an acceptable run time (several minutes) the results were unsatisfactory: the output of the algorithm included one huge 390-element cluster, two mediumsized 77- and 69-element clusters, and the remaining approximately optimal cubes contained less than 10 points each. This means that more than 40% of samples (381 out of 917) actually were not clusterized. Such behavior was the result of strictness of the relation \a point lies in a box" which means that each coordinate of a point must fall into a xed range. Under this restriction, even one outlying coordinate of a point knocks it out of a cube. In high dimensional spaces single coordinate outliers are quite probable and inevitable, so before using the clustering algorithm it is reasonable to apply some dimension reduction and smoothing technique.
We applied Ward's method of hierarchial clustering to data features (R function hclust from the package stats [7] was used). The dendrogram produced (Fig. 1) was cut at height 55, which corresponds to 10 clusters. Then the expression values in the clusters were averaged. The new feature space had dimension d equal to 10. The greedy clustering algorithm was run on the dataset with reduced dimension with the cube length equal to 3; the other parameter values were left unchanged. The number of outliers essentially decreased after moving to the new agglomerated feature space | their quantity varied in the range between 25 and 35. The resulting partition consisted of 6 groups (see Fig. 2) and had an interesting biological interpretation. Namely, we calculated the number of samples in all intersections of clusters and organs. Based on this cardinalities we concluded that the clusters obtained were highly correlated with organ groups (see Fig. 3): { Group 1: haematopoietic and lymphoid tissue, liver, skin, central nervous system, bone, soft tissue, pleura; { Group 2: salivary gland, upper aerodigestive tract, oesophagus, biliary tract, stomach, pancreas, small intestine, large intestine, breast, thyroid, endometrium, urinary tract, lung (non-small cell cancer); { Group 3: Kidney, ovary, prostate; { Group 4: Autonomic ganglia and lung (small cell cancer).
It can be seen that major organ systems fall into di erent groups. Namely, Group 1 contains almost all non-solid organs, Group 2 contains organs from digestive system, Group 3 contains organs from genitourinary system, and Group 4 contains organs from autonomic nervous system and respiratory system. However Groups 2 and 3 seem to be dependent: Group 2 also contains some organs from genitourinary system. Thus the clusters di er by the organ systems they contain. Note that Figures 2 and 3 give ground to merge Cluster 6 with Cluster 1 and Cluster 5 with Cluster 4. The quality of the clusters can be additionally illustrated by more subtle arguments. For example, separation of small and non-small cell lung cancers seems to be reasonable, since there are some receptor coding genes which are di erently expressed in these cancer types [8]. Note also that small cell lung cancer appear in the same cluster with the autonomic ganglia cancer (neuroblastoma), since their molecular mechanisms include some number of the same receptors [9]. 5
In this paper we tested the applicability of the greedy clustering algorithm based on interval pattern concepts from the paper [4] to high-dimensional biomedical data. We showed that the clusters produced by the algorithm applied to \The Cancer Cell Line Encyclopedia" dataset were highly correlated with di erent organ groups and sophisticated molecular mechanismes of di erent cancer types. 2. Ganter, B., Kuznetsov, S.: Pattern Structures and Their Projections. Preprint MATH-AL-14-2000, Technische Universit at Dresden, Herausgeber, Der Rektor (2000) 3. Kaytoue, M., Duplessis, S., Kuznetsov, S.O., Napoli, A.: Two FCA-Based Methods for Mining Gene Expression Data. In: S. Ferre and S. Rudolph (Eds.): ICFCA 2009, LNAI 5548, pp. 2511{266, 2009. 4. Nersisyan, S.A., Pankratieva, V.V., Staroverov, V.M., Podolskii, V.E.: A Greedy Clustering Algorithm Based on Interval Pattern Concepts and the Problem of Optimal Box Positioning. Journal of Applied Mathematics, Article ID 4323590 (2017) 5. Barmin, V., Sadovnichy, ., Sokolov, M., Amiraliev, A., Pikin, O.: An original device for intraoperative detection of small indeterminate nodules. European Journal of Cardio-thoracic Surgery, 46(6), 1027{1031 (2014) 6. Barretina, J., Caponigro, G., Stransky, N. et al.: The Cancer Cell Line Encyclopedia enables predictive modelling of anticancer drug sensitivity. Nature 483(7391), 603{ 607 (2012) 7. R Core Team: R: A language and environment for statistical computing. R Foundation for Statistical Computing, Vienna, Austria (2018) 8. Wistuba, I.I., Gazdar, A.F., Minna, J.D.: Molecular genetics of small cell lung carcinoma. Seminars in Oncology 28(2 Suppl 4), 3{13 (2001) 9. Stone, J.P., Wagner, D.D.: P-selectin mediates adhesion of platelets to neuroblastoma and small cell lung cancer. The Journal of Clinical Investigation 92(2) (1993)