Yeow Marc Plantevit

Wei Choong

Anne Laurent

Dominique Laurent

Maguelonne Teisseire

Maguelonne Teisseire Motifs

Y W Choong

Motifs Séquentiels Multidimensionnels Etoilés

Keywords: Fouille de données, motifs séquentiels, bases de données multidimensionnelles

la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Résumé

L'extraction de motifs séquentiels est un domaine de la fouille de données permettant de rechercher des corrélations fréquentes entre des valeurs en prenant en compte leur chronologie d'apparition. Dans le contexte du panier de la ménagère, ce type de méthodes permet par exemple l'extraction de règles de la forme (T V, DV D)(magneto numerique) , indiquant qu'un nombre suffisamment important (au sens du support) de clients ont acheté d'abord un téléviseur et un lecteur DVD puis un magnétoscope numérique. Si de nombreux travaux permettent l'extraction de tels motifs, il n'en reste pas moins que ces motifs sont parfois très pauvres par rapport aux bases de données qu'ils décrivent. En effet, il n'existe pas à l'heure actuelle de méthode permettant de mettre en exergue des corrélations entre valeurs de différents attributs, par exemple pour découvrir des règles de la forme {(surf, N Y ), (housse, N Y )}, {(combi, SF )} indi-quant qu'un nombre important de personnes ont acheté leur planche de surf et la housse à New York avant de se rendre à San Francisco où ils ont acheté une combinaison. Si la littérature recense des contributions liées aux motifs séquentiels multidimensionnels proposées par l'équipe de Jiawei Han, celles-ci ne permettent pas de combiner plusieurs attributs au sein des motifs extraits. Dans cet article, nous montrons donc les limites des approches existantes et proposons une approche complète d'extraction de motifs multidimensionnels multi-attributs. Nous définissons les concepts associés à ces motifs et décrivons les algorithmes permettant leur extraction. Ces algorithmes sont validés par des expérimentations montrant l'intérêt de notre approche.

Introduction

Les motifs séquentiels sont apparus afin de permettre la découverte de règles intégrant la notion de temporalité et d'enchaînement d'événements. De telles règles seront par exemple de la forme : les clients qui ont acheté un téléviseur et un lecteur DVD achètent plus tard un magnétoscope numérique.

De nombreux travaux ont traité cette problématique. Les recherches se sont notamment intéressées à l'extraction efficace des motifs face à de gros volumes de données [START_REF] Srikant | Mining sequential patterns : Generalizations and performance improvements[END_REF].

La pertinence des règles et leur découverte est fondée sur la notion de support qui, de même que pour les règles d'assocation, spécifie dans quelle proportion les données de la base contiennent les données du motif.

Cependant, les propositions existantes ne travaillent que sur une seule dimension d'analyse, nommée produit dans les approches de type étude du panier de la ménagère. Ainsi, même si cette dimension peut être modifiée dans des applications des motifs séquentiels à d'autres domaines que le panier de la ménagère (par exemple dans le cadre de l'étude des comportements d'internautes [START_REF] Tanasa | Mesures de l'internet, chapter Fouille de données appliquées au logs web : état de l'art sur le Web Usage Mining[END_REF]), il n'en reste pas moins qu'il n'est possible d'analyser qu'une seule dimension à la fois.

Ainsi, il n'existe pas à l'heure actuelle de méthode permettant de mettre en exergue des corrélations entre valeurs de différents attributs, par exemple pour découvrir des règles de la forme {(surf, N Y, 1), (housse, N Y, 1)}, {(combi, SF, 1)} indiquant qu'un nombre suffisant (au sens du support) de personnes ont acheté leur planche de surf et la housse à New York avant de se rendre à San Francisco où ils ont acheté une combinaison.

Si la littérature recense des contributions liées aux motifs séquentiels multidimensionnels proposées par l'équipe de Jiawei Han [PHP + 01], cellesci ne permettent pas de combiner plusieurs attributs au sein des motifs extraits pour ce qui est de la partie séquentielle, les multiples attributs n'apparaissant que pour restreindre le cadre dans lequel on trouve la séquence fréquente.

Dans cet article, nous montrons donc les limites des approches existantes et proposons une approche complète d'extraction de motifs multidimensionnels multi-attributs. Nous définissons les concepts associés et présentons les algorithmes permettant leur extraction. Des expérimentations montrent l'intérêt de notre approche. Plusieurs types de motifs séquentiels multidimensionnels sont définis, selon que toutes les dimensions d'analyse sont spécifiées ou non, et selon que la valeur de mesure est spécifiée ou non. On parle de motif multidimensionnel α-étoilé quand une dimension d'analyse au moins n'est pas spécifiée. Par exemple, le motif {(surf, N Y, 1), (housse, N Y, 1)}, {(combi, * , 1)} indique que les personnes ayant acheté une planche de surf et une housse à New York achètent par la suite une combinaison (sans précision de la ville). On parle de motif multidimensionnel µ-étoilé quand la valeur de mesure n'est pas spécifiée. Par exemple, le motif

{(lecteur dvd, F N AC, )}, {(DV D, supermarche, )}
indique que les personnes achetant un ou plusieurs lecteur(s) DVD à la FNAC achètent ensuite un ou plusieurs DVD dans un supermarché (sans précision de la quantité).

Cet article est organisé de la manière suivante. La section 2 introduit brièvement les concepts liés aux motifs séquentiels, présente les travaux de la littérature traitant le cas où plusieurs attributs sont considérés et introduit les principaux concepts liés aux bases de données multidimensionnelles. La section 3 introduit notre contribution, M 2 SP, pour la définition de motifs séquentiels multidimensionnels. La section 4 présente l'extension de cette proposition à la prise en compte de valeurs joker sur les dimensions d'analyse et sur la mesure. La section 5 présente les algorithmes associés à notre proposition. La section 6 présente les premières expérimentations menées qui confirment l'intérêt de notre approche. Enfin, la section 7 conclut et présente les principales perspectives associées à ce travail.

Dans cette section, nous présentons les principes des motifs séquentiels ainsi que les approches de la littérature ayant traité le cas où plusieurs attributs sont considérés. Dans un dernier temps, nous présentons brièvement les notations sur lesquelles nous nous appuyons dans le contexte des bases de données multidimensionnelles.

Motifs séquentiels

Nous présentons ici très brièvement les concepts fondamentaux liés aux motifs séquentiels. Le lecteur désirant plus de détails se référera à [START_REF] Masseglia | Recherche des motifs séquentiels[END_REF]. Les bases de données sur lesquelles s'appuie la recherche de motifs séquentiels doivent comporter trois données liées à la problématique du panier de la ménagère : la première représente un identifiant (souvent appelé client), la deuxième représente une liste de valeurs (souvent appelé produits), la troisième représente la date à laquelle ce client a acheté cet ensemble de produits. On appelle item une valeur prise par l'attribut produit. Par exemple, DV D ou encore magnetoscope sont deux items possibles. On appelle itemset un ensemble d'items. Par exemple (DV D, magnetoscope) est un itemset. La base de données est donc composée d'itemsets identifiés par une date et un identifiant de client. On appelle séquence une liste ordonnée (selon la date) d'itemsets. La base de données peut donc être vue comme un ensemble de séquences identifiées par le client. On appelle motif séquentiel une séquence qu'un nombre suffisant (au sens du support) de clients partagent au sein de la base de données.

