Alain Gély
email: alain.gely@loria.fr

Miguel Couceiro
email: miguel.couceiro@loria.fr

Laurent Miclet
email: laurent.miclet@gmail.com

Amedeo Napoli
email: amedeo.napoli@loria.fr

A study of Algorithms Relating Distributive Lattices, Median Graphs, and Formal Concept Analysis

In this paper, we study structures such as distributive lattices, distributive semilattices, and median graphs from an algorithmic point of view. Such structures are very useful in classification and phylogeny for representing lineage relationships for example. A distributive lattice can be considered as a median graph while a distributive ∨-semilattice can be considered as a median graph provided that some conditions holding on triple of elements are satisfied. Starting from a lattice structure with different representations, we study the problem of building a median graph from such structures. We make precise and propose algorithms for checking how a lattice can be distributive and can be a median graph. Then, we adapt the problem to semilattices as a lattice where the bottom element is removed is a ∨-semilattice. We also state the problem in terms of Formal Concept Analysis and the representation of a lattice as a formal context, i.e., a binary table. Moreover, we also propose as input a system of implications such as the Duquenne-Guigues basis of a lattice, and we study how to compute such a basis for a distributive semilattice. In the paper, we provide algorithms and examples which illustrate the difficulties related to these different classification tasks. In particular, the minimality of the output lattices is a condition which is hard to ensure and which cannot be always achieved.

Motivations

Lattices and median graphs are two structures useful in many applications, in particular in classification and knowledge discovery [START_REF] Carpineto | Concept Data Analysis: Theory and Applications[END_REF][START_REF] Poelmans | Formal Concept Analysis in Knowledge Processing: A Survey on Applications[END_REF]. Median graphs are especially used in biology, for example in phylogeny, for modeling interspecies relationships [START_REF] Vigilant | Mitochondrial DNA sequences in Single Hairs from a Southern African population[END_REF][START_REF] Bandelt | Median-Joining Networks for Inferring Intraspecific Phylogenies[END_REF][START_REF] Bandelt | Median Networks: Speedy Construction and Greedy Reduction, One Simulation, and Two Case Studies from Human mtDNA[END_REF][START_REF] Bernt | Using Median Sets for Inferring Phylogenetic Trees[END_REF]. In phylogeny, one of the main problems is to discover evolution trees for representing existing species from accessible DNA fragments. When several trees are leading to the same inter-species phylogenetic relationships, the preferred ones are the most "parsimonious", where the number of modifications such as mutations for example, is minimal for the considered species. However, several possible parsimonious trees may exist. Such a situation arises with inverse or parallel mutations, e.g., when a gene goes back to a previous state or the same mutation appears for two non-linked species. This calls for a generic representation of such a family of trees.

In Bandelt et al. [START_REF] Bandelt | Median algebras[END_REF][START_REF] Bandelt | Median-Joining Networks for Inferring Intraspecific Phylogenies[END_REF], authors propose the notion of median graph to deal with this problem, since it was proved that a median graph may encode all parsimonious trees. It is also known that median graphs are related to lattices (see, e.g., [START_REF] Avann | Median Algebras[END_REF][START_REF] Bandelt | Median algebras[END_REF]) as follows. Any distributive lattice is a median graph while any median graph can be considered as a distributive ∨-semilattice such that, for all x, y, z, if the supremum of each pair exists, then the supremum of {x, y, z} also exists (it follows that a distributive ∨-semilattice is not necessarily a median graph). Dually, a median graph can be considered as a distributive ∧-semilattice such that, for all x, y, z, if the infimum of each pair exists, then the infimum of {x, y, z} also exists.

Formal Concept Analysis (FCA) is based on lattice theory and can be used in classification and knowledge discovery [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF]. In [START_REF] Priss | Concept Lattices and Median Networks[END_REF][START_REF] Priss | Representing Median Networks with Concept Lattices[END_REF] Uta Priss proposes for the first time to reuse the algorithmic machinery of FCA and the links between distributive lattices and median graphs to analyze phylogenetic trees. However, not every concept lattice is distributive, and thus does not correspond to a median graph. A transformation should be designed to build a median graph from a concept lattice. Moreover, in [START_REF] Priss | Representing Median Networks with Concept Lattices[END_REF] Uta Priss sketches an algorithm to convert any concept lattice into a median graph. The key step is to transform any concept lattice into a distributive lattice. However, how to transform a concept lattice into a distributive one is not detailed in [START_REF] Priss | Representing Median Networks with Concept Lattices[END_REF].

An example for relating a median graph and a concept lattice. In [START_REF] Bandelt | Median Networks: Speedy Construction and Greedy Reduction, One Simulation, and Two Case Studies from Human mtDNA[END_REF], Bandelt uses a data set borrowed from [START_REF] Vigilant | Mitochondrial DNA sequences in Single Hairs from a Southern African population[END_REF] to illustrate and evaluate a median graph. In this introduction, we will reuse this example to highlight the commonalities and differences between a median graph and a concept lattice.

The data set is an extract of mitochondrial DNA for 9 groups of individuals from a Khoisan-speaking hunter-gathered population in Southern Africa. For some sequences in mitochondrial DNA (nucleotide positions, denoted by a, b, . . . , j in the data table), a binary information indicates whether a group of individuals owns the consensus version of the sequence -marked as an empty cell in the data table-or a variation for this sequence -marked as a × in the corresponding cell in the data table. For each nucleotide position, the consensus version of the sequence is the one with the larger number of apparitions in the population. A sequence which is not the consensus version of the sequence is considered as a variation. The data table and the related consensus graph are shown in Table 1 and in Fig. 1 It can be noticed that the data table can fully be considered as a formal context from which a concept lattice can be issued, as it will be discussed below. In this table there are only 8 rows or individual groups (from 0 to 7). The potential ninth row is omitted as it does not present any The median graph related to Table 1.

