FCA, graphes médians et phylogéniecohen/assets/files/alainGely.pdf · 2019-11-22 · Motivation Pré-Requis Algorithme Conclusion FCA, graphes médians et phylogénie Alain Gély,

Motivation Pré-Requis Algorithme Conclusion

FCA, graphes médians et phylogénie

Alain Gély, Miguel Couceiro, Amedeo Napoli

LORIA (CNRS - Inria Nancy Grand Est - Université de Lorraine),{alain.gely, miguel.couceiro, amedeo.napoli}@loria.fr

journées QCM-BioChem, Paris, 29-30 Août 2018


Plan

1 Motivation

2 Pré-RequisTreillis et ensembles ordonnésTreillis distributifsTreillis distributifs et treillis des idéaux

3 AlgorithmeIdée généraleCalcul du contexte - Principe


Outline

1 Motivation




Phylogénie - liens inter-espèces

On recherche des arbres parcimonieux. Plusieurs arbrespeuvent être solution


Arbres phylogénétiques

Mettent en avant les filiations inter-espècesPermettent de suivre l’évolution des mutationsNe sont pas uniques


Garphe Médian

Un graphe médian est une structure qui contient l’ensembledes arbres phylogénétiques parcimonieux.


Graphe MédianDéfinition

Oui Oui Non

Définition

Graphe Médian G = (V ,E) tel que ∀x , y , z ∈ V , il existe un uniquesommet qui est l’intersection des plus courts chemins entre (x , y),(y , z) et (x , z).


Graphe médian et Treillis Distributifs

Liens forts entre graphe médian et treillis distributifsTreillis utilisés dans le cadre de la FCAU. Priss propose un algorithme pour utiliser les outils FCAen phylogénie.


ButConstruire le contexte d’un treillis distributif sans construire le treillis

context lattice distributive lattice


ButConstruire le contexte d’un treillis distributif sans construire le treillis


Outline

1 Motivation




Treillis et ensembles ordonnés

Treillis et Contexte

a

4

b/1

2

c

d/3

1 2 3 4a × × ×b × ×c × × ×d × ×

Définition(T ,≤,∨,∧) un treillisJ l’ensemble des éléments∨-irréductiblesM l’ensemble des éléments∧-irréductiblesOn considère un contexte (J,M,≤)


Treillis distributifs

DéfinitionUn treillis est distributif ssi ∨ et ∧ sont distributifs entre eux.

x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z)x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z)

Théorème

Un treillis (T ,≤,∨,∧) est distributif ssi une (toutes) lesdéfinitions équivalentes sont satisfaites :

1 (x ∧ y) ∨ (y ∧ z) ∨ (z ∧ x) = (x ∨ y) ∧ (y ∨ z) ∧ (z ∨ x)2 T contient exactement une double-flèche ↔ par ligne et

par colonne, sans autre flèches.3 T ne contient ni N5 ni M3 comme sous-treillis



Relations flèches - ↑ -relation

... m1 m2 ...

.

.

j ↑ ↑..



Relations Flèches - ↓ -relation

... m ...

.

.

j1 ↓j2 ↓..



Relations Flèches - ↔-relation

... m ...

.

.

j1 ↔j2 ↔..



Treillis et relations flèches - Treillis distributifs.

Théorème

Un treillis (T ,≤,∨,∧) est distributif ssi1 T contient exactement une double-flèche ↔ par ligne et

par colonne, sans autres flèches.

a

4

b/1

2

c

d/3

1 2 3 4a × × ↔ ×b × × ↔c ↔ × × ×d ↔ × ×



Treillis N5 et M3.

b/2a/1

c/3

a/1 c/3b/2

N5 1 2 3a × ↓ ↔b ↔ × ×c ↑ ↔ ×

M3 1 2 3a × ↔ ↔b ↔ × ↔c ↔ ↔ ×


Treillis distributifs et treillis des idéaux

L’ensemble des idéaux d’ordre d’un ensemble ordonné estun treillis, appelé treillis des idéauxLes treillis des idéaux sont en bijection avec les treillisdistributifsPlus précisément, un treillis distributif est en bijection avecle treillis des idéaux de (J,≤)

c

ba

↓ b = {b}

↓ c = {b, c}

{a, b, c}

↓ a = {a}

{a, b}

∅





RemarquePour un treillis non distributif T , il n’y a pas d’isomorphismeavec O(J(T )).Mais il existe un plongement de T vers O(J(T )).

b/2a/1

c/3

c

ba

↓ b = {b}

↓ c = {b, c}

{a, b, c}

↓ a = {a}

{a, b}

∅


Outline

1 Motivation




Idée générale

IdéeUtiliser un plongement pour obtenir un treillis distributif quiconserve les relations initiales entre les données.

ProblèmeComment calculer le contexte de ce treillis distributif ?


Calcul du contexte

Théorème (GW96)

Soit (P,≤) un ensemble ordonné, Alors C(P,P, 6≤) est lecontexte de I(P)


Calcul du contexte - Principe

Calcul de (J,≤)

1 2 3a ×b × ×c ×

j1 ≤ j2 ⇐⇒ j ′2 ⊂ j ′1

c

ba



Calcul de MdRemarque



Calcul de MdRemarque



Calcul de Mdéléments ∧-irréductibles de Ld

ma

ab ×c ×




ma mb

a ×b ×c ×




ma mb mc

a × ×b × ×c ×



Contexte espèce/attribut initial

Input context

1 2 3a ×b × ×c ×

Context résultat

ma mb mc

a × ×b × ×c ×



RemarquePriss, 2013

“an algorithm for converting a concept lattice [into a me-dian graph] consists of omitting the bottom node andthen checking every principal filter for distributivity andturning it into a distributive lattice if it is not already one.”



a b c d e1 × × ×2 × × ×3 × ×4 × ×5 ×6 ×

FIGURE – Contexte problématique et treillis des concepts associé



m2 m5 m1 m6

2 × × ×3 × ×5 ×1 × × ×4 × ×6 ×

(a) (b)

FIGURE – (a) Solution obtenue après une approche locale et (b)solution optimale.


En résumé

Algorithme qui produit un plongement dans un treillisdistributif ;Retourne le contexte sans avoir besoin de construire letreillis ;Conserve un lien entre le treillis initial et le treillis distributif,via l’isomorphisme de (J,≤)

Annexe

Bibliography

BibliographyBirkhoff, G. (1967).Lattice theory.In Colloquium Publications (3. ed.), Volume 25. Amer. Math. Soc.

Carpineto, C. et G. Romano (2004).Concept data analysis : Theory and applications.John Wiley & Sons.

Caspard, N., B. Leclerc, B. Monjardet, et al. (2007).Ensembles ordonnés finis : concepts, résultats et usages, Volume 60.Springer.

Davey, B. A. et H. A. Priestley (2002).Introduction to lattices and order.Cambridge university press.

Ganter, B. et R. Wille (1999).Formal concept analysis : mathematical foundations.Springer.

Bandelt, H.-J., P. Forster, A. Röhl (1999).Median-joining networks for inferring intraspecific phylogenies.Molecular biology and evolution 16(1), 37–48.

Priss, U. (2012).Concept lattices and median networks.In CLA, pp. 351–354.

Priss, U. (2013).Representing median networks with concept lattices.In ICCS, pp. 311–321. Springer.

Documents

FCA, graphes médians et phylogéniecohen/assets/files/alainGely.pdf · 2019-11-22 · Motivation Pré-Requis Algorithme Conclusion FCA, graphes médians et phylogénie Alain Gély,