Étant donnée une valeur minimale de support (spécifiée par l'utilisateur), on dit qu'un motif séquentiel est fréquent si un nombre de clients supérieur au seuil minimal de support ont réalisé cette séquence d'achats.

L'enjeu des méthodes de fouille de données est donc l'extraction la plus efficace possible des motifs féquents. Pour cela, plusieurs techniques existent dont PSP [START_REF] Masseglia | Algorithmes et applications pour l'extraction de motifs séquentiels dans le domaine de la fouille de données : de l'incrémental au temps réel[END_REF]

Motifs séquentiels multidimensionnels

Nous présentons ici les trois approches de la littérature ayant abordé la problématique des motifs séquentiels multidimensionnels. et montrons en quoi elles sont limitées par rapport à notre proposition.

Approche de Pinto et al.

Dans [PHP + 01] les auteurs sont les tout premiers à rechercher des motifs séquentiels multidimensionnels. Ainsi, les achats ne sont plus décrits en fonction des seuls date et identifiant du client, mais en fonction d'un ensemble de dimension telles que Type de consommateur, Ville, Age, comme illustré par le tableau 1. L'approche proposée repose sur la définition de séquence multidimensionnelle selon le schéma A 1 , ..., A m , S où les A i correspondent aux dimensions sur lesquelles les données sont décrites et S représente les séquences des achats réalisés par le client ordonnés selon le temps. Une séquence multidimensionnelle possible est donc du type (id 1 ,(a 1 , ..., a m ),s) avec a i ∈ A i ∪ { * }.

Exemple 1 Le tableau 1 donne un exemple de base de données intégrant des séquences d'achat de produit (dans la dernière colonne) décrites selon plusieurs dimensions. La première colonne correspond à l'identifiant de chaque client (cid). La deuxième colonne correspond au groupe de consommateur (Customer Group) associé. alliant différents patterns multidimensionnels. Ceux-ci ne peuvent en effet pas être découverts dans la proposition précédente.

Approche de Yu et Chen

Dans [START_REF] Yu | Mining sequential patterns from multidimensional sequence data[END_REF], les auteurs tentent d'étendre la recherche de motifs séquentiels au contexte des bases de données décrivant les informations au moyen de plusieurs attributs.

Cependant cette approche est restreinte au cas particulier où les dimensions étudiées entretiennent entre elles un très fort lien. En effet, ces dimensions sont organisées en hiérarchie. Ainsi, dans l'exemple pris par les auteurs, les différentes dimensions sont liées au comportement d'internautes dont les visites de pages sont organisées en transactions (dimension 1) elles-mêmes organisées en sessions (dimension 2) elles-mêmes organisées en jours (dimension 3). Ces différents dimensions sont imbriquées au sein des motifs trouvés et il est impossible de retrouver les valeurs fréquentes le long de ces dimensions, celles-ci n'intervenant que pour organiser le temps de manière hiérarchique. De même que dans l'approche proposée par [PHP + 01], les séquences ne concernent qu'une seule dimension (les pages internet dans ce cas).

Approche de De Amo et al.

L'approche de [START_REF] De Amo | An aprioribased approach for first-order temporal pattern mining[END_REF] est basée sur la logique temporelle du premier ordre. Cette proposition est proche de la notre mais présente des limites que nous étendons ici. Notre proposition est une généralisation de [START_REF] De Amo | An aprioribased approach for first-order temporal pattern mining[END_REF] puisque dans notre approche : (i) la notion de groupe n'est pas codée dans la base mais déterminée par l'utilisateur et (ii) plusieurs attributs peuvent apparaître dans les séquences. Concernant ce dernier point, les auteurs mentionnent la possibilité de traiter plusieurs attributs, cependant le formalisme mis en place n'est pas étendu de manière complète au cas multi-attributs. De plus, dans [START_REF] De Amo | An aprioribased approach for first-order temporal pattern mining[END_REF] les auteurs construisent leurs séquences candidates à partir d'une opération de jointure sur les séquences, contrairement à notre approche qui s'appuie sur les travaux déjà validés de construction tels que [START_REF] Masseglia | Algorithmes et applications pour l'extraction de motifs séquentiels dans le domaine de la fouille de données : de l'incrémental au temps réel[END_REF].

Bases de données multidimensionnelles

Il n'existe pas à l'heure actuelle de consensus concernant les modèles de bases de données multidimensionnelles [START_REF] Chaudhuri | An overview of data warehousing and olap technology[END_REF][START_REF] Marcel | Manipulations de Données Multidimensionnelle et Langages de Règles[END_REF]. Dans cet article, nous adoptons un point de vue relationnel au niveau du stockage des cubes (ROLAP). L'ensemble des notations utilisées dans cet article sont reprises dans le tableau 6. Définition 2 (Cellule) On appelle cellule d'un cube à n dimensions D 1 ,. . .,D n , un n-uplet de la forme :

(d 1 , • • • , d n ), µ où : -∀i ∈ [1 • • • n], d i ∈ Dom(D i ) -µ ∈ Dom(M ) Définition 3 (Projection) Soit cell = (d 1 , • • • , d n ), µ une cellule. On note cell.D i = d i la restriction de cell sur la dimension D i .
Exemple 2 Si l'on considère l'hypercube du tableau 2 donné sous forme tabulaire, une cellule de cet hypercube sera par exemple :

(1, Educ, Chicago, A, clou), 50 . Dans cette représentation, les cellules pour lesquelles la valeur de mesure est nulle sont omises. Ainsi, la cellule (1, Educ, M iami, A, clou), N U LL appartient au cube mais n'est pas représentée.

Définition 4 (Sous-Cube) Soit C un cube à n dimensions D = {D 1 , • • • , D n }, un sous- cube SC de C défini sur les k dimensions {D j 1 , • • • , D j k } ⊆ D est un n-uplet d j 1 , • • • , d j k . Le sous-cube SC correspond à l'ensemble des cellules telles que : c = (c 1 , • • • , c n ), µ avec µ ∈ Dom(M ) et ∀j ∈ [j 1 , • • • , j k ] c j = d j .
Un sous-cube est défini à partir de dimensions sur lesquelles les valeurs sont fixées. Un cube peut donc être partitionné en un ensemble de souscubes le long d'un ensemble de dimensions, tel que l'opération split du modèle multidimensionnel le réalise [START_REF] Chaudhuri | An overview of data warehousing and olap technology[END_REF][START_REF] Marcel | Manipulations de Données Multidimensionnelle et Langages de Règles[END_REF].

Exemple 3 Soit le cube C décrit par le tableau 2. Si l'on considère les dimensions Cust-Grp et City, il est possible de diviser ce cube en trois souscubes définis par les n-uplets Educ, Chicago (cf tableau 3), Educ, LosAngeles (cf tableau 4) et Reti., M iami (cf tableau 5). Ces trois sous-cubes définissent une partition de C.

Définition 5 (Opérateur de sélection slice) Soit θ un prédicat de la forme D i op val où op est un opérateur de comparaison. On note σ θ (C) le cube résultant d'une sélection sur les valeurs de dimension (slice) du cube C. Tab. 5 -sous-cube de C défini par Reti., M iami Par exemple, on peut sélectionner les données du cube correspondant à la date 1 en calculant σ Date=1 . Ceci revient à ne conserver que les cellules correspondant aux cinq premières lignes du tableau 2. Les autres cellules voient leur valeur µ mise à NULL, ce qui revient à les éliminer de la mémoire. On notera en effet que du point de vue de l'implémentation, seules les cellules dont la valeur de mesure est non nulle seront conservées pour être traitées, ce qui réduit les temps de parcours de la base de données.

Pour toute cellule cell = (d 1 , • • • , d n ), µ de C, on a cell dans σ θ (C) si la condition θ est satisfaite et cell = (d 1 , • • • , d n ), N U LL dans σ θ (C) sinon.

M 2 SP

Dans cette section, nous présentons une nouvelle définition des motifs séquentiels multidimensionnels, nommée M 2 SP (Mining Multidimensional Sequential Patterns).

Données manipulées

Dans le cadre de ce travail, on suppose que parmi toutes les dimensions définissant un cube, il existe une dimension D t (dimension temporelle) dont le domaine est totalement ordonné. -

D F = ∅ -D R = {Cust-Grp, City } -D A = {Age, P roduct} -D t = {Date}
Dans le cadre de l'extraction des motifs séquentiels multidimensionnels, l'ensemble D R permet d'identifier les sous-cubes par rapport auxquels le support sera calculé. Pour cette raison, cet ensemble est nommé référence. On note que dans le cadre des motifs séquentiels classiques et des extensions [PHP + 01] et [START_REF] De Amo | An aprioribased approach for first-order temporal pattern mining[END_REF], cet ensemble est réduit à un seul attribut (identifiant du client cid du tableau 1 ou identifiant IdG dans [START_REF] De Amo | An aprioribased approach for first-order temporal pattern mining[END_REF]). Dans nos calculs, le support d'une séquence sera ainsi calculé comme étant la proportion de souscubes où cette séquence peut être retrouvée.

L'ensemble D A décrit les axes d'analyse, c'est-àdire l'ensemble des dimensions apparaissant explicitement dans les motifs séquentiels multidimensionnels extraits. Dans le cadre des motifs classiques, seule une seule dimension apparaît, correspondant aux produits achetés (ou encore aux pages internet visitées). Dans notre approche, cette dimension est étendue à la prise en compte d'un ensemble de dimensions.

L'ensemble F décrit les axes ignorés, c'est-àdire ceux qui ne servent ni à définir la date, ni à identifier un sous-cube, ni à définir le motif lui-même.

Item, itemset et séquence multidimensionnels

Définition 7 (Item multidimensionnel) Un item multidimensionnel e défini sur les dimensions

D A = D i 1 , . . . , D im et la mesure M est un n-uplet de la forme : e = (d i 1 , • • • , d im , µ) tel que : -∀k, k ∈ [i 1 , • • • i m ], d i k ∈ Dom(D i k ) -µ ∈ dom(M ) On note e = a, µ .
i = {(d i1 1 , • • • , d im 1 , µ 1 ), • • • , (d i1 p , • • • , d im p , µ p )}. On note i = {e 1 , • • • , e p }.
= {(d i1 1 , • • • , d im 1 , µ 1 ), • • • , (d i1 p , • • • , d im p , µ p )}, • • • {(d i1 1 , • • • , d im 1 , µ 1 ), • • • , (d i1 p , • • • , d im p , µ p )} On note ς = i 1 , • • • , i l . {(A, clou, 50), (B, pneu, 2)} {(B, rustine, 10)} est une séquence. Définition 10 (Inclusion de séquence) Une séquence multidimensionnelle ς = a 1 , • • • , a l est appelée sous-séquence d'une séquence ς = b 1 , • • • , b l s'il existe des entiers 1 ≤ j 1 ≤ j 2 ≤ • • • ≤ j l ≤ l tels que a 1 ⊆ b j 1 , a 2 ⊆ b j 2 , • • • , a l ⊆ b j l .
On dit aussi que la séquence ς est une sur-séquence de ς.

Exemple 5 Soient les séquences multidimensionnelles ς = {(A, clou, 50)}, {(B, rustine, 10)} et ς = {(A, clou, 50), (B, pneu, 2)}, {(B, rustine, 10)} . ς est une sous-séquence de ς .

Support

Calculer le support d'une séquence revient à compter le nombre de sous-cubes de la base qui la supportent, de même qu'il revient à compter le nombre de clients ayant suivi la séquence d'achat dans le contexte du panier de la ménagère. Dans notre approche, un sous-cube supporte une séquence s'il est possible de trouver un ensemble de cellules qui la vérifient. Il s'agit, pour chaque itemset de la séquence, de trouver une date de la dimension D t à laquelle tous les items sont présents. Tous les itemsets doivent être alors trouvés à des dates de D t respectant l'ordre de la liste des itemsets, d'où la définition ci-dessous.

Définition 11 Un cube C supporte une séquence i 1 , • • • , i l si -∀j = 1 • • • l, ∃d j ∈ Dom(D t ), ∀e = a, µ e ∈ i j , ∃cell = (f, a, r, d j ), µ ∈ C et µ e = µ -d 1 < d 2 < • • • < d l
support(ς) = |{SC∈C C,D R t.q. SC supporte ς}| |C C,D R | Définition 13 (Séquence fréquente) Soit suppmin ∈ [0, 1],

Valeurs joker

Nous définissons ici d'une part les raisons pour lesquelles une valeur joker peut être intéressante dans le cadre de la recherche de motifs séquentiels multidimensionnels et d'autre part les moyens mis en oeuvre pour la définition d'une telle valeur.

Motifs séquentiels α-étoilés

Dans les définitions précédentes, un item ne peut être trouvé que s'il existe une combinaison de valeurs de domaines de D A se retrouvant fréquemment dans les données. Or il peut par exemple arriver que ni (A, rustine), µ ni (B, rustine), µ ni (C, rustine), µ ne soit fréquent alors que la valeur rustine est fréquemment associée à la valeur µ. Pour cette raison, nous introduisons une valeur joker symbolisée par * . Cette valeur signifie que l'on ne tient pas compte de la valeur sur la dimension d'analyse. Dans le cas précédent, on notera ( * , rustine), µ . Un tel item est dit α-étoilé.

Définition 14 (Item α-étoilé) Soit a [d i /δ] la substitution de la valeur d i par δ dans a. Un item multidimensionnel α-étoilé est de la forme e = a, µ tel que :

1. ∀d i ∈ a, d i ∈ Dom(D i ) ∪ { * } 2. ∃d i ∈ a t.q. d i = * 3. ∀d i = * , δ ∈ Dom(D i j ) t.q. e = a [d i /δ] , µ est fréquent
Ainsi, un item α-étoilé contient au moins une dimension d'analyse spécifiée (non étoilée), et ne contient une étoile que si celle-ci ne peut pas être remplacée par une valeur du domaine tout en restant un item fréquent. On note qu'un item fréquent est une séquence fréquente composée d'un seul itemset lui-même composé d'un seul item.

Une séquence α-étoilée est une séquence dont au moins un item est α-étoilé. Un sous-cube supporte une telle séquence si on peut trouver un ensemble d'ensemble de cellules vérifiant chacun des itemsets dans les contraintes de temps imposées par l'ordre des itemsets.

Définition 15 (Support de séquence α-étoilée) Un cube de données C supporte une séquence α-

étoilée ς = i 1 , • • • , i l si : -∀j = 1 • • • l, ∃d j ∈ Dom(D t ), ∀e = (a i 1 , • • • , a im ), µ e ∈ i j , ∃cell = (f, (x i 1 , • • • , x im ), r, d j ), µ ∈ C avec a i = x i ou a i = * -d 1 < d 2 < • • • < d l .
Le support de ς est la proportion de souscubes de C supportant ς :

support(ς) = |{SC∈C C,D R t.q. SC supporte ς}| |C C,D R |

Motifs séquentiels µ-étoilés

S'il peut arriver qu'une combinaison de dimensions ne trouve pas d'instanciation fréquente, ce cas de figure est d'autant plus vrai dans le cadre de la mesure. En effet, cette dimension particulière du cube est le plus souvent numérique et prend un nombre de valeurs très important, ce qui rend très improbable la présence de valeurs fréquentes. Pour cette raison, nous définissons, de manière similaire au caractère joker sur les dimensions d'analyse, un caractère joker sur la valeur de mesure, noté . Un item contenant ce caractère est dit µ-étoilé.

Définition 16 (Item µ-étoilé) Un item multidimensionnel µ-étoilé est de la forme : e = a, µ où µ ∈ Dom(M ) ∪ Définition 17 (Support de séquence µ-étoilée) Un cube de données C supporte une séquence µ-

étoilée ς = i 1 , • • • , i l si : ∀j = 1 • • • l, ∃d j ∈ Dom(D t ), ∀e = a, µ e ∈ i j , ∃cell = (f, a), µ ∈ C avec µ e = ou µ e = µ.
Le support de ς est la proportion de souscubes de C supportant ς :

support(ς) = |{SC∈C C,D R t.q. SC supporte ς}| |C C,D R |
Remarque 2 La présence du symbole revient en fait à ne considérer que la restriction sur D A sans se soucier de la valeur de µ (seule la présence d'une cellule non nulle suffit).

Exemple 7 Sur les trois sous-cubes définis à partir du cube du tableau 2 et de D R , seul un vérifie l'item i 1 = clou, 50 , alors que les trois vérifient l'item i 2 = clou, . On a support(i 1 ) = 1 3 et support(i 2 ) = 1.

Algorithmes

Dans cette section, nous définissons tout d'abord les algorithmes permettant d'extraire les items multidimensionnels fréquents puis les algorithmes mis en oeuvre pour extraire l'ensemble des séquences fréquentes.

Génération des 1-fréquents

Les items multidimensionnels fréquents sont la base de l'extraction des motifs séquentiels. Ils représentent les fréquents de taille 1 puisqu'ils correspondent à des séquences composées d'un seul item (contenu dans un seul itemset).

Dans le cas où l'on cherche des items non étoilés, un parcours sur la base permet de recencer les items et leur support (donc les items fréquents), de même que dans le cas classique mono-attribut. Dans le cas où les items peuvent être étoilés, il s'agit de rechercher les items maximaux (au sens du nombre de dimensions spécifiées). Afin de limiter le calcul du support aux items dont la probabilité d'être fréquents est non nulle, nous adoptons une méthode de génération par niveau. Cette recherche s'effectue au sein d'un treillis dont la bordure sera retenue pour constituer l'ensemble des items fréquents maximaux. Pour ce faire, le premier niveau considère les items multidimensionnels pour lesquels une seule dimension d'analyse est spécifiée, les autres dimensions étant mises à la valeur * . Les items multidimensionnels fréquents sont alors joints entre eux pour obtenir la liste des items candidats pour lesquels deux dimensions d'analyse spécifiées dont on ne retient que les fréquents. Cette procédure est itérée tant que de nouveaux items fréquents sont trouvés.

L'opération de jointure entre deux items fréquents suppose que les items soient compatibles, c'est-à-dire qu'ils partagent un nombre suffisant de valeurs de dimensions d'analyse (voir définition 19). On note que cette exploration est très proche de l'exploration du treillis des cuboïdes dans le cadre des iceberg cubes [START_REF] Beyer | Bottom-up computation of sparse and iceberg cube[END_REF][START_REF] Casali | Cube lattices : A framework for multidimensional data mining[END_REF]. L'amélioration de cette exploration dans le cadre de notre proposition s'effectuera en relation avec ces approches.

La figure 2 met en évidence le fait que ignorer une dimension en la mettant dans D F n'est pas équivalent à instancier cette dimension par la valeur joker. En effet, les items multidimensionnels fréquents extraits ne sont pas les même. Par exemple si D 2 ∈ D F , nous ne pouvons pas extraire l'item (a , b, c).

= (d 1 , • • • , d n ) et e 2 = (d 1 , • • • , d n ) où d i et d i ∈ dom(D i ) ∪ { * }. On dit que e 1 et e 2 sont -compatibles si -e 1 et e 2 sont distincts -∃∆ = {D i 1 , . . . , D i n-2 } ⊂ {D 1 , . . . , D n } t.q. d i 1 = d i 1 = * et d i 2 = d i 2 = * . . . et d i n-2 = d i n-2 = * -Pour {D i n-1 , D in } = {D 1 , . . . , D n }\∆, on a d i n-1 = * et d i n-1 = * et d in = * et d in = *
Pour être -compatibles, deux items multidimensionnels définis sur n dimensions doivent donc partager n -2 valeurs de dimension. Par exemple, (Chicago, A, * ) et ( * , A, rustine) sont deux items définis sur 3 dimensions d'analyse et partagent 3 -2 = 1 valeur sur la dimension Age. Ils sont donccompatibles. En revanche, les items (Chicago, B, * ) et (N Y, A, * ) ne sont pas -compatibles. Notation On note F i 1 l'ensemble des 1-fréquents dont i dimensions sont spécifiées (différentes de * ).

Définition 19 (Jointure) Soient 2 items multi- dimensionnels -compatibles e 1 = (d 1 , • • • , d n ) et e 2 = (d 1 , • • • , d n ). On définit e 1 e 2 = (v 1 , • • • , v n ) avec : -v i = d i si d i = d i -v i = d i si d i = * -v i = d i si d i = * Soit deux
L'ensemble Cand 1 1 des items candidats pour lesquels une seule dimension est fixée est calculé grâce à l'algorithme 1.

Données : C, D A , M, µopt Résultat : E 1 début Cand 1 ←-{}; si µopt alors µ ←-; D ← D A ; sinon /*la mesure est considérée comme une dimension ordinaire */ D ←-D A ∪ {M }; pour chaque dim ∈ D faire pour chaque v ∈ dom(dim) faire si µopt alors e ←-(d 1 , • • • , d D.length ), µ ; sinon e ←- (d 1 , • • • , d D.length-1 ), d D.length ; pour chaque i ≤ D.length faire si dim = i alors d i = v; sinon d i = * ; Cand 1 ←-Cand 1 ∪ {e};
retourner Cand 1 fin Algorithme 1: génération de Cand 1 1 Les fréquents de taille 1 sont alors obtenus en fonction des candidats de taille 1. De manière générale, les candidats de taille i sont obtenus en considérant les fréquents de taille i-1 (cf. algorithme 2) dont on extrait les fréquents de taille i :

F 1 1 = {f ∈ Cand 1 1 , support(f ) ≥ suppmin} F i 1 = f requents(F i-1 1 F i-1
1 ) À l'issue de cette génération, il est important de s'interroger sur les items susceptibles d'être examinés. Ainsi, l'utilisateur devra spécifier s'il accepte ou non les items α-et µ-étoilés. Si tel n'est pas le cas, l'utilisateur pourra se trouver plus facilement dans le cas où aucun item multidimensionnel fréquent n'a été identifié, les caractères joker * et favorisant la présence d'items fréquents.

Génération de candidats

Une fois les 1-fréquents extraits, les k-candidats (k ≥ 2) sont générés et testés afin de savoir s'ils sont fréquents. Cette opération est itérée tant que des k-candidats fréquents sont trouvés. Nous nous baserons par exemple sur l'algorithme de [START_REF] Masseglia | Algorithmes et applications pour l'extraction de motifs séquentiels dans le domaine de la fouille de données : de l'incrémental au temps réel[END_REF] en incluant les modifications liées aux jokers sur les valeurs des dimensions (motifs α-étoilés) et sur la valeur de mesure (motifs µ-étoilés).

Calcul du support des séquences

Nous pouvons maintenant définir un algorithme qui calcule le support d'une séquence ς au sein d'un cube de données C, suivant les dimensions de référence et d'analyse désirés.

Les dimensions de référence permettent d'énumérer tous les sous-cubes de C susceptibles de supporter ς. Cette énumération est indispensable pour calculer le ratio des sous-cubes qui supportent ς, et donc pour définir si la séquence est fréquente ou non.

L'algorithme 3 vérifie pour chaque sous-cube de C si la séquence est supportée ou non. Si la séquence est supportée, alors le support est incrémenté. L'algorithme retourne ensuite le ratio des cubes supportant ς. L'algorithme 4 permet de vérifier si le sous-cube SC supporte la séquence ς. Pour cela, cet algorithme cherche à instancier itemset par itemset en conjugant récursivité et ancrage. L'ancrage correspond à une cellule du cube C d'où il est espéré que la séquence pourra être instanciée. Cette cellule correspond donc à une date à laquelle le premier item du premier itemset de la séquence est trouvé. À partir de cette cellule, seules les cellules pertinentes sont retenues, c'est-à-dire celles qui partagent la même date. On ne retient donc que les cellules partageant la même date. Si le sous-cube résultant de l'ancrage supporte l'itemset alors on appelle la fonction sur les autres itemsets de ς. Cet appel est effectué en réduisant l'espace de recherche aux seules cellules dont la date est supérieure à la date de l'ancrage précédent, puisque l'on passe à l'itemset suivant, donc à une date ultérieure. Si l'ancrage échoue, on continue la recherche du premier itemset en tentant d'autres ancrages. L'appel récursif s'arrête dès que la séquence placée en paramètre d'entrée est vide. Une telle propriété signifie en effet que tous les itemsets de la séquence ont été trouvés. On retourne donc la valeur vrai. La valeur f aux est retournée si aucun ancrage n'a réussi et si tout le cube a été parcouru sans succès.

Données : C, D R , D A , D t , F 1 , * αopt Résultat : l'ensemble des items multidimensionnels fréquents début i ←-1; F m 1 ←-∅; tant que F i 1 = ∅ ∧ i ≤ m faire Cand i+1 1 ←-∅; pour chaque couple (e 1 , e 2 ) ∈ F i 1 2 tel que e 1 , e 2 -compatibles faire Cand i+1 1 ←-Cand i+1 1 ∪ {e 1 e 2 }; F i+1 1 ←-{f ∈ Cand i+1 1 , support(f ) ≥ suppmin}; i ←-i + 1 ; si *αopt

Complexité

Afin de faciliter l'étude de complexité des algorithmes, nous posons les notations suivantes :

-

Expérimentations

Nous avons implémenté les algorithmes présents dans ce rapport afin de réaliser un outil d'extraction de motifs séquentiels multidimensionnels étoilés ( * , ) ou non. Des expérimentations sont menées sur des bases de données synthétiques représentées sous forme tabulaire (que les cellules non vides présentes). Par défaut le jeu de données utilisé contient 12 000 n-uplets, 15 dimensions d'analyse de cardinalité moyenne 20 et une dimension de mesure dont la cardinalité est 15.

Ces premières expérimentations comparent les résultats obtenus en terme de temps de calcul et de nombre de fréquents trouvés en fonction du nombre de dimensions prises en compte, du seuil de support considéré, de la taille de la base de données. Nous établissons également une comparaison entre notre approche et l'approche de [PHP + 01] en fonction du nombre motifs extraits par rapport à la taille de la base ou le nombre de dimensions d'analyse.

Ces expérimentations sont menées sans prise en compte de valeurs jokers (M 2 SP ), avec prise en compte de valeurs jokers sur les dimensions d'analyse (M 2 SP -alpha), avec prise en compte de valeurs jokers sur la mesure (M 2 SP -mu) et avec prise en compte de valeurs jokers à la fois sur les dimensions d'analyse et sur la mesure (M 2 SP -alpha-mu).

Les figures 3 et 4 le nombre de fréquents extraits ainsi que le temps de calcul en fonction du support considéré. Le fait de ne pas accepter la présence de la valeur joker sur les dimensions d'analyse représente une contrainte importante. En effet, cela est équivalent à rechercher toutes les combinaison de valeurs de domaines de D A se retrouvant 3). Nous considérerons ainsi par la suite les méthodes M 2 SP -alpha et M 2 SP -alpha-mu qui autorisent la présence de la valeur joker sur les dimensions d'analyse. On note que la prise en compte de la valeur joker sur la mesure permet d'augmenter le nombre de fréquents trouvés, la contrainte sur la valeur de mesure étant alors relachée.

La figure 5 montre le nombre de motifs séquentiels multidimensionnels extraits ainsi que le temps de calcul en fonction de la taille de la base. Le nombre de fréquents extraits augmente de façon quasi linéaire à partir d'une certaine taille (15 000 nuplets). Le temps d'éxécution évolue de façon semblable. Ces courbes nous permettent de souligner la robustesse de notre approche ainsi que son caractère « passage à l'échelle ». Nous posons les définitions formelles soustendant ces propositions originales. Les algorithmes associés à notre approche sont présentés et validés par des expérimentations effectuées sur des jeux de données synthétiques. Ces expérimentations montrent en particulier l'intérêt de l'introduction des valeurs joker * sur les dimensions d'analyse et sur la mesure pour traiter les cas où aucun fréquent n'est trouvé.

Ce travail ouvre de nombreuses perspectives, notamment en ce qui concerne la gestion des contraintes de temps pour la définition de motifs multidimensionnels généralisés, ainsi que sur l'intégration d'approximation dans la mesure. Cette dernière approche permettrait en effet de ne pas perdre totalement la connaissance de la valeur de mesure (ce qui est le cas avec ) tout en conservant une chance de trouver des motifs fréquents face au grand nombre de valeurs de mesure possibles dans les bases de données issues du monde réél. Ainsi, nous pourrons construire des règles de la forme Les personnes ayant acheté un lecteur DVD à la FNAC achètent par la suite environ 3 DVDs dans un supermarché. De plus, outre ses applications immédiates au contexte du panier de la ménagère, cette proposition sera utilisée au sein de bases de données multidimensionnelles MOLAP afin de rechercher des enchaînements fréquents de blocs de cellules au sein d'une représentation cubique des données. Des recherches similaires ont été menées dans le cadre de règles d'association [START_REF] Choong | Summarizing multidimensional databases using fuzzy rules[END_REF], il s'agit de les étendre à la prise en compte de motifs séquentiels. Enfin, les hiérarchies, intérêt majeur du modèle multidimensionnel, seront traitées afin de rechercher des motifs séquentiels multidimensionnels à différents niveaux de granularité.

Tab. 1 -

 1 Exemple de base de données incluant plusieurs dimensions d'analyse Nous considérons les bases de données comme étant organisées en cubes eux-mêmes composés de cellules. Dans une représentation relationnelle, chaque cellule correspond à un n-uplet de la base. Nous considérons D = {D 1 , • • • , D n } un ensemble de dimensions définies sur leurs domaines actifs 1 respectifs Dom(D 1 ), . . . , Dom(D n ), et une mesure M (correspondant le plus souvent à une valuation numérique) définie sur le domaine Dom(M ). Le domaine de la mesure inclut la valeur nulle. Définition 1 (HyperCube) Un hypercube (ou simplement cube) de données défini sur les dimensions D 1 , . . ., D n est un n-uplet Dom(D 1 ), . . . , Dom(D n ), Dom(M ), C où C est une application C : Dom(D 1 ) × . . . × Dom(D n ) → Dom(M ). Par abus de langage, on notera C un tel cube.

Définition 6 (

 6 Partition des dimensions) Pour tout cube défini sur les dimensions D, on considère une partition de D en quatre ensembles notés respectivement : -D t pour la ou les dimensions temporelles -D A pour les dimensions dites d'analyse -D R pour les dimensions dites de référence -D F pour les dimensions ignorées. Il en découle que chaque cellule cell = (d 1 , • • • , d n ), µ d'un cube peut être notée cell = (f, r, a, t), µ avec f la restriction sur D F de cell, r la restriction sur D R de cell, a la restriction sur D A de cell, t la restriction sur D t de cell. Exemple 4 Dans la suite de cet article, nous considérons la partition suivante des dimensions du cube de données C représenté sur le tableau 2 :

  (A, clou, 50), (B, pneu, 2), (B, rustine, 10) sont des items multidimensionnels.Définition 8 (Itemset multidimensionnel)On appelle itemset multidimensionnel i un ensemble non vide d'items multidimensionnels de la forme

  {(A, clou, 50), (B, pneu, 2)} et {(B, rustine, 10)} sont des itemsets multidimensionnels. Remarque 1 Il est important de remarquer que d'une part tous les items d'un itemset sont définis sur les mêmes dimensions (D A ), et que d'autre part les items multidimensionnels d'un même itemset sont deux à deux distincts. Définition 9 (Séquence multidimensionnelle) On appelle séquence multidimensionnelle une liste ordonnée non vide d'itemsets de la forme ς

  , clou, 50), (B, pneu, 2)}, {(B, pneu, 3)} puisque l'on retrouve bien la date 1 à laquelle l'itemset {(A, clou, 50), (B, pneu, 2)} est vérifié et la date 2 à laquelle l'itemset {(B, pneu)} est vérifié. Le support d'une séquence ς dans un cube C est la proportion de sous-cubes de C qui la supportent. On note C C,D R l'ensemble des sous-cubes du cube C définis à partir des dimensions D R (voir tableau 6). Formellement, on a : C C,D R = {r ∈ D i ∈D R Dom(D i ) t.q. ∃ (f, a, r, d j ), µ ∈ C et µ = N U LL}. Chaque sous-cube SC de C C,D R est donc défini comme un n-uplet de valeurs des domaines des dimensions de D R . Définition 12 (Support d'une séquence) Soit D R les dimensions de référence et C un cube partitionné en l'ensemble de souscubes C C,D R . Le support d'une séquence ς est :