a b c d e f g h i j 0 × × 1 × × 2 × × 3 × × 4 × × × 5 × 6 × × 7 × × ×
variation on any nucleotide position (consensus group) and thus is not marked with any cross.

In the median graph, vertices stands either for an individual group (numbered from 0 to 7 or consensus) or a latent vertex (L1, L2, L3, L4). A latent vertex corresponds to an hypothetical group of individuals which is not present in the data set. The existence of such a group is related to the "principle of parsimony". This principle assumes that, in an evolutionary process, there is no chance for two variations to exactly arise at the same moment in the same population. Thus, only one variation exists between two vertices -groups of individuals in the data set or latent vertices-in the nucleotide sequence. This variation is indicated over the edges. For example, there is only one variation from the consensus group to vertex L4 occurring in sequence g while there is again only one variation between vertex L4 and vertex 0 occurring in sequence j.

As recalled above, the median graph contains every parsimonious tree as a covering tree. A median graph shows some other good properties. Removing an edge labeled with a sequence variation produces two disconnected components, where one component corresponds to individuals holding the variation and the other component to the complementary, i.e., individuals not holding the variation. For example, the edges labeled with j partition the vertices in two connected components. The first component includes the vertices L1, 0, 2, 4, and 7, i.e., individuals holding a variant on position j. The complementary component includes all other vertices and the individual groups not holding this variant. By contrast, the individual groups represented by vertex 0 are related to a double variation denoted by gj. In this case, there is not enough data to determine whether the evolutionary path from the consensus started with a variant on position g, yielding the latent vertex L4, or with a variant on j, yielding latent vertex L1. Actually, the related median graph is able to display both alternatives, which would not be possible within a parsimonious tree.

In Table 1, the variations in the mitocondrial DNA sequences are represented as a binary data table. Accordingly, FCA algorithms can be applied to build a concept lattice which is shown in Fig. 2. In general, such a concept lattice does not correspond to a median graph. However, as FCA proposes a range of effective and efficient practical tools, the main idea of the present research work is to discuss and to show how to reuse FCA machinery to deal with phylogenetic data and median graphs. Following this idea, the binary data set can be modified in such a way that there exists a bijection between the resulting concept lattice -minus the bottom element-and a median graph. An example of such a transformation is given in Fig. 3. A new column k is added in the formal context (see Table 2) such that a new concept (046, k) appears in the new concept lattice, which corresponds to L4 in the median graph. This concept was missing in the concept lattice computed from the initial data set and displayed in Fig. 2 (a concept lattice which by the way does not correspond to a median graph).

a b c d e f g h i j k 0 × × × 1 × × 2 × × 3 × × 4 × × × × 5 × 6 × × × 7 × × ×
It should be noticed that the choice of the new column k is not unique and is guided by several constraints, among which building a concept lattice as close as possible to the initial median graph and minimal in the number of elements to be added.

Outline of the paper. This paper proposes a synthesis and an extension of two preceding papers published in [START_REF] Gély | Steps in the Representation of Concept Lattices and Median Graphs[END_REF][START_REF] Gély | Steps Towards Achieving Distributivity in Formal Concept Analysis[END_REF], which are based on representation theorem of Birkhoff for distributive lattice [START_REF] Birkhoff | Representations of lattices by sets[END_REF] and on Formal Concept Analysis [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF]. In this paper, we firstly gather some preceding results about the design of distributive lattices from several representations. We make precise the related algorithms and we give examples for illustrating our approach. In particular, we discuss the constraints related to distributivity but also the minimality of the designed structures. It appears that minimality is a hard constraint that cannot be always guaranteed. In addition, we start from several possible representations of lattices and semilattices, and an originality of this paper is to study how the Duquenne-Guigues implication basis, which is minimal and non-redundant, can be used for solving the problem of designing a median graph. This opens the way to an original and very interesting research line in the domain of distributive lattices. The summary of the paper is as follows. Basic definitions and notations are introduced in Section 2, while Section 3 considers the problem of embedding a lattice or a semilattice into a median graph. In subsection 3.1, we discuss how a lattice can be embedded into a lattice isomorphic to a median graph, while in subsection 3.2, we discuss the same problem for a semilattice. Algorithms are proposed and made precise in Section 4. Firstly, the inputs and outputs of algorithms are lattices or semilattices (see Section 3.1). Secondly, alternative representations such as contexts (see subsection 4.2) or implication bases (see subsection 4.3) are used as input and output of the algorithms.

Definitions and Notations

For the sake of completeness, we recall in this section definitions and notations needed throughout the paper. Moreover, we refer the reader to [START_REF] Davey | Introduction to Lattices and Order[END_REF][START_REF] Caspard | Finite Ordered Sets: Concepts, Results and Uses[END_REF] for more details about ordered sets and to [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF][START_REF] Ganter | Conceptual Exploration[END_REF] for more details about FCA.

Partially ordered sets and lattices

Only finite sets are considered in this paper. Given a poset (L, ≤) and X ⊆ L, ↓ X = {y ∈ L : y ≤ x for some x ∈ X} is the order ideal of X, while ↑ X = {y ∈ L : x ≤ y for some x ∈ X} is the order filter of X. The principal ideal of x is given by ↓ x (or ↓ {x}) and the principal filter by ↑ x (↑ {x}).

Given a poset (L, ≤) and x, y ∈ L, x ∨ y denotes the supremum of x and y while x ∧ y denotes the infimum. A ∨-semilattice (L, ≤) is an ordered set such that the supremum exists for all X ⊆ L, X = ∅. Dually, a ∧-semilattice (L, ≤) is an ordered set such that the infimum exists for all X ⊆ L. A lattice (L, ≤) is an ordered set such that a supremum and an infimum exist for all X ⊆ L. Such an order has a lowest element (bottom) denoted by ⊥ = L, and a greatest element (top) denoted by = L.

