View
1
Download
0
Category
Preview:
Citation preview
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
Motivation Pré-Requis Algorithme Conclusion
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
Motivation Pré-Requis Algorithme Conclusion
Outline
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
Motivation Pré-Requis Algorithme Conclusion
Phylogénie - liens inter-espèces
On recherche des arbres parcimonieux. Plusieurs arbrespeuvent être solution
Motivation Pré-Requis Algorithme Conclusion
Arbres phylogénétiques
Mettent en avant les filiations inter-espècesPermettent de suivre l’évolution des mutationsNe sont pas uniques
Motivation Pré-Requis Algorithme Conclusion
Garphe Médian
Un graphe médian est une structure qui contient l’ensembledes arbres phylogénétiques parcimonieux.
Motivation Pré-Requis Algorithme Conclusion
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).
Motivation Pré-Requis Algorithme Conclusion
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.
Motivation Pré-Requis Algorithme Conclusion
ButConstruire le contexte d’un treillis distributif sans construire le treillis
context lattice distributive lattice
Motivation Pré-Requis Algorithme Conclusion
ButConstruire le contexte d’un treillis distributif sans construire le treillis
Motivation Pré-Requis Algorithme Conclusion
Outline
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
Motivation Pré-Requis Algorithme Conclusion
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,≤)
Motivation Pré-Requis Algorithme Conclusion
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
Motivation Pré-Requis Algorithme Conclusion
Treillis distributifs
Relations flèches - ↑ -relation
... m1 m2 ...
.
.
j ↑ ↑..
Motivation Pré-Requis Algorithme Conclusion
Treillis distributifs
Relations Flèches - ↓ -relation
... m ...
.
.
j1 ↓j2 ↓..
Motivation Pré-Requis Algorithme Conclusion
Treillis distributifs
Relations Flèches - ↔-relation
... m ...
.
.
j1 ↔j2 ↔..
Motivation Pré-Requis Algorithme Conclusion
Treillis distributifs
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 ↔ × ×
Motivation Pré-Requis Algorithme Conclusion
Treillis distributifs
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 ↔ ↔ ×
Motivation Pré-Requis Algorithme Conclusion
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}
∅
Motivation Pré-Requis Algorithme Conclusion
Treillis distributifs et treillis des idéaux
Motivation Pré-Requis Algorithme Conclusion
Treillis distributifs et treillis des idéaux
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}
∅
Motivation Pré-Requis Algorithme Conclusion
Outline
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
Motivation Pré-Requis Algorithme Conclusion
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 ?
Motivation Pré-Requis Algorithme Conclusion
Calcul du contexte
Théorème (GW96)
Soit (P,≤) un ensemble ordonné, Alors C(P,P, 6≤) est lecontexte de I(P)
Motivation Pré-Requis Algorithme Conclusion
Calcul du contexte - Principe
Calcul de (J,≤)
1 2 3a ×b × ×c ×
j1 ≤ j2 ⇐⇒ j ′2 ⊂ j ′1
c
ba
Motivation Pré-Requis Algorithme Conclusion
Calcul du contexte - Principe
Calcul de MdRemarque
Motivation Pré-Requis Algorithme Conclusion
Calcul du contexte - Principe
Calcul de MdRemarque
Motivation Pré-Requis Algorithme Conclusion
Calcul du contexte - Principe
Calcul de Mdéléments ∧-irréductibles de Ld
ma
ab ×c ×
Motivation Pré-Requis Algorithme Conclusion
Calcul du contexte - Principe
Calcul de Mdéléments ∧-irréductibles de Ld
ma mb
a ×b ×c ×
Motivation Pré-Requis Algorithme Conclusion
Calcul du contexte - Principe
Calcul de Mdéléments ∧-irréductibles de Ld
ma mb mc
a × ×b × ×c ×
Motivation Pré-Requis Algorithme Conclusion
Calcul du contexte - Principe
Contexte espèce/attribut initial
Input context
1 2 3a ×b × ×c ×
Context résultat
ma mb mc
a × ×b × ×c ×
Motivation Pré-Requis Algorithme Conclusion
Calcul du contexte - Principe
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.”
Motivation Pré-Requis Algorithme Conclusion
Calcul du contexte - Principe
a b c d e1 × × ×2 × × ×3 × ×4 × ×5 ×6 ×
FIGURE – Contexte problématique et treillis des concepts associé
Motivation Pré-Requis Algorithme Conclusion
Calcul du contexte - Principe
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.
Motivation Pré-Requis Algorithme Conclusion
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.
Recommended