Exemple 8

 8 La figure 1 illustre l'approche de spécification par niveau pour les dimensions d'analyse D 1 , D 2 , D 3 avec : dom(D 1 ) = {a, a } dom(D 2 ) = {b, b } dom(D 3 ) = {c} Dans une première étape, au niveau 1, les items où une dimension d'analyse est définie sont considérés. Ainsi, il s'agit de tester si les candidats (a, * , * ), (a , * , * ), . . ., ( * , * , c) sont fréquents. Imaginons que ( * , b , * ) ne soit pas fréquent. Les items candidats de niveau 2 sont alors construits en combinant les fréquents de taille 1. Ainsi, (a, b, * ), . . ., ( * , b, c) sont potentiellement fréquents. Il faut donc vérifier leur fréquence. Dans notre exemple, seuls les items non barrés sont trouvés fréquents. On construit alors les candidats de taille 3. Par exemple, l'item candidat (a, b, c) est construit en combinant (a, b, * ) et (a, * , c). Après test des fréquences, on trouve les items maximalement spécifiques (a , b, c), (a, b, * ) et (a, * , c). Un élagage est possible avant même la vérification sur la base. Par exemple, si ( * , b, c) n'avait pas été fréquent, il aurait été impossible que (a , b, c) le soit, même si (a , b, * ) et (a , * , c) l'étaient.