Given a lattice (L, ≤), an element x ∈ L such that x = y ∨ z implies x = y or x = z is a ∨-irreducible element. Dually, an element x ∈ L such that x = y ∧ z implies x = y or x = z is a ∧-irreducible element. The sets of ∧-irreducible elements and ∨-irreducible elements of L are respectively denoted by M(L) and J (L). Atoms are minimal ∨-irreducible elements while co-atoms are maximal ∧-irreducible elements. Atoms(L) and Coatoms(L) respectively denote the sets of atoms and co-atoms of L.

A lattice L is distributive if ∧ and ∨ are distributive operations, i.e., for every x, y, z ∈ L, one or equivalently both of the following identities hold:

(i) x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z), (ii) x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z).
A ∨-semilattice SL is distributive if for all x ∈ SL, the lattice defined by ↑ x is distributive, while a ∧-semilattice SL is distributive if for all x ∈ SL, the lattice defined by ↓ x is distributive. Since any sublattice of a distributive lattice is distributive, it is sufficient to check distributivity of ↑ x for x minimal element in SL, or dually distributivity of ↓ x for x maximal element in SL.

A main result about distributive lattices is given by "representation theorem of Birkhoff" [START_REF] Birkhoff | Representations of lattices by sets[END_REF], which is based on order ideals. Let (L, ≤) be a poset, ID(L) = { x∈2 L ↓ X} is the set of order ideals of L. Then, the representation theorem of Birkhoff for distributive lattices states that [START_REF] Birkhoff | Representations of lattices by sets[END_REF]:

Theorem of Birkhoff. For every poset L, the set ID(L) ordered by inclusion is a distributive lattice called the ideal lattice of L. Moreover, the poset of ∨-irreducible elements of ID(L) given by J (ID(L)) = {↓ x | x ∈ L} is order-isomorphic to L.

Median Graphs

The following property discussed in [START_REF] Bandelt | Median-Joining Networks for Inferring Intraspecific Phylogenies[END_REF] establishes links existing between median graphs and distributive lattices.

Definition and properties of a median graph. A graph is a median graph if and only if it is isomorphic to a ∨-semilattice L with the two following properties: i) dist: L is distributive, ii) triple: for all x, y, z ∈ L such that (x ∧ y), (y ∧ z), and (z ∧ x) are defined, then (x ∧ y ∧ z) is defined.

Thanks to duality between ∨ and ∧, the corresponding property exists in a distributive ∧-semilattice.

In the following and for the sake of simplicity, we will use the expressions "median lattice" and "median semilattice" for denoting a distributive lattice (respectively semilattice) verifying the conditions dist and triple.

Formal Concept Analysis

Formal Concept Analysis [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF][START_REF] Ganter | Conceptual Exploration[END_REF] is a mathematical formalism based on lattice theory and aimed at data analysis and knowledge discovery. FCA allows to build a concept lattice from a formal context (G, M, I) using two derivation operators. In (G, M, I), G is a set of objects, M a set of attributes, and I an incidence relation between objects and attributes. Given X ⊆ G and Y ⊆ M , the derivation operators denoted by work as follows:

X = {y ∈ M | xIy for all x ∈ X} is the set of attributes common to objects in X while Y = {x ∈ G | xIy for all y ∈ Y } is the set of objects having all attributes in Y . A formal concept is a pair (X, Y ) verifying X = Y and Y = X.
The extent X and the intent Y of the concept (X, Y ) are closed sets verifying X = X and Y = Y (derivation can be iterated). The set of all formal concepts ordered by inclusion of extents generates a concept lattice. Moreover, the set of extents and of intents are closure systems, i.e., a family of sets closed by intersection with a maximal element. The operator , which is the composition of the two derivation operators is a closure operator (a closure operator is monotone, extensive, and idempotent).

To terminate, we recall basics about implications and implication bases in concept lattices. Given a context (G, M, I), an implication between attributes in M is a pair of subsets of M , denoted by

A → B. A subset T ⊆ M respects the implication A → B if A ⊆ T or B ⊆ T .
Farther, we will use the notion of minimum basis of implications, i.e., a family of implications Σ which is minimal among all equivalent families of implications (they represent the same set of implications). In FCA, the so-called canonical basis or Duquenne-Guigues basis shows very interesting properties [START_REF] Guigues | Famille minimale d'implications informatives résultant d'un tableau de données binaires[END_REF].

Let X → X be a closure operator on M . A subset P ⊆ M is pseudo-closed iff (i) P = P , and (ii) if Q ⊂ P is a pseudo-closed proper subset of P , then

Q ⊆ P .
Then the canonical basis of Duquenne-Guigues can be defined as the set of implications {P → P | P is pseudo-closed}. This basis is sound, complete w.r.t. the operator , and non-redundant.

Embedding a Semilattice Into a Median Graph

In this section, firstly we investigate the following problem: considering a lattice L given as input, how to embed L into a median graph, in fulfilling some properties about minimality or maximality w.r.t. the size of the median graph. Secondly, we consider a variation of the above problem. While no particular information is usually associated with the element ⊥ in a lattice, given as input a ∨-semilattice SL -then SL ∪ {⊥} is a lattice-how to embed SL into a median graph.

Embedding a Lattice Into a Lattice Isomorphic to a Median Graph

A median graph is equivalent to a distributive ∨-semilattice SL when the triple condition is met. It should be noticed that if SL is a lattice, then the triple condition is obviously satisfied since the infimum exists for every subset of elements in SL. Thus, firstly we check how to embed a lattice L into a median graph which is also a lattice and not only a ∨-semilattice.

First order embedding proposal.

The problem can be formally stated as follows:

Problem 1. Basic order-embedding Input: a lattice L, Output: a lattice LM such that: i) L can be order-embedded into LM , ii) LM is a median graph.

Since LM is both a median graph and a lattice, then it follows that LM is a distributive lattice. It is straightforward that L can be order-embedded into a Boolean lattice, i.e., a distributive lattice isomorphic to (2 J (L) , ⊆). Actually, this output is not really interesting in data analysis tasks. Indeed, two different lattices L 1 and L 2 having the same number of ∨-irreducible elements, i.e., |J (L 1 )| = |J (L 2 )|, will be mapped into the same Boolean lattice whereas they can be very different.

