Les arborescences comme des structures de données

Au travail, je suis devenu familier avec les arborescences. Il s’agit d’une façon de représenter une collection de données. Les relations entre les instances d’une arborescence sont relativement intuitives á comprendre, grâce à l’analogie avec les arbres botaniques, avec lesquelles on est familier (j’espère). Les idées des racines, des feuilles, et des branches se transfèrent assez bien quand on parle de la structure de données, plutôt que la plante périnéale.

Les arbres et les hiérarchies se trouvent partout — notamment sont, parmi les exemples dans le monde réel, les structures des entreprises et les arbres évolutionnaires.

On peut voir que c’est relativement facile à dessiner un arbre pour un ensemble de données qui est lié hiérarchiquement. Mais qu’est-ce qu’il faut faire quand on a beaucoup de données, ou si les données évoluent constamment ? Le processus de redessiner l’arbre entier est douloureux et consomme pas mal de temps…

ETE Toolkit

C’est ici qu’ETE Toolkit peut nous aider. Il s’agit d’une bibliothèque Python pour l’analyse et la visualisation des arborescences. C’était développée originalement par la faculté de bio-informatiques au Principe Felipe Centre de Recherche à Valence, Espagne, donc c’est capable de tout un tas d’analyses scientifiques. Elle fournit une façon utile à automatiser la visualisation de n’importe quelle structure de données avec la forme d’un arbre. On ne va que traiter les basiques ici — jetez un petit coup d’œil à la gallérie ETE Toolkit pour voir quelques fonctionnalités plus avancées.

La visualisation d’un système pour les renvois d’abonnés

Alors, par exemple, utilisons un système pour les renvois d’abonnés. Vous êtes probablement familier avec la façon dans laquelle ça marche — un client qui a acheté un produit est donné un code unique pour partager avec un ou une de leurs amis. Si l’un d’entre eux décide à obtenir le produit aussi et utilise ce code quand on le fait, les deux reçoivent une récompense. Il s’agit d’un scénario gagnant-gagnant — l’entreprise qui vend le produit peut concorder les intérêts des clients avec les siens en fournissant une motivation pour passer le mot au niveau du produit. Et bien sûr, les clients eux-mêmes profitent d’une réduction.

Disons que chaque client est permis à recommander jusqu’à cinq personnes. Disons aussi qu’on a actuellement nos données sous forme de tableau, comme ci :

On a les données sur plusieurs achats. En particulier :

• La date de l’achat ;
• Le nom du client ;
• Qui a recommandé le client ; et
• Combien d’argent ce client a dépensé.

Les données ici ont une forme hiérarchique — chaque client peut être représenté avec un nœud d’un arbre, avec la personne qui l’a recommandé en haut de lui. Les autres que le client lui-même a recommandés se trouvent en bas. On peut aussi voir ici qu’Alice est la cliente « originale » qui a créé cette chaîne particulière de recommandations — c’est-à-dire, Alice est la seule cliente qui n’était pas recommandée par quelqu’un d’autre. Du coup, elle est la racine de cet arbre.

Cela étant, on pourrait dessiner un diagramme à la main — on pourrait traverser chaque client et élaborer qui devrait être lié au client dans l’arbre, ajoutant les « fils » où c’est nécessaire. Mais pourquoi le faire quand ETE peut faire tout le boulot pour nous ?

ETE reçoit des informations sous format « Newick » — qui est une manière relativement standarde pour décrire la structure d’un arbre de façon compacte, utilisée dans les domaines mathématiques et scientifiques. Laissez-moi vous donner quelques exemples:

Vous pouvez probablement remarquer qu’un ensemble des branches est représenté par une paire de parenthèses. Le nombre de branches qui viennent d’une des branches est déterminé par la présence de virgules entre les parenthèses. Et bien sûr, les parenthèses peuvent être emboitées afin de produire des structures de plus en plus complexes.

Je ne vais pas rentre dans les détails du format Newick — ça suffit de savoir qu’on peut indiquer à ETE ce qu’on veut en transformant nos données en ce format. J’ai écrit un peu de code pour le faire pour nous que je ne vais pas expliquer ici — si vous êtes intéressé, jetez un œil au Notebook Jupyter sur GitHub qui accompagne ce poste pour plus d’informations.

Nos données des clients peuvent être écrit sous format Newick comme ci :

Voyons ce qu’on obtient quand on les donne à ETE :

Pas mal ! Un peu basique maintenant, me semble-t-il — mais ETE a facilité le processus de visualisation. En plus, on peut simplement reprendre le code lorsqu’on obtient les données actualisées !

Un autre avantage d’ETE s’agit du fait qu’on peut facilement faire les ajustements aux aspects de présentation de l’arbre. Voyons si on peut le rendre un petit peu plus beau…

C’est mieux. On ne gratte que la surface des capabilités d’ETE Toolkit — mais pour une petite démonstration, c’est suffisant pour obtenir les idées clées.

Conclusion

Le cerveau humain adore aspirer les informations visuels. Les arborescences viennent avec une analogie simple qui les rend intuitive et facile à comprendre. Du coup, elles sont un bon outil pour l’expression et l’explication des idées aux non-spécialistes. Enfin, une dernière généralisation — le cerveau a un nombre de points forts et un nombre de faiblesses. En ce qui concerne ces particularités, on va toujours avoir plus de facilité à digérer les données quand elles sont présentées à nous d’une manière qui travaille avec au lieu de contre elles.

Plus d’infos et remerciements

Andrew Hetherington est actuaire et passionné des données travaillant à Londres, Royaume-Uni. All views are Andrew’s own and not those of his employer. Connectez avec lui sur LinkedIn.

Photo d’arbre : Todd Quackenbush sur Unsplash.

ETE 3: Reconstruction, analysis and visualization of phylogenomic data.

Jaime Huerta-Cepas, Francois Serra and Peer Bork.

Mol Biol Evol 2016; doi: 10.1093/molbev/msw046