Fig. 1 -

 1 Fig. 1 -Les items multidimensionnels fréquents maximalement spécifiques avec D 2 ∈ D A

  ensembles d'items multidimensionnels de même taille n E et E , on note : E E = {e e t.q. (e, e ) ∈ E×E et e et e' sont -compatibles} Par exemple, la jointure des deux items (Chicago, A, * ) et ( * , A, rustine) résultera en (Chicago, A, rustine).

  alors /* on retourne les items avec le moins d'* possible */ retourner ({e item α étoilé}); sinon /*pas de 1-fréquent avec une * • • • on retourne les 1-frqts dont les m dim sont spécifiées */ retourner (F m 1 ) fin Algorithme 2: Génération et extraction des items fréquents

Fig. 3 -Fig. 4 -

 34 Fig. 3 -Le nombre de motifs extraits et le temps d'exécution en fonction du support sans valeur joker * sur les dimensions d'analyse

Fig. 5 -

 5 Fig. 5 -Le nombre de motifs extraits et le temps d'éxécution en fonction de la taille de la base

Fig. 7 -Fig. 8 -

 78 Fig. 7 -Comparaison avec [PHP + 01] en fonction du nombre de dimensions d'analyse

  ou encore PrefixSpan [PHMA + 04]. Ces techniques sont fondées sur des recherches par niveau a la APriori.

  le support minimal fixé par l'utilisateur. On dit qu'une séquence ς est fréquente si support(ς) ≥ suppmin.On cherche le support de la séquence ς = { (A, clou), 50 , (B, pneu), 2 } { (B, rustine), 10 } . Ce calcul nécessite le parcours de tous les sous-cubes définis par les dimensions de référence, c'est-à-dire les trois sous-cubes des tableaux 3, 4 et 5. 1. sous-cube défini par Educ, Chicago (cf tableau 3). Dans ce sous-cube, deux dates sont présentes. A la date 1, on a bien (A, clou), 50 et (B, pneu), 2 . Puis à la date 2 on retrouve bien (B, rustine), 10 . Donc ce sous-cube supporte la séquence ς. 2. sous-cube défini par Educ, LosAngeles (cf tableau 4). Ce sous-cube ne supporte pas l'item (B, pneu), 2 , et donc pas la séquence ς. 3. sous-cube défini par Reti., M iami (cf tableau 5). Ce sous-cube ne contient qu'une seule date, il ne peut donc pas supporter la séquence ς qui nécessite des sous-cubes contenant au moins deux dates différentes.On a donc : support(ς) = 1 3 ≥ suppmin. ς est une séquence fréquente.

	Exemple 6 On considère le cube du ta-
	bleau 2 avec D R	=	{Cust-Grp, City},
	D A	=	{Age, P roduct}, suppmin	=	1 5 .

  n C est le nombre de cellules du cube C m = |D A | est le nombre de dimensions des items multidimensionnels. Dans le pire des cas, la complexité de l'algorithme est de O(n C × m × log n C ). supportcount (algorithme 3) On appelle la fonction précedente pour tous les l sous-cubes C i de C suivant D R . Soit n max = max n C i . La complexité dans le pire des cas est donc O(l × n max × m × log n max ).

	supportCube (algorithme 4)
	-Le cube C étant ordonné par rapport	à
	la dimension D t , l'opération d'ancrage est
	réalisable en O(log n C ). En effet, il suffit de
	réaliser une recherche à l'aide d'un parcours
	dichotomique pour trouver toutes les cellules
	respectant une certaine condition sur la date.
	-Vérifier si une cellule supporte un item est
	réalisable en O(m). Il suffit de comparer les m
	dimensions de l'item avec celles de la cellule.