Second order-embedding proposal with invariance of (J (L), ≤).

Regarding order-embedding, the Boolean lattice (2 J (L) , ⊆) is a maximal output w.r.t. the number of elements, but this embedding does not yield meaningful information. Recall that the posets of irreducible elements, namely (J (L), ≤) and (M(L), ≤), are important suborders of a lattice as they can be used to rebuild the whole lattice L. Moreover, we keep in mind that two lattices LM 1 and LM 2 may differ despite |J (L 1 )| = |J (L 2 )|. Any two lattices L 1 and L 2 are considered to be isomorphic iff (J (L 1 ), ≤) is isomorphic to (J (L 2 ), ≤) and (M(L 1 ), ≤) is isomorphic to (M(L 2 ), ≤). Then there does not exist any isomorphism between L 1 and L 2 when one or both posets differ, i.e., (J (L 1 ), ≤) = (J (L 2 ), ≤) and/or (M(L 1 ), ≤) = (M(L 2 ), ≤).

To enforce the output LM to be more closely related to the input lattice L, the following constraint relating L and LM can be considered: either (J (LM ), ≤) is isomorphic to (J (L), ≤) or (M(LM ), ≤) is isomorphic to (M(L), ≤). Here after, we assume that (J (LM ), ≤) is isomorphic to (J (L), ≤) and we investigate the following problem: Problem 2. Embedding with invariance of (J (L), ≤) Input: a lattice L, Output: a lattice LM such that:

i) L can be order-embedded into LM , ii) LM is a median graph, iii) (J (L), ≤) = (J (LM ), ≤).
A solution is directly given by the representation theorem of Birkhoff [START_REF] Birkhoff | Representations of lattices by sets[END_REF], where it is shown that there exists an isomorphism between the ideal lattice and a distributive lattice. It follows that the ideal lattice of (J (L), ≤) is a distributive lattice such that L can be order-embedded into (J (L), ≤). In this case, there is a ∧-embedding from L into LM , and LM is a maximal lattice with respect to the embedding with (J (L), ≤) = (J (LM ), ≤) [START_REF] Nation | The Lattice of Completions of an Ordered Set[END_REF].

Moreover, if we have LM = LD where LD is a distributive lattice such that LD can be order-embedded into LM , then (J (LM ), ≤) is not isomorphic to (J (LD), ≤), and thus the ideal lattice of (J (L), ≤) is the greatest lattice with respect to inclusion verifying (J (L), ≤) = (J (LM ), ≤).

Embedding a Semilattice Into a Semilattice Isomorphic to a Median Graph

In the previous subsection, we investigate the embedding of a lattice into a lattice isomorphic to a median graph. Here we do not consider anymore a lattice as input but instead a ∨-semilattice. This is justified by the fact that a median graph is usually not a lattice. More precisely we study the following problem: Problem 3. Embedding with invariance of (J (SL), ≤) Input: a ∨-semilattice SL, Output: SM a ∨-semilattice such that: i) SL can be order-embedded into SM , ii) SM is a median graph, iii) (J (SL), ≤) = (J (SM ), ≤).

As all sets are assumed to be finite, it should be noticed that a ∨-semilattice SL always verifies that {SL ∪ ⊥} is a lattice. In this way, given a ∨-semilattice SL, (J (SL), ≤) and (M(SL), ≤) denote the set of irreducible elements of the lattice {SL ∪ ⊥}. Then, one could argue that it could be sufficient to reuse and apply the preceding transformation to the semilattice {SL ∪ ⊥} and build a distributive lattice say SLM having the same set of ∨-irreducible elements. This is possible but not optimal as shown here after.

If a lattice L is distributive, then L\⊥ is a distributive ∨-semilattice. Next, a ∨-semilattice SL is distributive iff for each element e ∈ SL, ↑ e is a distributive lattice. ↑ e is a sublattice of SL and a sublattice of a distributive lattice is distributive. More than that, a ∨-semilattice SL is distributive iff for all minimal element e ∈ SL, ↑ e is a distributive lattice. The converse is not true in general: L\⊥ may be a distributive ∨-semilattice and L be a nondistributive lattice.

Two simple examples are the N 5 and M 3 lattices. Recall that a lattice L is not distributive iff the diamond M 3 or the pentagon N 5 is order-embedded into L (see for example [START_REF] Davey | Introduction to Lattices and Order[END_REF]). An embedding of the lattice M 3 -more generally M n where n is the number of atoms-into a distributive lattice with the same poset of ∨-irreducible element yields a Boolean lattice isomorphic to (2 n , ⊆). Thus a lattice with n + 2 elements such as M n can be embedded into a lattice with 2 n elements, i.e., (2 n , ⊆). Now, consider the ∨-semilattice SM n = M n \⊥, where the atoms of M n are the minimal elements of SM n . Given an atom a ∈ M n , the filter ↑ a = {a, } determines a total order and hence a distributive lattice. Then the lattice M n can be embedded into a Boolean lattice with 2 n elements while the semilattice SM n is isomorphic to a median graph and can be embedded into itself. This shows that the embedding of a ∨-semilattice such as L\⊥ can be much more compact w.r.t. the number of elements than the embedding of the related lattice L.

Existence of an infimum in the triple condition.

Recall that a median graph requires the two conditions dist and triple to be satisfied. The first condition dist is related to distributivity while the second condition triple involves the existence of particular infimum elements. Previously, as either the input or the output are lattices, the triple condition is satisfied because of the existence of an infimum for any subset of elements. Now, if a ∨-semilattice SL is considered, we must check that the triple condition is effectively satisfied. As {SL ∪ ⊥} is a lattice, the triple condition may be rewritten in such a way that it involves the ⊥ element:

if x ∧ y, y ∧ z, x ∧ z exist, then x ∧ y ∧ z also exists (triple) if x ∧ y > ⊥, y ∧ z > ⊥, x ∧ z > ⊥ then x ∧ y ∧ z > ⊥, (triple ⊥ )
In Section 4, we make precise the design of algorithms based on the condition triple ⊥ to compute a median graph as a semilattice or a lattice.

Minimal and minimum embedding

Given a semilattice SL, a subsequent question is to check whether there exists a minimum, i.e., minimal and unique, ∨-semilattice SM such that SL can be embedded into SM through an isomorphism between posets of ∨-irreducible elements. Actually, the answer is negative since a counter-example showing that such a minimum does not always exist was proposed in [START_REF] Gély | Embedding Median Graphs into Minimal Distributive Join-Semi-Lattices[END_REF] and is displayed in Fig. 4.

Given the lattice in subfigure (a), the lattices in subfigures (b) and (c) differ by only one element and are minimal distributive ∨-semilattices when the ⊥ element is removed. However, (b) and (c) are not isomorphic and no minimum ∨-semilattice exists. Then a practical strategy should be defined when using FCA algorithms to build median graphs. In the following section we show that the proposed algorithms do not always output a minimal solution.

Three Algorithms for Computing Distributive Lattices and Median Graphs

An Algorithm Based on a Lattice Structure

In this section, we propose an algorithm which takes a ∨-semilattice as input and returns as output a median graph. Below we explain the process and we prove the correctness of the algorithm. Then we adapt the algorithm to deal with alternate representations of a concept lattice such as a context or a basis of implications.

Algorithm 1: Construction of a median (∨-semi) lattice.

Data The algorithm implements the two conditions for a structure to be a median graph, i.e., checking whether the output satisfies the triple ⊥ condition and whether every atom filter in the output is a distributive lattice.

In algorithm 1, the triple ⊥ condition is verified in polynomial time w.r.t. the size of the lattice (checking for every triple). If triple ⊥ is not satisfied, then the algorithm outputs the ideal lattice of (J (SL), ≤). This is the only solution where (J (SL), ≤) is invariant. When triple ⊥ is satisfied, then the algorithm computes a ∨-semilattice, which can be considered as a lattice when the element ⊥ is added. The idea is to embed lattices defined by the filter of atoms into a distributive lattice using the representation theorem of Birkhoff.

It should be noticed that the triple ⊥ condition is checked over the input lattice, thanks to propositions 1 and 2 which are presented here after. Proposition 1 states that if the input concept lattice does not satisfy the condition triple ⊥ , the output cannot satisfy triple ⊥ either. Proposition 2 states that if the input satisfies the condition triple ⊥ , then the output of the algorithm should satisfy triple ⊥ . Lemma 1. Let L and LD be two lattices such that L can be embedded into LD and (J (L), ≤) is isomorphic to (J (LD), ≤). If triple ⊥ is not satisfied in L, then triple ⊥ cannot be satisfied in LD.

Proof. Since L and LD are two lattices such that L can be embedded into LD and (J (L), ≤) is isomorphic to (J (LD), ≤), the embedding from L to LD is ∧-preserving. It follows that if there exist x, y, z ∈ L such that x ∧ y > ⊥,

x ∧ z > ⊥, y ∧ z > ⊥, and x ∧ y ∧ z = ⊥, then there exist three elements f (x), f (y), and f (z) in LD, images of x, y, z through the embedding, such that

f (x) ∧ f (y) > ⊥, f (x) ∧ f (z) > ⊥, f (y) ∧ f (z) > ⊥, and f (x) ∧ f (y) ∧ f (z) = ⊥,
and thus triple ⊥ is not satisfied in LD.

The following proposition is a consequence of the lemma: Proposition 1. If L is a lattice in which there exist x, y, z ∈ L with x ∧ y, x ∧ z, y ∧ z > ⊥ and x ∧ y ∧ z = ⊥, then there is exactly one median semilattice S L such that (J (L), ≤ L ) is isomorphic to (J (S L ), ≤ S L ). This semilattice is the ideal lattice of (J (L), ≤ L ).

Proof. Let us consider a lattice L and a semilattice S L verifying the hypotheses. Let us add the new element a = x ∧ y ∧ z to S L and check whether S L is a median semilattice. There are two alternatives which are illustrated in Fig. 5.

1. a = ⊥ and in this case S L is a lattice. In addition, S L is a median semilattice if it is distributive, and thus corresponds to the ideal lattice of (J (L), ≤). 2. a = ⊥ and in this case a is a new atom in S L and thus a new ∨-irreducible element. Then it can be checked that there is no isomorphism between (J (L), ≤) and (J (L d ), ≤)

(i) (ii)
Figure 5: Illustration of the proof of Proposition 1. In the lattice (i), each filter is distributive and L\⊥ is a distributive ∨-semilattice. However, triple ⊥ is not satisfied. A first alternative is to keep ⊥ in L but then the lattice (i) should be distributive and this is not the case. Another alternative is to add a new infimum distinct from ⊥. Then the posets of ∨-irreducible elements of (i) and (ii) are no more isomorphic, which violates the hypothesis of the proposition.

When the condition triple ⊥ is satisfied, it remains to ensure that every filter of L\⊥ is distributive. This process is performed as follows. The filter of an atom a is considered as an independent lattice denoted by L a and the theorem of Birkhoff is used to compute the ideal lattice of (J (L a )). The ideal lattices of the atoms are combined using the ideal representation of each atom and the inclusion order. At this step, it may be possible that an element in the filter of the atom a belongs to the filter of another atom b and breaks the distributivity in ↑ b. In this case, the process of adding a new element is repeated until a fixpoint is reached, i.e., it is no more necessary to add a new element as distributivity is achieved. Such a fixpoint exists, since at each step, only new elements are added and at most the ideal lattice of (J (L), ≤) is obtained (See Fig. 6). Moreover, from one step to the other, the condition triple ⊥ remains satisfied.