-

  Vérification si une séquence est supportée par un cube donné) fréquemment dans les données. C'est ainsi que nous du utiliser des supports très faibles afin d'obtenir des résultats significatifs pour M 2 SP et M 2 SP -µ (figure

	Fonction supportCube
	Données : ς, C, comptage
	Résultat : Booleen
	début
	/*initialisation */
	booleen ItemSetT rouvé ←-f aux
	sequence ←-ς
	itemset ←-sequence.f irst()
	item ←-itemset.f irst()
	/*condition d'arrêt de la recursivité */
	si ς = ∅ alors
	retourner (vrai)
	sinon
	itemset ←-sequence.f irst()
	/*on ne veut plus revoir les cellules de C' */
	C ←-σ date>cell.date (C)
	/* pas trouvé */
	retourner (faux)
	fin
	Algorithme 4: supportCube (

/*parcours du cube */ tant que cell ←-C.next = ∅ faire si supporte(cell, item, comptage) alors itemSuivant ←itemset.second() si itemSuivant = ∅ alors itemsetT rouvé ←vrai /*Recherche de tous les items de l'itemset */ sinon /* On ancre par rapport à l'item (date) */ C ←σ date=cell.date (C) tant que cell ←-C .next() = ∅ ∧ itemsetT rouvé = f aux faire si supporte(cell , itemSuivant, comptage) alors itemSuivant ←itemset.next() si itemSuivant = ∅ alors itemsetT rouvé ←vrai si itemsetT rouvé = vrai alors /* recherche des autres itemset */ retourner (supportCube(sequence.tail(), σ date>cell.date (C), comptage))

  La figure 6 montre le nombre de fréquents extraits et le temps de calcul en fonction du nombre de dimensions d'analyse. On note que lorsque nous avons une seule dimension d'analyse, nous nous situons dans le cas classique de la recherche des motifs séquentiels. En effet, la définition 14 impose qu'au moins une dimension d'analyse soit instanciée par une valeur de son domaine actif. Dans le cas où nous avons plusieurs dimensions d'analyse, le nombre de fréquents extraits croît quand le nombre de dimensions d'analyse augmente. Ceci est dû principalement à l'augmentation des items fréquents. En effet, tout item fréquent sur k dimensions d'analyse permet la construction d'au moins un item fréquent sur k+1 dimensions d'analyse (ce qui diffère du cas classique de APriori). Par exemple, si les valeurs N Y et jeune apparaissaient ensemble de manière fréquente sur les k = 2 dimensions City et Age, celles-ci se retrouveront nécessairement de manière fréquente sur les k+1 = 3 dimensions City, Age et P roduit si l'on considère la valeur joker * sur la dimension P roduit et l'item (N Y ,jeune, * ). Il est même possible que le nombre d'items fréquents augmente si plusieurs valeurs de P roduit se retrouvent fréquemment associées à N Y et jeune (e.g. (N Y ,jeune,surf ) et (N Y ,jeune,combi)). Le nombre d'items fréquents est donc toujours égal (utilisation de la valeur joker) ou supérieur (valeurs spécifiées) quand on ajoute une dimension d'analyse. Nous avons simulé l'approche de [PHP + 01] afin d'établir une comparaison de cette dernière avec notre approche. Une telle comparaison ne peut s'effectuer qu'en autorisant la valeur joker sur les dimensions d'analyse et sur la mesure (M 2 Sp-alphamu). Les figures figures 7 et 8 relatent ces comparaisons qui sont centrées sur la capacité d'extraction de motifs séquentiels multidimensionnels par rapport à la taille de la base (figure 7) d'une part et le nombre de dimensions d'analyse (figure 8) d'autre part. Notre approche permet l'extraction de plus de motifs séquentiels multidimensionnels. Ceci est principalement dû au fait que notre approche est une généralisation de [PHP + 01] qui permet de surcroît l'extraction de motifs séquentiels multidi-Fig. 6 -Le nombre de motifs extraits et le temps d'exécution en fonction du nombre de dimensions d'analyse mensionnels inter pattern, ce que ne permet pas [PHP + 01].

									1000	M2SP-alpha Han's approach
									800
		1000	M2SP-alpha M2SP-alpha-mu					Number of Frequent Patterns	200 400 600
		800
									0	2	4	6	8	10	12	14
	nombre de frequents	400 600							Number of Analysis Dimensions
		200
			2	4	6	8	10	12	14
				nombre de dimensions d'analyse
			M2SP-alpha-mu M2SP-alpha
	temps d'execution (s)
			2	4	6	8	10	12	14
				nombre de dimensions d'analyse

Le domaine actif d'une dimension est, comme dans le modèle relationnel, la partie finie du domaine de la dimension contenant les valeurs présentes dans la base.


Christophe Jean Douady
email: cdouady@is.dal.ca

Frédéric Delsuc

Yan Boucher

Ford Doolittle

Emmanuel J P Douzery
email: douzery@isem.univ-montp2.fr

W Ford Doolittle

Comparison of Bayesian and Maximum Likelihood Bootstrap Measures of Phylogenetic Reliability

Comparison of Bayesian and maximum likelihood

bootstrap measures of phylogenetic reliability.

Testing evolutionary hypotheses in a phylogenetic context becomes more reliable as reconstruction methods based on more realistic models of molecular evolution are available. However, computing time burden limits the application of model-based methods such as Maximum Likelihood (ML) when many taxa and/or assessment of reliability via standard-non parametric-bootstrap methods are involved [START_REF] Felsenstein | Confidence limits on phylogenies: an approach using the bootstrap[END_REF]. Time savings thus account in part for the increasing popularity of Bayesian inference methods (e.g., [START_REF] Karol | The closest living relatives of land plants[END_REF][START_REF] Lutzoni | Major fungal lineages are derived from lichen symbiotic ancestors[END_REF][START_REF] Murphy | Resolution of the early placental mammal radiation using Bayesian phylogenetics[END_REF], as implemented in programs like MrBayes (Huelsenbeck and Ronquist 2001).

These methods promise computational tractability with large data sets and complex evolutionary models [START_REF] Larget | Markov chain Monte Carlo algorithms for the Bayesian analysis of phylogenetic trees[END_REF]Huelsenbeck et al. 2001).

Bayesian inference of phylogeny combines the prior probability of a phylogeny with the tree likelihood to produce a posterior probability distribution on trees (Huelsenbeck et al. 2001). The best estimate of the phylogeny can be selected as the tree with the highest posterior probability, i.e. the MAximum Posterior probability (MAP) tree [START_REF] Rannala | Probability distribution of molecular evolutionary trees: a new method of phylogenetic inference[END_REF]. Topologies and branch lengths are not treated as parameters-as in ML methods [START_REF] Felsenstein | Evolutionary trees from DNA sequences: a maximum likelihood approach[END_REF])-but as random variables. Because posterior probabilities cannot be obtained analytically, they are approximated by numerical methods known as Markov chain Monte Carlo (MCMC) or Metropolis coupled MCMC (MCMCMC). These chains are designed to explore the posterior probability surface by integration over the space of model parameters. Trees are sampled at fixed intervals and the posterior probability of a given tree is approximated by the proportion of time that the chains visited it [START_REF] Yang | Bayesian phylogenetic inference using DNA sequences: a Markov Chain Monte Carlo method[END_REF]. A consensus tree can be obtained from these sampled trees, and Bayesian posterior probabilities of individual clades (PP), as expressed by the consensus indices, may be viewed as clade credibility values. Thus, Bayesian analysis of the initial matrix of taxa and characters produces both a MAP tree and estimates of uncertainty of its nodes, directly assessing substitution model, branch length and topological variables, as well as clade reliability values, all in a reasonable computation time.

Reliability of nodes in phylogenetic trees is classically evaluated in two ways.

First, from the initial matrix of characters, a strength of grouping value is measured, i.e. the least decrease in log-likelihood associated with the breaking of the clade defined by that node (e.g. [START_REF] Meireles | Molecular phylogeny of ateline New World monkeys (Platyrrhini, Atelinae) based on gamma-globin gene sequences: evidence that Brachyteles is the sister group of Lagothrix[END_REF]. The statistical significance of this decrease can be estimated with non-parametric or parametric tests [START_REF] Goldman | Likelihood-based tests of topologies in phylogenetics[END_REF]. With Bayesian methods, reliability of MAP tree nodes derives directly from corresponding posterior probabilities. In the second way, the initial character matrix is redrawn with replacement, and bootstrap percentages (BP) are calculated, for example under the ML criterion (BP ML ), and interpreted as a measure of experiment repeatability [START_REF] Felsenstein | Confidence limits on phylogenies: an approach using the bootstrap[END_REF] or phylogenetic accuracy [START_REF] Felsenstein | Is there something wrong with the bootstrap on phylogenies -a reply[END_REF].

The Bayesian approach is presumed to perform roughly as bootstrapped ML (Huelsenbeck et al. 2001) but runs much faster [START_REF] Larget | Markov chain Monte Carlo algorithms for the Bayesian analysis of phylogenetic trees[END_REF]Huelsenbeck et al. 2001). Recent analyses have aimed at comparing Bayesian and ML supports by studying the correlation between posterior probabilities (PP) and bootstrap percentages (BP ML ) [START_REF] Leaché | Molecular systematics of the Eastern Fence Lizard (Sceloporus undulatus): a comparison of parsimony, likelihood, and Bayesian approaches[END_REF][START_REF] Whittingham | Phylogeny of the tree swallow genus, Tachycineta (Aves: Hirundinidae), by Bayesian analysis of mitochondrial DNA sequences[END_REF]. A compilation of literature values [START_REF] Karol | The closest living relatives of land plants[END_REF][START_REF] Murphy | Resolution of the early placental mammal radiation using Bayesian phylogenetics[END_REF]Buckley et al. 2002;[START_REF] Leaché | Molecular systematics of the Eastern Fence Lizard (Sceloporus undulatus): a comparison of parsimony, likelihood, and Bayesian approaches[END_REF][START_REF] Whittingham | Phylogeny of the tree swallow genus, Tachycineta (Aves: Hirundinidae), by Bayesian analysis of mitochondrial DNA sequences[END_REF]Wilcox et al. in press) reveals that plotting PP as a function of BP ML can show significant correlation (P-values < 0.02), but that the strength of this correlation is highly variable and sometime very low (correlation coefficient r 2 between 0.29 and 0.99, median at 0.71). Moreover, the slope (S) of the regression line (S between 0.29 and 1.08, median at 0.79) indicates that BP ML are generally lower than PP. This trend has already been noticed by [START_REF] Rannala | Probability distribution of molecular evolutionary trees: a new method of phylogenetic inference[END_REF] in their pioneering work where PP appeared systematically higher than resampling estimated log-likelihood (RELL) bootstrap support values.