Proposition 2. Let us consider Algorithm 1 and assume that SM i is the lattice used in iteration i.

If triple ⊥ is satisfied in iteration i then triple ⊥ is satisfied in iteration i + 1, Proof.
In each iteration i of algorithm 1, i.e., an iteration of the "repeat" loop, a lattice SM i is embedded into a new lattice SM i+1 such that (J (SM i ), ≤) is isomorphic to (J (SM i+1 ), ≤). Let us assume that:

1. in SM i , the condition triple ⊥ is satisfied, 2. in SM i+1 , the condition triple ⊥ is not satisfied, i.e., there exist e 1 , e 2 , e 3

such that e 1 ∧ e 2 ∧ e 3 = ⊥, e 1 ∧ e 2 = x = ⊥, e 1 ∧ e 3 = y = ⊥, and e 2 ∧ e 3 = z = ⊥.

We will show that these two hypotheses are leading to a contradiction. When triple ⊥ is satisfied in SM i , at least one of the three elements e 1 , e 2 , e 3 should not belong to SM i , say e 3 (without loss of generality). Then e 3 can be considered as a new element where y < e 1 and y < e 3 since y = e 1 ∧ e 3 . As well z < e 2 and z < e 3 as z = e 2 ∧ e 3 .

In the algorithm, the new element e 3 is introduced in SM i+1 because the filter of an atom a is not distributive in SM i . Thus there exists an atom a with a < y < e 3 and a < z < e 3 . Moreover, a < y < e 1 and a < z < e 2 . To sum up, it comes that a < e 1 , a < e 2 , a < e 3 and then it follows that e 1 ∧e 2 ∧e 3 ≥ a > ⊥. This leads to a contradiction with hypothesis 2 above.

Thus we may conclude that if the condition triple ⊥ is satisfied at the beginning of an iteration i, then it is satisfied at the beginning of the next iteration i + 1.

In Algorithm 1, the filters of the atoms are considered independently one from the others. This approach is correct but does not necessarily output a minimal embedding, i.e., there may exist a distributive ∨-semilattice SM m that can be embedded in SM , while SL can be embedded into

SM m with |SD| < |SM m | < |SM | and (J (SL), ≤) = (J (SM m ), ≤) = (J (SM ), ≤).
This may happen because each filter is independently processed, and an element may belong to several filters, then processing one filter may break the distributivity of another one. This is illustrated in Fig. 6. Element g is added in (ii) to make distributive the left atom filter -denoted by 1 in (ii). However, applying the same process for making distributive the filter of the rightmost atom -denoted by 4 in (ii)-the filter of 1 is no more distributive. A local modification of the filters, e.g., adding the element r in the filter of 4 but also in the filter of 1, may have an impact on neighboring filters and breaks the distributivity. The processing of filters consists in adding elements until no more change arises and distributivity is satisfied. The resulting structure is a median graph, i.e., a distributive ∨-semilattice satisfying the triple condition. However, there is no guarantee that this resulting structure is of minimal size w.r.t. the number of elements. In particular, it should be noticed that lattice (iv) in Fig. 6 is a minimal lattice verifying all the constraints and where only one element is added w.r.t. the initial lattice (i). However, this lattice cannot be designed by the algorithm, showing that minimality of the output lattice cannot be guaranteed.

(i) (ii) (iii) (iv)

An Algorithm Based on a Formal Context

In this subsection, we present an algorithm whose input is a standard context -as used in FCA or in phylogeny-and whose output is the context related to a distributive lattice verifying the properties of a median graph, namely dist and triple.

Firstly, let us recall that the standard context of the ideal lattice of a poset P is given by (P, P, ≥) [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF]. The ideal lattice of ∨-irreducible elements (J(P ), ≤) can be computed from the context (P, P, ≥). Moreover, embedding every atom filter into a distributive lattice can be performed in polynomial time in the size of the context. Then it remains to check the triple condition when the input is a context. To sum up, we present in the following the design of an algorithm deciding in polynomial time in the size of a context, i.e., J (L) × M(L), whether the condition triple is satisfied. This is the objective of the following lemma.

Lemma 2. Let L be a lattice. There exist x, y, z ∈ L such that x ∧ y, x ∧ z, y ∧ z > ⊥ and x ∧ y ∧ z = ⊥ iff there exist a x , a y , a z ∈ Atoms(L), and m x , m y , m z ∈ M(L), such that:

• a x ≤ m x , a x ≤ m y , a x ≤ m z , • a y ≤ m y , a y ≤ m x , a y ≤ m z , • a z ≤ m z , a z ≤ m x , a z ≤ m y .
Proof. Suppose that there exist x, y, z ∈ L such that x ∧ y, x ∧ z, y ∧ z > ⊥ and x ∧ y ∧ z = ⊥. Then there exist 3 atoms a x , a y , a z such that: (i)

a z ≤ x ∧ y and a z ≤ z otherwise x ∧ y ∧ z ≥ a z > ⊥. Similarly, it comes (ii) a y ≤ x ∧ z, a y ≤ y otherwise x ∧ y ∧ z ≥ a y > ⊥, and (iii) a x ≤ y ∧ z, a x ≤ x otherwise x ∧ y ∧ z ≥ a x > ⊥.
Now let us pick m i ∈ M ax(M(L)\ ↑ a i ) with i ∈ {x, y, z}. Then, (i) m x is greater than a y and a z and not greater than a x , and similarly, (ii) m y is greater than a x and a z and not greater than a y , and (iii) m z is greater than a x and a y and not greater than a z , showing that the conditions are necessary. Now, for showing that the conditions are also sufficient, let us suppose that there are a 1 , a 2 , a 3 ∈ Atoms(L) and m 1 , m 2 , m 3 ∈ M(L) such that: (i)