As more phylogenetic results relying strictly on Bayesian analyses are published [START_REF] Arkhipova | Three retrotransposon families in the genome of Giardia lamblia: two telomeric, one dead[END_REF][START_REF] Henze | Unique phylogenetic relationships of glucokinase and glucosephosphate isomerase of the amitochondriate eukaryotes Giardia intestinalis, Spironucleus barkhanus and Trichomonas vaginalis[END_REF][START_REF] Lutzoni | Major fungal lineages are derived from lichen symbiotic ancestors[END_REF], a better understanding of the relation between PP and BP ML becomes essential. In a work to be published, Wilcox et al. explored this relation by performing simulations on their original data set. They conclude that, under the condition of their study, PP and BP are both overconservative measures of phylogenetic accuracy, but that Bayesian support values provide closer estimates of the true probabilities of recovering clades. Thus they advocate the preferential use of PP rather than BP (Wilcox et al. in press). However, cases where conflicting hypotheses are supported by high posterior probabilities have been reported (Buckley et al. 2002;Douady et al., in press). This suggests that at least in certain cases PP put overconfidence on a given phylogenetic hypothesis and drawing conclusions from this sole measure of support might be misleading.

To better understand the relationship between PP and BP, we applied standard bootstrap resampling procedures to the Bayesian approach, studying the correlation between PP, BP ML , and BP Bay -i.e. posterior probabilities estimated after bootstrapping of the data-for eight empirical data sets spanning different kind of characters, types of sequences, genomic compartments, and taxonomic groups. Even when the correlation between PP and BP ML was weak (r 2 < 0.52), it became very strong (r 2 > 0.96) when Bayesian posterior probabilities are computed on bootstrapped data matrices. Moreover, albeit less clearly, simulation seems to confirm this trend. These simulations also tend to predict that PP overcome BP support for both true and false nodes. We discuss the effect of the bootstrapped approach in the case of apparent conflicts between data sets, and consider its practical implications for measuring phylogenetic reliability.