a 1 ≤ m 1 , a 1 ≤ m 2 , a 1 ≤ m 3 , (ii) a 2 ≤ m 2 , a 2 ≤ m 1 , a 2 ≤ m 3 , and (iii) a 3 ≤ m 3 , a 3 ≤ m 1 , a 3 ≤ m 1 .
A solution is given by x = a 2 ∨ a 3 , y = a 1 ∨ a 3 , and z = a 1 ∨ a 2 . It should be noticed that there cannot be any comparable pair from {x, y, z} as this would contradict the existence of m 1 , m 2 , m 3 ∈ M(L) satisfying the conditions of the lemma. Hence, x, y and z are pairwise incomparable w.r.t. ≤. Moreover, x ∧ y > ⊥, x ∧ z > ⊥, y ∧ z > ⊥ and x ∧ y ∧ z = ⊥. This completes the proof of the lemma.

This lemma ensures that it is possible to check whether the triple ⊥ condition is satisfied in polynomial time in the standard context of a lattice. It should be noticed that this problem can be seen as a variation applied to atoms, i.e., minimal ∨-irreducible elements, of a result obtained on totally balanced matrices, see for example [START_REF] Anstee | Characterizations of Totally Balanced Matrices[END_REF][START_REF] Brucker | Totally Balanced Formal Context Representation[END_REF].

Algorithm 2 is based on Lemma 2. The input of the algorithm is a context CT which is a representation of a semilattice, i.e., the concept lattice related to CT minus the element ⊥. The output of the algorithm is a context and the Boolean value triple ⊥ . If triple ⊥ is true, then the output context is the representation of a median semilattice (the lattice without the bottom element ⊥). If triple ⊥ is false, then the output context is the representation of the ideal lattice of (J (L), ≤). if tri == f alse then return CT (J (L), J (L), ≥), f alse foreach j ∈ J (L), minimal do (P j , ≤) ← ∅ repeat stability ← true; foreach j ∈ J (L), minimal do compute P j the poset of ∨-irreducible elements in ↑ j compute CT j = (P j , P j , ≥) if P j modified since last iteration then stability ← false;

Merge all CT j = (P j , P j , ≥) in a unique context CT Reduce CT until stability return CT (L med ), true

An Algorithm Based on an Implication Basis

In this section, we consider an alternative representation in the FCA formalism which is based on an implication basis. In the preceding section we were interested in building a median semilattice based on a lattice L and on the reduced context (G, M, I) related to L. Here we still study how to build a semilattice SL but this time based on the Duquenne-Guigues basis -DG-basis-of implications, also called the canonical basis of implications (see [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF][START_REF] Ganter | Conceptual Exploration[END_REF] for example). The objective is to build the DG-basis of a distributive ∧-semilattice starting from the DG-basis of an arbitrary lattice, taking into account ∧-irreducible elements and the fact that any two elements should have a meet.

More practically, for working with implications, we consider a ground set on which are based all implications and which corresponds to J, i.e. the set of ∨-irreducible elements, represented by the element in the lattice L. A correspondence can be made with FCA and a context (G, M, I), where the ground set would be M . Moreover, for an element m of the lattice L, we denote the "closure" m of m as m = {↓ m} ∩ J.

The main principle on which are relying the algorithms presented above is to decompose an initial lattice into sublattices related to atoms. Each sublattice corresponds to the filter {↑ a} of an atom a and is modified in order to meet constraints related to a median semilattice (i.e., dist and triple conditions). Then starting with the reduced context of a lattice L, one can build the context corresponding to the filter {↑ a} of an atom a. Such an operation is not so straightforward when the input is the DG-basis of the underlying lattice. There does not exist any easy way to build the DG-basis of the filter {↑ a} of an atom a or of any other element of the initial lattice L. By contrast, given a co-atom m ∈ L, the DG-basis of the ideal {↓ m} can be easily built from the DG-basis of L.

This can be illustrated as follows. Let us consider Σ L = Σ m ∪ Σ m the DGbasis of L. Then the DG-basis of {↓ m} is given by Σ m , where m = {↓ m} ∩ J:

• Σ m = {P → P } with P ⊆ m , • Σ m = {P → P } with P ⊆ m .
Actually, the implications lying in Σ m are related to elements which are not in m and thus which are neither related to any closed set in m nor in {↓ m}. Moreover, Σ m is an implication basis of {↓ m} where implications are related to closed sets which are lower than m for the lattice order (recall that {↓ m} is an ideal). In addition, Σ m is a DG-basis. Let us suppose the contrary, then P is not a pseudo-closed set in at least one implication P → P in Σ m . In such a case, P would not be either a pseudo-closed set in Σ L which contradicts the initial hypothesis.

Building a distributive ∧-semilattice.

As discussed above, a median graph can be seen as a ∨-semilattice or a ∧-semilattice verifying the conditions of distributivity (dist) and existence of a lower bound (triple). The algorithms defined above are based on filters in a ∨-semilattice, i.e., L \ ⊥. Let us now consider the dual situation and a ∧semilattice based on ideals. We have just seen above how to build the DG-basis related to the lattice induced by an ideal {↓ m}. Then contrasting what was done in the preceding sections, we will now consider a ∧-semilattice and L \ instead of L \ ⊥. While the latter condition is changed, we are still trying to build a median semilattice SL (i.e., L\ ) where the set of ∨-irreducible elements namely J is invariant, and such that the initial lattice L can be embedded into SL. This can be summarized in the following theorem: Theorem 1. Let us consider a lattice L and the related DG-basis Σ L . Then L \ is a distributive ∧-semilattice iff for every implication P → P ∈ Σ L , |P | = 1 or P = .

Proof. For proving this theorem, we should recall that the DG-basis of a distributive lattice L is such that [START_REF] Demetrovics | Functional Dependencies in Relational Databases: A Lattice Point of View[END_REF][START_REF] Monjardet | The presence of lattice theory in discrete problems of mathematical social sciences[END_REF]: Σ L = {j → j | j ∈ (J (L), ≤)}, where (J (L), ≤) is the set of ∨-irreducible elements in L.