Eight highly diverse empirical data sets were chosen (see details in Supplementary Material at MBE web site: http://www.molbiolevol.org), including two pairs showing conflict (i.e., PP strongly supporting mutually exclusive nodes): mitochondrial versus nuclear markers for 14 cicadas (Buckley et al. 2002), and mitochondrial rRNA markers for either 21 or 23 sharks (Douady et al. in press). The model of sequence evolution that best fits each DNA data set and the corresponding GTR substitution rate parameters, shape of the four-categories gamma distribution (Γ4) and fraction of invariable sites (INV) were estimated by Modeltest 3.06 [START_REF] Posada | MODELTEST: testing the model of DNA substitution[END_REF], and then used in PAUP* 4b10 [START_REF] Swofford | PAUP*. Phylogenetic Analysis Using Parsimony (*and Other Methods)[END_REF] to compute ML bootstrap percentages (BP ML ) after 100 pseudo-replications with NJ starting trees and TBR branch swapping. For the HMGR amino acid data set, BP ML were obtained using PROML version 3.6a2.1 of the PHYLIP package [START_REF] Felsenstein | PHYLIP (PHYLogeny Inference Package)[END_REF]) with a JTT substitution matrix provided by E. Tillier (pers. comm.) combined to a Γ4 + INV model, and parameters optimized by PUZZLE 4.0.2 [START_REF] Strimmer | Quartet Puzzling: a quartet maximumlikelihood method for reconstructing tree topologies[END_REF]. Bayesian posterior probabilities (PP) were computed under the same ML models with MrBayes 2.01 (Huelsenbeck and Ronquist 2001) by running four chains for 100,000 MCMCMC generations using the program default priors on model parameters. For bootstrapped Bayesian analyses we generated 100 bootstrap pseudo-replicates for each data set using the program SEQBOOT 3.6a2.1 [START_REF] Felsenstein | PHYLIP (PHYLogeny Inference Package)[END_REF], and estimated Bayesian posterior probabilities as previously described for each pseudo-replicate. For all analyses, 1,000 trees were sampled from the posterior probability distribution (one every 100 generations) and a conservative 50% of the trees (500) was systematically discarded as "burn-in" to ensure that the chains have reached stationarity. Bayesian bootstrap percentages (BP Bay ) were computed for each node into three ways: i) the consensus of the 500 x 100 = 50,000 trees generated from the 100 bootstrapped pseudo-replicates, ii) the average of each nodes PP for the 100 MAP trees, and iii) the consensus of the 100 MAP trees ("consensus of consensus"). Given the tedious aspect of preparing files for bootstrapped Bayesian analyses, a Perl script was custom-made and is available upon request.

We also explored the relation between PP and BP using a simulation design.

Monte Carlo simulation of 100 data sets of 1,000 characters for seven taxa each was performed using SEQ-GEN 1.2.5 [START_REF] Rambaut | Seq-Gen: an application for the Monte Carlo simulation of DNA sequence evolution along phylogenetic trees[END_REF], under a model topology and associated branch lengths taken from the armadillo subset of VWF xenarthran data (Supplementary Material). The K2P model of nucleotide substitution [START_REF] Kimura | A simple method for estimation evolutionary rate of base substitutions through comparative studies of nucleotide sequences[END_REF] was chosen with a transition : transversion ratio of 2.00 and a Γ 8 distribution with α = 1.00. BP ML and PP supports were obtained for these 100 simulated data sets following the same procedure as described above. For computing time reasons, i.e. running 2,500 times MrBayes, BP Bay were only computed for the 25 data sets showing the greatest contrast between BP ML and PP.

For all eight data sets the scatter plots of PP and BP Bay versus BP ML were very similar. In all cases, PP versus BP ML are characterized by a moderate dispersion but a flattened slope (S column in Supplementary Material: 0.18-0.93) while BP Bay vs. BP ML have very little unexplained variation, slopes of correlation lines appearing much steeper and being always very close to 1 (0.93-1.22). Figure 1 illustrates this trend for three individual data sets showing that the results are independent of the nature of the data analyzed: nucleotide versus amino acid characters, nuclear versus mitochondrial compartments, protein coding versus non-coding markers and different taxonomic groups and levels (Fig. 1A-C). Because empirical observations suffer from the difficulty of drawing general conclusions from a limited number of observations, we combined the six strictly independent data sets and confirmed our observations (Fig. 1D; Supplementary Material). Therefore, we are confident that, in empirical data sets, PP and BP ML will prove only moderately correlated (r 2 = 0.27-0.93; S = 0.18-0.93; P-values < 0.02), whereas the BP Bay and BP ML are strongly correlated (r 2 = 0.95-0.99; S = 0.93-1.22; Pvalues < 10 -6 ).

Such a correlation between BP ML and BP Bay seems expectable since the use of uniform priors in the Bayesian analyses involves that the posterior probability density is strongly dependent upon the likelihood function. However, this correlation is not trivial either because the ML and the MAP trees obtained from each bootstrap pseudo-replicate are not always identical. For example, in the case of the 21-shark and xenarthran data sets, ML and MAP trees are different in 38% and 27% of the replicates, respectively. Therefore, the very high quality correlation between BP Bay and BP ML (r 2 >0.95) cannot be expected a priori. We also tested several of the assumptions leading to the strong correlation between BP Bay and BP ML . First, the possibility that the quality of the correlations observed could depend upon random error occurring between independent runs seems to be discarded by the minimal PP variance observed on MCMCMC repeatability plots (Huelsenbeck et al. 2001). It is thus unlikely that the low correlation between PP and BP ML reflects a problem of repeatability between independent runs. Second, we a priori removed 50% of the sampled trees as MCMCMC "burn-in". This was done to ensure that all trees sampled before stationarity were discarded, without actually checking Bayesian results of each individual bootstrap pseudo-replicate. To check for potential biases at this stage, we recomputed BP Bay , keeping 90% of all sampled trees (i.e., removing 100 instead of 500 trees for each pseudo-replicate). Results indicate that bias is quite unlikely as the level of BP Bay variation is very low (e.g., 1% for the ITS data set). Therefore, "burn-in" threshold seems to be of modest importance as long as it is kept realistic, probably because of the rapid convergence towards stationarity of our data. Third, we looked at the effect of making an overall consensus (i.e., consensus of all 50,000 trees sampled over all 100 pseudo-replicates and after a 50% burn-in) versus making the consensus of the 100 MAP trees or the average of the PP. Compilation of node supports-for example for both ITS and Buckley et al. (2002) nuclear data setsyields high correlations (r 2 > 0.95) between BP ML and BP Bay , "PP average" or "MAP trees consensus". However, it seems that BP Bay and "PP average" are closer to Bayesian philosophy whereas "MAP tree consensus" values are closer to the ML bootstrap approach. Indeed, in the two first cases, the complete collection of trees is considered while in the last case a single optimal tree is kept to represent each pseudo-replicate.

Given the likely loss of information during the consensus iteration, it seems that using an overall consensus was a better option.

Non-parametric bootstrapping may be an over-conservative estimator of node reliability [START_REF] Hillis | An empirical-test of bootstrapping as a method for assessing confidence in phylogenetic analysis[END_REF]Wilcox et al. in press; but see [START_REF] Felsenstein | Is there something wrong with the bootstrap on phylogenies -a reply[END_REF][START_REF] Efron | Bootstrap confidence levels for phylogenetic trees[END_REF]. However, it remains the most commonly used way to characterize it. From the statistical point of view, posterior probabilities have the advantage of straightforwardness but, as we just showed, they are not tightly correlated with ML bootstrap percentages. These estimators seem rather different, as PP needs to be calculated on bootstrapped data to behave like BP ML supports. Recently, Wilcox et al. (in press), based on a simulation study, conclude that PP and BP are both over-conservative measures of node support, but that PP provided closer estimates of the true probabilities of recovering clades. Results from our simulations seem to confirm the fact that PP is less conservative than BP. Indeed, when considering true nodes-those that were present in the model topology-PP are generally higher than BP ML and BP Bay (Fig. 2A: upper right quarter). However, PP is also higher when looking at strong support for false nodesthose that were absent of the model tree (Fig. 2B: upper right quarter). Below 50% of PP and BP (Fig. 2B: lower left quarter), i.e. for values that are usually not interpreted for phylogenetic inference, there is a large dispersion of points with a trend of low BP to overestimate accuracy as noted by [START_REF] Hillis | An empirical-test of bootstrapping as a method for assessing confidence in phylogenetic analysis[END_REF]. As a whole these simulation results imply that, at least in certain cases, high PP falsely interpret signal and may end up strongly supporting incorrect phylogenetic relationships. Thus, the more conservative BP ML and BP Bay seem less subject to the behavior of strongly supporting a node when it is actually false.

Furthermore, the existence of strong conflicts in empirical data using Bayesian inference seems to argue that this approach may be sensitive to small model misspecifications as theoretically anticipated by [START_REF] Waddell | A Phylogenetic Foundation for Comparative Mammalian Genomics[END_REF] and subsequently shown by Buckley et al. (2002) and [START_REF] Buckley | Model misspecification and probabilistic tests of topology: evidence from empirical data sets[END_REF]. Bayesian analyses on bootstrapped data were able to eliminate apparent conflicts. Two nodes opposed by PP = 0.93/0.94 (Rhodopsalta sister to either Maoricicada or Kikihia depending on the choice of mitochondrial or nuclear markers: Buckley et al. 2002) and0 In particular, hybridization between taxa might alternatively account for the conflict observed between mitochondrial and nuclear genes in Cicadas. However, in the case of sharks, the conflict arose when taxa are added to the outgroup (for the same gene). It appears more than likely that this spurious conflict was the result of the overestimation of node support based on PP and that conclusions based solely on this estimator would have been positively misleading.

Drawing general conclusions from empirical studies could be problematic because we do not know how representative our example data sets are of phylogenetic problems. However, using "real" data sets does have the advantage of avoiding the simplifying assumptions inherent in simulating DNA data under a given model [START_REF] Buckley | Model misspecification and probabilistic tests of topology: evidence from empirical data sets[END_REF][START_REF] Buckley | The effect of nucleotide substitution model assumptions on estimates of nonparametric bootstrap support[END_REF]. Furthermore, in our case analyses based on both empirical and simulated data seem to corroborate each other in suggesting that, being more conservative, BP ML and BP Bay might be less prone to strongly supporting a false phylogenetic hypothesis, thus reinforcing concerns regarding PP sensitivity to model misspecifications.

Nevertheless, Bayesian inference (with or without bootstrap) remains a very efficient way to simultaneously estimate substitution model parameters, branch lengths and topology under complex models of evolutionary change [START_REF] Huelsenbeck | Testing a covariotide model of DNA substitution[END_REF]). If we take our shark 12S-16S data set with 23 taxa as an example, a regular PP (or one BP Bay replicate) requires roughly 1.5 hour of computing time on a Pentium 4 running at 1.80 GHz, against 120 hours for a single replicate of BP ML with simultaneous estimation of all parameters. Bayesian search on bootstrap data is much faster than ML if the user wants parameters to be estimated as the search goes, and gives very similar results. However, in the wide majority of cases, a ML (or BP ML ) search with simultaneous estimation of the parameters is not necessary and a priori approximations allow the identification of the optimal trees and bootstrap supports. The Bayesian approach also provides a unique way to analyze amino acid data with simultaneous parameters estimation (in popular phylogenetic packages such as PAUP or PHYLIP this option is only available for DNA).