Let m be a co-atom in L and suppose that for all P → P ∈ Σ L , either |P | = 1 or P = . Intuitively, the condition P = corresponds to the case P = J, i.e., there does not exist a closed element including P without including all other elements.

Then, {↓ m} is a lattice such that Σ {↓m} = {P → P | P → P ∈ Σ L , P ⊆ {↓ m}}. As m is a co-atom, m < and P = . It follows that every implication P → P in Σ {↓m} is such that |P | = 1 and that the DG-basis of the lattice {↓ m} is of the form {j → j }, i.e., the implication basis of a distributive lattice. Thus L\ is a distributive ∧-semilattice. Now, let us assume that L\ is a distributive ∧-semilattice. Then every ideal is a distributive lattice where the DG-basis is such that Σ L = {P → P } with |P | = 1. Σ L includes every implication of the form {j → j } and as well implications {P → P } such that P \m = ∅ for a co-atom m ∈ L. In such a case, P can only be . This theorem can be implemented within an algorithm designing the DGbasis of a ∧-semilattice L \ based on the DG-basis of an arbitrary lattice L. If Σ L denotes the DG-basis of the lattice L, then one can build Σ L\ corresponding to the ∧-semilattice L \ , i.e., Σ L\ = {P → P | P → P ∈ Σ L , |P | = 1 or P = }.

As Σ L\ ⊆ Σ L , then L can be embedded into L \ . Moreover, since Σ L\ and Σ L have the same set of implications, i.e., P → P with |P | = 1, the lattices L and L \ have the same set of ∨-irreducible elements.

Finally, for building a median graph, the triple condition remains to be satisfied based on the DG-basis. This last point should still be investigated in future work.

Conclusions and Perspectives

In this paper, we investigated how to build a median graph from a lattice and a semilattice. In particular, we also studied how this can be adapted to the special case of concept lattices in Formal Concept Analysis. We have made precise three algorithms whose output is a median graph. The first one has as input a lattice or a semilattice. The second and third algorithms are working within the formalism of FCA and take as input a formal context and an implication basis respectively. These algorithms run in polynomial time in the size of the input and the size of the output. When the input is an implication basis -actually the canonical basis in a concept lattice-we derive a condition such that a canonical basis corresponds to a distributive ∨-semilattice. However, this condition is necessary but not sufficient.

Then many directions are possible for future work. We have still to study how to deal with the triple condition when the input and output are an implication basis. Moreover, we should also work on the minimality of the output distributive lattices. The median graphs which are returned by the algorithms verify the properties (i) L\⊥ can be order-embedded into a semilattice SL, and (ii) there is an isomorphism between (J (L), ≤) and (J (SL ∪ {⊥}), ≤). The property (i) seems to be natural in applications. In phylogeny problems for example, one can be interested in adding latent vertices representing the species not yet observed, while the relative order of the observed species should not be changed. The second property can be considered as an extension of the first one, as all elements in a lattice can be inferred from irreducible elements. In this way, the invariance of the poset of ∨-irreducible elements ensures that the "core" of the data under study does not change.

Finally, we have also to work on the minimality of the output structures. We have shown and discussed the lack of a minimum solution when the two properties (i) and (ii) are satisfied. Thus the existence and the way how to reach such a minimum solution if any remains to be more deeply investigated.

Figure 1 :

 1 Figure1: The median graph related to Table1.

Figure 4 :

 4 Figure 4: The lattice in subfigure (a) is such that there exist two non isomorphic minimal distributive ∨-semi-lattices (b) and (c) when the bottom element is removed.

Figure 6 :

 6 Figure 6: From left to right and top to bottom: (i) The input lattice: one element is at the intersection of two filters. (ii) During the first iteration in the loop of Algorithm 1, g is added for making the filter ↑ 1 distributive. Similarly, r is added for making the filter ↑ 4 distributive. However, g belongs to ↑ 4 while r belongs to ↑ 1, which breaks distributivity in ↑ 1 and ↑ 4 at the end of the first iteration. Thus new elements should be added. (iii) After a finite number of iterations, no more elements need to be added to the filters as they are all distributive. The output of the algorithm is a lattice structure. (iv) The semilattice (i)\⊥ can be embedded into the semilattice (iv)\⊥ which is a median graph with the same poset of ∨-irreducible elements as lattice (i).

Algorithm 2 :

 2 Construction of the context of a median (∨-semi) lattice. Data: A context CT (L) = (J (L), M(L), I) of a lattice L. Result: A context CT (L med ) = (J (L med ), M(L med ), I) and the Boolean value triple ⊥ . tri ← check_triple ⊥ _condition((J (L), M(L), I))

Table 1 :

 1 In this data table borrowed from[START_REF] Bandelt | Median Networks: Speedy Construction and Greedy Reduction, One Simulation, and Two Case Studies from Human mtDNA[END_REF], a row stands for a groups of individual and a column for a variation in the mitocondrial DNA sequence.

Table 2 :

 2 A new column k is added to the data table 1 for building a concept lattice which is a distributive ∨-semilattice when ⊥ is removed.

			01234567,{}
			046,k	0247,j
		13,a	46,hk	04,jk	27,cj
	1,ae	3,ai	6,bhk	4,ghjk	7,cfj	5,d
			{},abcdefghijk
	Figure 3: The new concept lattice issued from the modified data table displayed in Table 2
	which yields a median graph when the bottom element is omitted.

  : A semilattice SL Result: a semilattice SM and a Boolean triple ⊥ triple ⊥ ← check_triple ⊥ _condition(SL) if triple ⊥ == f alse then return ID(J (SL ∪ ⊥)), ⊆), triple

⊥ SM ← SL; repeat stability ← true; foreach a ∈ atoms(SM ) do compute P a the poset of ∨-irreducible elements in ↑ a SM ← SM ∪ ID(P a ) (embed the lattice ↑ a into the ideal lattice of ∨-irreducible elements) if SM modified since last iteration then stability ← false; until stability return {(SM, ⊆), triple ⊥ }