Both PP and Bootstrap supports are of great interest to phylogeny as potential upper and lower bound of node support accuracy, but they are surely not interchangeable and cannot be directly compared. In that context, users may prefer computing PP and BP Bay or BP ML to better explore the range of node support estimates, especially when potential conflicts between data sets are explored. A.

  .98/0.99 (relative position of Hexanchiformes in sharks' inter-ordinal tree depending on the choice of the outgroup: Douady et al. in press) respectively, then received BP Bay = 59/65 and 57/47 after bootstrap resampling. Evidently, certain conflicts diagnosed by PP could be biologically explained by differences between gene trees and species trees introduced by horizontal transfer, lineage sorting, and gene duplication and extinction (review in Maddison 1997).

FIG. 1 .

 1 FIG.1. Linear correlation between maximum likelihood bootstrap percentages (BPML)

2:

  Nuclear protein coding gene vWF (1161 nt) for 13 xenarthran mammals (Delsuc et al. in press); highest likelihood tree: (((Dasypus novemcinctus,Dasypus kappleri),((Euphractus sexcinctus,(Chaetophractus villosus,Zaedyus pichiy)),(Tolypeutes matacus,(Priodontes maximus,Cabassous unicinctus)))),(Cyclopes didactylus,(Tamandua tetradactyla,Myrmecopha tridactyla)),(Choloepus didactylus,Bradypus tridactylus)).Seven armadillo genera are underlined and were used to provide the model tree for simulations.3 : EF1α protein coding gene (2033 nt) ofBuckley et al. (2002) for 14 cicada insects; highest likelihood tree: (Diemeniana frenchi,Diemeniana tillyardi,(((Amphipsalta cingulata,Notopsalta sericea),(Cicadetta celis,Cicadetta puer)),(Pauropsalta johanae,(Myersalna depicta,((Maoricicada cassiope,Maoricicada hamiltoni),((Kikihia scutellaris,Kikihia cauta),(Rhodopsalta cruentata,Rhodopsalta leptomera))))).

  4 : Mitochondrial (12S-16S ribosomal RNA [rRNA] + COI + COII) markers (2249 nt) ofBuckley et al. (2002) for 14 cicadas; highest likelihood tree: (Diemeniana frenchi,Diemeniana tillyardi,(((Amphipsalta cingulata,Notopsalta sericea),(Cicadetta celis,Cicadetta puer)),(Pauropsalta johanae,(Myersalna depicta,((Kikihia scutellaris,Kikihia cauta),((Maoricicada cassiope,Maoricicada hamiltoni),(Rhodopsalta cruentata,Rhodopsalta leptomera))))).

  hydroxy-3-methylglutaryl coenzyme A reductase (HMGR, 258 amino acids) for 15 taxa representing all three domains of life (Eukarya-Bacteria-Archea; Boucher et al. 2001); highest likelihood tree: (((Archaeoglobus profundus,(Archaeoglobus fulgidus,(Streptococcus pyogenes,Pseudomonas mevalonii))),((Saccharomyces cerevisiae,Homo sapiens),(Arabidopsis thaliana,Zea mays))),((Methanothermobacter thermautotrophicus,(Vibrio cholerae,Haloferax volcanii)), (((Pyrococcus abyssi,Pyrococcus horikoshii), Streptomyces aeriouvifer ), Aeropyrum pernix))) 6 : Shark mitochondrial 12S-16S rRNA for 23 taxa (1880 nt, Douady et al., in press); highest likelihood tree: (Petromyzon marinus,(Polymixia japonica,((((((Centrophorus granulosus,Squalus acanthias),(Squatina californica,Pristiophorus nudipinnis)),((Heterodontus francisci,Ginglymostoma cirratum),(((((Isurus oxyrinchus,Isurus paucus),Lamna nasus),Carcharodon carcharias),(Carcharias taurus,Alopias vulpinus)),((Carcharhinus porosus,Mustelus manazo),Scyliorhinus canicula)))),(Hexanchus griseus,Heptranchias perlo)),(Raja radiata,Urobatis jamaicensis)),Hydrolagus colliei)),Siren intermedia).

7:

  Shark mitochondrial 12S-16S rRNA for 21 taxa (1963 nt, Douady et al., in press); highest likelihood tree: (Polymixia japonica,(((((((Centrophorus granulosus,Squalus acanthias),(Squatina californica,Pristiophorus nudipinnis)),(Hexanchus griseus,Heptranchias perlo)),((((((Isurus oxyrinchus,Isurus paucus),Lamna nasus),Carcharodon carcharias),Carcharias taurus),Alopias vulpinus),((Carcharhinus porosus,Mustelus manazo),Scyliorhinus canicula))),Heterodontus francisci),Ginglymostoma cirratum),(Raja radiata,Urobatis jamaicensis)),Hydrolagus barbouri).

  highest likelihood tree: ((Leptotyphlops dulcis,(Typhlops jamaicensis,Typhlops ruber)),(Anilius scytale,((Trachyboa boulengeri,(Tropidophis greenwayi,(Tropidophis pardalis,(Tropidophis feicki,Tropidophis melanurus)))),((Xenopeltis unicolor,(Morelia boeleni,Loxocemus bicolor)),((Cylindrophis ruffus,(Uropeltis melanogaster,Rhinophis philippinus)),(((Ungaliophis continentalis,Exiliboa placata),Eryx conicus),(Boa constrictor,(Acrochordus javanicus,(Pituophis lineaticolis,(Crotalus polysticus,Azemiops feae)))))))))).

9:

  Six strictly independent data sets (Sharks 12S-16S [21 taxa] and Insects EF1α data sets excluded).

  Figure 3

: Snake mitochondrial 12S-16S rRNA for 23 taxa (1545 nt,Wilcox et al., in press);

Acknowledgments

Chris Simon and Thomas R. Buckley kindly made their Cicada data sets available. David M. Hillis and Thomas P. Wilcox provided precious enlightenment about their simulations on the Snake data set. We are grateful to Alistair G. B. Simpson, the Associate Editor Mark A. Ragan, and two anonymous reviewers for insightful comments. This work was supported by a grant from the Canadian Institute for Health Research (MOP-42470), a Killam Postdoctoral Fellowship to CJD, a doctoral MENRT grant (contract 99075) to FD, a doctoral research award from the Canadian Institutes of Health Research to YB, and by the TMR Network "Mammalian phylogeny" (contract FMRX -CT98 -022) of the European Community, the "Génopole Montpellier Languedoc-Roussillon", and the "Action Bioinformatique" of the CNRS to EJPD. This is the contribution ISEM 2002-BBB of the Institut des Sciences de l'Evolution de Montpellier (UMR 5554 -CNRS).