Celine Scornavacca

Vincent Berry
email: vberry@lirmm.fr

Vincent Ranwez
email: vincent.ranwez@univ-montp2.fr

From Gene Trees to Species Trees Through a Supertree Approach

Keywords: Computational biology, evolutionary trees, graphs and graph transformation, duplications, polynomial and FPT algorithms, intractability proof

Gene trees are leaf-labeled trees inferred from molecular sequences. Due to duplication events arising in genome evolution, gene trees usually have multiple copies of some labels, i.e. species. Inferring a species tree from a set of multi-labeled gene trees (MUL trees) is a wellknown problem in computational biology. We propose a novel approach to tackle this problem, mainly to transform a collection of MUL trees into a collection of evolutionary trees, each containing single copies of labels. To that aim, we provide several algorithmic building stones and describe how they fit within a general species tree inference process. Most algorithms have a linear-time complexity, except for an FPT algorithm proposed for a problem that we show to be intractable.

Introduction

An evolutionary tree (or phylogeny), is a tree displaying the evolutionary history of a set of sequences or organisms. A gene tree is an evolutionary tree built by analyzing a gene family, i.e. homologous molecular sequences appearing in the genome of different organisms. Gene trees are primarily used to estimate species trees, i.e. trees displaying the evolutionary relationships among studied species. Unfortunately, most gene trees can significantly differ from the species tree for methodological or biological reasons, such as long branch attraction, lateral gene transfers, deep gene coalescence and, principally, gene duplications and losses [START_REF] Cotton | Rates and patterns of gene duplication and loss in the human genome[END_REF]. For this reason, species trees are usually estimated from a large number of gene trees.

Inferring a species tree from gene trees is mostly done in a two-step approach. First, a micro-evolutionary model that takes into account events affecting individual sites is used to infer the gene trees. The species tree is then inferred on the basis of a macro-evolutionary model, i.e. minimizing the number of transfer, duplication and loss events [START_REF] Ma | From gene trees to species trees[END_REF][START_REF] Hallett | New algorithms for the duplication-loss model[END_REF][START_REF] Chen | Notung: a program for dating gene duplications and optimizing gene family trees[END_REF][START_REF] Vernot | Reconciliation with non-binary species trees[END_REF][START_REF] Chauve | Gene family evolution by duplication, speciation, and loss[END_REF]. To produce more biologically meaningful trees, unified models have been proposed in which the micro and macro-evolutionary dimensions are entangled [START_REF] Goodman | Fitting the Gene Lineage into its Species Lineage, a Parsimony Strategy Illustrated by Cladograms Constructed from Globin Sequences[END_REF][START_REF] Arvestad | Bayesian gene/species tree reconciliation and orthology analysis using MCMC[END_REF][START_REF] Durand | A hybrid micro-macroevolutionary approach to gene tree reconstruction[END_REF]. However, it is difficult to determine how to incorporate events occurring on different spatial and temporal scales, as well as belonging to neutral and non-neutral processes, in a single model [START_REF] Durand | A hybrid micro-macroevolutionary approach to gene tree reconstruction[END_REF]. Lately, a hybrid approach has been proposed, where a first draft of a species tree is inferred with a micro-evolutionary model, the most uncertain parts of which are then corrected according to a macro-evolutionary model [START_REF] Durand | A hybrid micro-macroevolutionary approach to gene tree reconstruction[END_REF].

In this paper, we propose instead to take advantage of the very large number of gene trees present in recent phylogenomic projects to avoid entering into the detail of all possible macro-evolutionary scenarios (e.g. is a parsimony approach always justified? Should only the most parsimonious scenario be retained?). We propose to extract the non-ambiguous part of the topological information contained in the gene trees, i.e. that resulting from speciation events as opposed to duplication events, and then apply a traditional supertree method letting the weight of evidence decide in favor of one candidate species tree [START_REF] Baum | The MRP method[END_REF][START_REF] Page | Modified mincut supertrees[END_REF][START_REF] Scornavacca | Physic ist: cleaning source trees to infer more informative supertrees[END_REF].

This approach is only possible when the number of gene trees is very large, and indeed this is now the case in projects such as the HOMOLENS database (http://pbil.univ-lyon1.fr/databases/homolens.php), storing several thousands of gene trees. In the release 04 of this database, 51% of gene families have paralogous sequences, i.e. sequences where duplications and losses have actually taken place. Currently, these gene families are discarded when inferring a supertree of the concerned species. Disentangling information derived from speciation events from that resulting from duplication events would thus provide more information for species tree inference. Supertree methods combine source trees whose leaves are labeled with individual species into a larger species tree. The source trees are single-labeled, i.e. each species labels at most one leaf. Note that, by definition, the inferred supertree is also single-labeled. In contrast, gene trees are usually multi-labeled, i.e. a single species can label more than one leaf, since duplication events resulted in the presence of several copies of the genes in the species genomes. The task we therefore have to solve is to extract the largest amount of unambiguous topological information from the multi-labeled gene trees under the form of single-labeled trees. This paper presents a number of results in this direction, that all play a role in the general scheme that is fully described below. The rest of the paper details these results, though in a different order for the sake of dependancies between definitions.

First of all, we propose to separately preprocess MUL trees in order to remove their redundant parts with respect to speciation events. For this purpose, we extend the tree isomorphism algorithm of [START_REF] Gusfield | Efficient algorithms for inferring evolutionary trees[END_REF] making it applicable to MUL trees while preserving a linear running time (section 5). This algorithm is then applied to the pairs of subtrees hanging from duplication nodes in MUL trees. We also give in passing a linear time algorithm to identify duplication nodes in MUL trees (section 4). This preprocess lowers the number of duplication nodes in gene trees. For the gene trees that still have duplication nodes, we define a set of triplets (binary rooted trees on three leaves [START_REF] Aho | Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions[END_REF][START_REF] Scornavacca | Physic ist: cleaning source trees to infer more informative supertrees[END_REF]) containing the topological information of a MUL tree that can be thought of as being unambiguously related to speciation events. We show that this set of triplets can be computed in linear time (section 2). When this set is compatible, the MUL tree contributes a coherent topological signal to build the species tree. In such a case, we can replace the MUL tree with a single-labeled tree representing its associated set of triplets by using the BUILD algorithm [START_REF] Aho | Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions[END_REF] (section 3). When a MUL tree is not auto-coherent, we propose to extract a maximum subtree that is both autocoherent and free of duplication events. Surprisingly, this optimization problem can be solved in linear time (section 6). When extracting largest single-labeled subtrees from MUL trees it is possible to obtain an incompatible collection, when a compatible collection could have been obtained by choosing subtrees of MUL trees in a coordinated way. However, solving this problem is computationally harder, as we show by providing an NP-completeness proof (section 7).

Preliminaries

In this paper we focus on rooted binary multi-labeled (MUL) trees. Let M be a MUL tree and n a vertex of M . We denote by s(n) and s'(n) the two sons of n and by sons(n) the set {s(n),s'(n)}. We define by subtree(n) the subtree with n as root and by L(n) the set of labels of subtree(n).

Definition 1. A node n of M is called an observed duplication node (odn) if the intersection of L(s(n)) and L(s ′ (n)) is not the empty set.
Note that, for an odn n, L(n) can contain one label more than once. We denote by D(M ) the set of odn. A label l ∈ L(M ) is a repeated label for M iff the label l occurs more than once in L(M ). We say that f is a repeated leaf for M iff L(f ) is a repeated label. For every three leaves we can have three different rooted tree binary shapes, called triplets. We denote by AB|C the rooted tree that connects the pair of taxa (A, B) to C via the root. We denote by R(M ) the set of triplets of a (single/multi)labeled evolutionary tree M i.e. R(M ) = {ab|c s.t. there exist three leaf nodes x, y, z ∈ M : L(x) = a, L(y) = b, L(z) = c and lca 1 (x, y) = (lca(x, z) =lca(y, z))}. Definition 2. Let M be a MUL tree. We define by R wd (M ) (R(M ) without duplications) the set of triplets ab|c of M s.t. there exist three leaf nodes x, y, z ∈ M : L(x) = a, L(y) = b, L(z) = c and lca(x, y) / ∈ D(M ), lca(x, y, z) / ∈ D(M ), lca(x, y) = (lca(x, z) =lca(y, z)).

For the MUL tree in figure 1 for example, R wd (M ) = {ac|b, ac|d, ab|d, bc|d, ac|o, ab|o, ad|o, bc|o, cd|o, bd|o, ab|c}. Hence, not all the triplets of R ( M ) are kept. This is due to the fact that, once a duplication event occurred in a gene's history, the two copy of the gene evolved independently. Each copied history is influenced by the species history but, considering them simultaneously may produce information unrelated to the species evolution. Therefore, it is more appropriate to discard the triplets mixing the histories of the two copies.

R wd (M ) has an O(n 3 ) size and can be computed in O(n 3 ) time. Indeed, once the lca of all pairs of nodes in M are computed in O(n) (see [START_REF] Harel | Fast algorithms for finding nearest common ancestors[END_REF][START_REF] Bender | The lca problem revisited[END_REF]), checking for three leaf nodes x, y, z of M if they satisfy the definition 2 can be done in 0(1) and in O(n 3 ) for all triplets of leaf nodes in M .

Auto-coherency of a MUL tree

Let M be a multi-labeled gene tree. Since M contains several copies of the same gene, we can wonder whether the evolutionary signal of each copy is coherent or not. Definition 3. Let M be a MUL tree. If there exists a tree T such that R wd (M ) ⊆ R(T ), we say that M is auto-coherent.

In the case of an auto-coherent MUL tree, we know that we can find a tree T containing all the information in R wd (M ), i.e. the information of M that is considered reliable. To find such a tree, we use the BUILD algorithm [START_REF] Aho | Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions[END_REF]. For a set of triplets R wd (M ), this algorithm indicates in O(|R wd (M )|) time whether there exists a tree T s.t. R wd (M ) ⊆ R(T ) and returns T in case of a positive answer. The time complexity of the algorithm checking the auto-coherency of a MUL tree is O(n 3 ) and it's dominated by the computation of R wd (M ).

Computing D(M ) in linear time

The easiest way to compute D(M ) is checking for each node n if the sets L(s(n)) and L(s ′ (n)) have at least one label in common; in the case of a positive answer, n is inserted in D(M ). The complexity of this approach is O(n 2 ), since it requires computing O(n) intersections of two lists of O(n) elements. The algorithm 1 uses the lca to find the set of odn D(M ) and requires only linear time. To demonstrate the correctness of algorithm 1, we need to determine some relationships between the lca and the odn. Lemma 1. A node is an odn if and only if it is the lca of at least two repeated leaves m and p.

Proof. Indeed, from the definition 1, n is an odn iff L(s(n)) ∩ L(s'(n)) = ∅. Therefore, ∃m ∈ subtree(s(n)) and ∃p ∈ subtree(s ′ (n)): L(m) = L(p). Thus n is a common ancestor of the two leaves m and p with the same label. Now, m and p belong to two different subtrees having n as father (m ∈ subtree(s(n)) and p ∈ subtree(s ′ (n))), hence n is their lowest common ancestor in M . Reciprocally, if n is the lca of two leaves m and p with the same label, this means that L(s(n)) ∩ L(s'(n)) = ∅, then n is an odn according to definition 1.

According to lemma 1, we can search for the lca of any two leaves m and p with the same label. The lca of all pairs of nodes in T can be computed in O(n) (see [START_REF] Harel | Fast algorithms for finding nearest common ancestors[END_REF][START_REF] Bender | The lca problem revisited[END_REF]). Once we have all lca, computing lca(m, p) requires O(1) time. We still have O(n 2 ) of these couples, giving an O(n 2 ) complexity. However, since there are only O(n) odn, checking the lca of any pair of leaves makes us recover the same odn several times. A smarter approach is used in algorithm 1: first of all, the subtrees of M are ordered from the left to the right in an arbitrary way. Then, each repeated leaf, starting from the left of the tree and moving to the right, is tagged with the repeated label followed by its occurrence number. Then, for each repeated label e, the lca of any two successive occurrences of e, e i and e i+1 is inserted in D(M ). This leads to a linear time complexity. Indeed, we have O(n) of these couples since each leaf of M is involved in at most two pairs (e i , e i+1 ). The correctness of algorithm 1 is justified by the lemma 2 showing that algorithm 1 retrieves all the odn of M .

Lemma 2. Let M be a MUL tree. For each odn n, ∃ two successive occurrences of a label e denoted by e i and e i+1 s.t. n = lca(e i , e i+1 ).

Proof. Given an odn n, there exists at least one label e present in both subtrees s(n) and s ′ (n). We denote by A the set of leaves a i s.t. a i ∈ subtree(s(n)) and L(a i ) = e and by B the set of leaves b j s.t. b j ∈ subtree(s ′ (n)) and L(b j ) = e.

If we take the last element of B (b |B| ) and the first one of A (a 1 ), we know that n is their lca. Additionally, due to the way we tagged M, we know that there is no other occurrence of the label e between b |B| and a 1 . Indeed, if there was another leaf x labeled with e, it would be either in s(n) (and then x = a 1 ) or in s ′ (n) (and then x = b |B| ). Then b |B| and a 1 are two successive occurrences of the same label and their lca is the node n.

Definition 4. Two rooted trees T 1 , T 2 are isomorphic (denoted by T 1 =T 2 ) iff there exists a one-to-one mapping from the nodes of T 1 onto the nodes of T 2 preserving leaf labels and descendancy.

We are interested in testing if, for each odn n, the two subtrees s(n) and s ′ (n) are isomorphic or not. In the case of a positive answer, we can prune one of the two isomorphic subtrees without losing information and eliminate the odn n, as in the example in figure 2. The algorithm 2 is an extension of the algorithm Checkisomorphism-or-find-conflict algorithm [START_REF] Berry | Improved parameterized complexity of the maximum agreement subtree and maximum compatible tree problems[END_REF] applicable to MUL trees. The latter is not able to deal with MUL trees. A node that has only two leaves as children is called cherry. In the case of single-labeled trees we have the following lemma:

Lemma 3.

[16] Let T 1 , T 2 be two isomorphic trees and let c 1 be a cherry in T 1 .

Then, there is a cherry

c 2 ∈ T 2 s.t. L(c 1 ) = L(c 2 ).
In the case of M U L trees, we can have several copies of the same cherry. We call a multiple cherry the list of cherries on the same two labels. The lemma 3 becomes: Lemma 4. Let M 1 , M 2 be two isomorphic MUL trees and let mc 1 be a multiple cherry in M 1 . Then, there is a multiple cherry

mc 2 ∈ M 2 s.t. L(mc 1 ) = L(mc 2 ) and |mc 1 | = |mc 2 |.
The proof is inspired from that of lemma 3 in [START_REF] Gusfield | Efficient algorithms for inferring evolutionary trees[END_REF] and left to the reader for lack of space.

Outline of the algorithm

First of all, we find all the multiple cherries for the MUL trees M 1 and M 2 . We store them in the list L mc using a simple linked list. Additionally, we use a hashtable H where each mc ∈ L mc is a key. H associates to each multiple cherry mc two linked lists, O 1 (mc) and O 2 (mc), storing pointers to nodes of M 1 and M 2 respectively that correspond to the occurrences of mc. The multiple cherries of a MUL tree are then examined in a bottom-up process. Given a multiple cherry mc in L mc we check if the size of O 1 (mc) is the same as that of O 2 (mc). If this is not the case, we have found a multiple cherry for which we do not have the same number of occurrences in M 1 and M 2 . In this instance, M 1 and M 2 are not isomorphic (lemma 4) and the algorithm returns FALSE. Otherwise we turn all the cherries in 1 (mc) and O 2 (mc) into leaves to which the same label, chosen arbitrarily in L(mc), is assigned. This modification of M 1 and M 2 can turn the fathers of some cherries in O 1 (mc) and O 2 (mc) into new cherries. Then L mc is updated and the processing of cherries in M 1 is iterated until both MUL trees are reduced to a single leaf with the same label if M 1 and M 2 are isomorphic, or a FALSE statement is returned. Proof. This algorithm is an extension of the Check-isomorphism-or-findconflict algorithm [START_REF] Berry | Improved parameterized complexity of the maximum agreement subtree and maximum compatible tree problems[END_REF] applicable to MUL trees. We show here that we can keep a linear time execution, using supplementary data structures. A simple depth-first search of trees M 1 and M 2 initializes L mc and H in O(n) time. At each iteration of the algorithm, choosing a multiple cherry mc to process is done in O(1) by removing the first element mc of L mc . H then provides in O(1) the lists O 1 (mc) and O 2 (mc) of its occurrences in the trees. Checking that these lists have the same number of elements is proportional to the number of nodes they contain, hence costs O(n) amortized time, as each node is only once in such a list, and the list is processed once during the whole algorithm. Replacing all occurrences of mc by a previously chosen label l ∈ L(mc) is done in O(n) amortized time, since each replacement is a local operation replacing three nodes by one in a tree and at most O(n) such replacements can take place in a tree to reduce it down to a single node (the algorithm stops when this situation is reached). Reducing a cherry can create a new occurrence o mc ′ of a cherry mc ′ . Checking in O(1) time if mc ′ is a key in H allows to know whether occurrences of mc ′ have already been encountered or not. In the positive, we simply add o mc ′ to the beginning of the list O 1) time. In the negative, we add mc ′ to the beginning of L mc , create a new entry in H for mc ′ , and initialize the associated lists O 1 (mc) and O 2 (mc) so that one contains o mc ′ and the other is the empty list. Again, this requires only O(1) time. Thus, performing all operations required by the algorithm globally costs O(n) time.

1 (mc) (if o mc ′ ∈ M 1 ) or O 2 (mc) (if o mc ′ ∈ M 2 ), requiring O(
Apply algorithm 2 to each subtree(s(n)) and subtree(s ′ (n)) of each odn of a MUL tree M in a bottom-up approach requires O(dn) time, where d is the number of duplication nodes in M .

Computing a largest duplication-free subtree of a MUL tree

If a MUL tree is not auto-coherent, identifying duplication nodes allows for the discrimination of leaves representing orthologous and paralogous sequences. Since only orthologous sequence history reflects the species history, a natural question is to determine the most informative sequence set for a given gene. As long as the gene tree contains odn, it will also contain leaves representing paralogous sequences. Yet, if for each node n ∈ D(M ) of M we choose to keep either s(n) or s ′ (n), we obtain a pruned single-labeled tree containing only apparent orthologous sequences (observed paralogous have been removed by pruning nodes). Note that the so obtained singe-label tree is auto-coherent by definition.

Definition 5. Let M be a MUL tree. We say that T is obtained by (duplication) pruning M iff T is obtained from M choosing for each odn n either s(n) or s ′ (n).

We denote this operation by the symbol .

One can wonder, for a non auto-coherent MUL tree M , what is the most informative tree T s.t. T M . We define this problem as the M IP T (Most Informative Pruned Tree) problem.

To evaluate the informativeness of a tree we can use either the number of triplets of T (see [START_REF] Ranwez | PhySIC: a veto supertree method with desirable properties[END_REF][START_REF] Semple | A supertree method for rooted trees[END_REF][START_REF] Page | Modified mincut supertrees[END_REF]) that, for binary trees, depends only on the number of leaves, or the CIC criterion (see [START_REF] Thorley | The information content of consensus trees[END_REF][START_REF] Scornavacca | Physic ist: cleaning source trees to infer more informative supertrees[END_REF]). The CIC of an incomplete tree T with |L(T )| leaves among the n possible is a function of both the number n R (T, n) of fully resolved trees T ′ on L(T ) such that R(T ) ⊆ R(T ′ ) and the number n R (n) of fully resolved trees on n leaves. More precisely,

CIC(T, n) = -log n R (T, n)/n R (n)
In the case of binary trees, n R (T, n) depends only on the number of source taxa missing in T since T does not contain multifurcations. Thus, dealing with binary trees, maximizing the information of a tree (i.e. maximizing the number of triplets or minimizing the CIC value) consists in finding the tree with the largest number of leaves. A natural approach for the MIPT problem for binary MUL trees is an algorithm that, after having computed D(M ), uses the bottom-up algorithm 3, with n =root(M ), to keep the most informative subtree between subtree(s(m)) and subtree(s ′ (m)), for each odn m.

Fig. 1 .

 1 Fig. 1. An example of MUL tree with one odn indicated by a black square.

Algorithm 1 :

 1 CompDuplicationNodes(r)Data: A MUL tree M . Result: A set of odn D(M ). Order M in an arbitrary way. In this order, tag each duplicated leaf with the repeated label followed by its occurrence number. Compute the lca for each couple of leaves. D(M ) ← ∅; foreach (repeated label e) do foreach ({ej , ej+1}) do D(M ) ← lca(ej, ej+1);return D(M );

Fig. 2 .

 2 Fig. 2. An example of MUL tree where the sons of the duplication node are isomorphic.

Theorem 1 .

 1 Let M 1 and M 2 be two rooted MUL trees with L(M 1 ) = L(M 2 ) of cardinality n. In time O(n), algorithm 3 returns TRUE if M 1 and M 2 are isomorphic, FALSE otherwise.

  Algorithm 2: CheckIsomorphismMULTree(M 1 ,M 2 ) Data: Two MUL tree M1 and M2. Result: TRUE if M1 and M2 are isomorphic, FALSE otherwise. Let Lmc be the list of multiple cherries in M1 and M2. Let H be the hashtable where each mc ∈ Lmc is a key. To each H(mc), we associates two lists O2(mc) and O1(mc), resp. of the occurrences of mc in M1 and M2; while (Lmc = ∅) do mc ← the first multiple cherry in Lmc; delete mc form Lmc; if (O2(mc) = O1(mc) ) then Turn all cherries in O2(mc) and O1(mc) into leaves to which the same label chosen in L(mc) is assigned; add the new multiple cherries in Lmc and H; else return FALSE; return TRUE;

T (li) is expressed in the Newick format.

Given a tree T and a label set S, we denote by T |S the restriction of T to the set S.

Proof. First of all, it's obvious that pruning(M,root(M ),D(M )) returns a tree. Indeed, if for each odn n only one node between s(n) and s ′ (n) is kept, at the end of the bottom-up procedure one copy of each duplicated leaf is present in the modified M . Now, we have to show that the resulting tree is the most informative tree s.t. T M , i.e. the tree with as many leaves as possible. For an odn n that is the ancestor of other duplication nodes, the choices made for s(n) do not influence the choices for s ′ (n) since for each duplication node we can keep only one of the two subtrees, the most populous one. Thus we can search for the best set of choices left/right for s(n) and s ′ (n) independently and then choose the most populous pruned subtree between s(n) and s ′ (n). Iterating recursively this reasoning, we demonstrate that the tree obtained by the algorithm 3 is the most informative tree T s.t. T M .

The computation of the set of odn D(M ) takes linear time. The subroutine pruning(M, root(M), D(M )) requires a tree walk, thus the time complexity of the algorithm 3 is O(n).

The compatibility issue of single-labeled subtrees obtained from MUL trees

We can also ask if it is possible, given a collection of MUL tree M, to discriminate leaves representing orthologous and paralogous sequences in a gene tree using the information contained in the other gene trees to obtain a compatible forest T , i.e. a forest for which there exists a tree T s.t. ∪ Ti∈T R(T i ) ⊆ R(T ). We denote this problem by ECF, Existence of a Pruned and Compatible Forest. Unfortunately, the ECF problem is NP-complete.

EPCF

Instance : A set of leaves X and a collection

Proof. We start by proving that EPCF is in NP, i.e. checking if a set S of choices left/right is a solution for the instance I = (M, X) can be done in polynomial time. First of all, for each MUL tree M j ∈ M, we place the choices left/right on M j , i.e. we discard the subtrees not chosen, obtaining a forest of trees T . We check then the compatibility of T with the Aho graph [START_REF] Aho | Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions[END_REF]. Constructing this graph can be done in polynomial time.

Given that EPCF is in NP, we use a reduction of 3-SAT to EPCF to demonstrate that it is NP-complete.

3-SAT

We need to show that every instance of 3-SAT can be transformed into an instance of EPCF; then we will show that given an instance I = (C, L) of 3-SAT, I is a positive instance, i.e. an instance for which a solution exists, iff the corresponding instance for EPCF is positive.

Given an instance I = (C, L) of 3-SAT, we build an instance I ′ = (M, X) of EPCF associating to each l i in L the binary tree 2 T (l i ) = (((x i , y i ), z i ), d) and to l i the binary tree T (l i ) = (((z i , y i ), x i ), d) (see figure 3 for an example). The set of subtrees

Then, for each clause C j = (a∨b∨c) in C, a binary MUL tree M j is built, formed by three subtrees ((T (a), T (b)), T (c)). Note that M j has exactly two duplication nodes due to the presence of d in T (a), T (b) and T (c), so that any left/right choice of M j will reduce it to either T (a), T (b) or T (c). In figure 4 an example of a MUL tree built from a clause. In this way we obtain a forest of MUL trees M on the leaf set X = m i=1 {x i , y i , z i } ∪ {d} , i.e. an instance of the EPCF problem. Clearly M can be built in polynomial time. We now need to show that a positive instance of 3-SAT gives a positive instance of EPCF through the previous transformation. Having a positive instance for 3-SAT implies that for each C j ∈ C with C j = (a ∨ b ∨ c), at least one of the three literals is TRUE. Without loss of generality, let us suppose that a is TRUE. Then in the MUL tree M j corresponding to C j we set the choice left/right so that only the subtree T (a) is kept. We then obtain a forest T that is a subset of T L . We need to prove that T is compatible. Let T (a) denote the tree T tree T s = ( T1 , T2 , • • • , T| T | , d). Since l i cannot have the value TRUE and FALSE at the same time, we have either T (l i ) or T (l i ) in T . The tree T s is therefore a single-labeled tree. Moreover, by construction T s |(L(T (a)) is identical to T (a), for all T (a) in T ensuring that Ti∈T R(T i ) ⊆ R(T s ). Thus T is compatible. Now, the only thing left to prove is that a positive instance of ECT gives a positive instance of 3-SAT. The repetition of the taxon d in each subtree makes the two nodes connecting the subtrees in each M j be odn. Thus a left/right choice set S reduces each M j in M into a tree T (a) ∈ T L , providing the forest T . Setting the value of a to TRUE ensures that the clause C j corresponding to M j is TRUE. This can be done simultaneously for all clauses ∈ C since the forest compatibility implies that there is no contradiction among the trees in T , all the more so direct contradictions. Then, either T (l i ) or T (l i ) is in T . This ensures us that either l i or l i is assigned to TRUE, but not both.

Note that the optimization problem associated with the EPCF, the MIPCF (Most Informative Pruned and Compatible Forest) problem is FPT. Indeed, analyzing all possible scenarios of choices left/right is FPT on the total number of duplication nodes in M.

Conclusions

In this paper we presented several algorithms to transform multi-labeled evolutionary trees into single-labeled ones so that they can be used by all existent supertree methods. In the future we plan to go further and extend the algorithm find-refinement-or-confict in [START_REF] Berry | Improved parameterized complexity of the maximum agreement subtree and maximum compatible tree problems[END_REF] applicable to MUL trees. We are also working on a more sophisticated FPT algorithm for the MIPCF problem.


Carole Daiguebonne

Olivier Guillou

Myrtil L Kahn

Olivier Kahn

Robert L Oushoorn

Kamal Boubekeur

A NdIIICuII molecular material with a honeycomb-like structure

à 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.

Introduction

One of the challenges in the field of molecular and supramolecular magnetism is to design materials exhibiting expected magnetic properties. [1][2][3][4][5][6][7][8][9][10][11] A necessary, if not sufficient, condition for this is obviously to control the architecture of the materials. For several years, we have been involved in the design of materials with different dimensionalities and topologies from a common precursor (which we also call a brick). Such an approach has been particularly developed in the case of the precursor [Cu(opba)] 2-, with opba standing for o-phenylenebis-(oxamato), whose structure is schematized below:

From this precursor, it was already possible to design linear and zigzag chains, 12,13 two-dimensional networks with a honeycomb-like structure, 13,14 three-dimensional networks with an interlocked structure, 15-17 and ladder compounds. 18 The com-pounds with parallel ladder motifs were obtained through the reaction of [Cu(opba)] 2-with a trivalent lanthanide ion, Ln III . Their formula is Ln 2 [Cu(opba)] 3 'S with S standing for solvent molecules. The Ln 2 Cu 3 stoichiometry is in principle also compatible with a two-dimensional honeycomb-like structure. The compounds of formula cat 2 M II [Cu(opba)] 3 'S, where M II is a divalent 3d ion, have such a honeycomb-like structure, with cat + cations located between M II [Cu(opba)] layers. 13,14 For quite some time, we have been wondering whether a honeycomblike structure of formula Ln 2 [Cu(opba)] 3 'S could be obtained. We report here on our results along this line.

Experimental Section

Synthesis. Reaction in a sealed tube of two 10 -4 M DMF ) dimethylformamide solutions of hexahydrated Nd III chloride and Na2-[Cu(opba)] at 70 °C within ca. 3 days affords tiny but well-shaped crystals of a compound of formula {Nd2[Cu(opba)0.5(ox)]3'9DMF}' 4.5DMF, with ox ) oxalato. During the synthesis, a partial hydrolysis of the oxamido groups into oxalato groups occurred. The yield of this reaction is 70%.

X-ray Crystallography. A single crystal was sealed in a glass capillary and mounted on a STOE IPDS single φ-axis diffractometer with a 2D area detector based on imaging plate technology. X-ray data were collected at room temperature; 300 images were recorded by using the rotation method (0°e φ e 150°) with ∆φ ) 0.5°increments, an exposure time of 5 min, and a crystal to plate distance of 60 mm (EXPOSE). 19 The images were processed with the set of programs from † Institut National des Sciences Applique ´es. ‡ Institut de Chimie de la Matie `re Condense ´e de Bordeaux. § Institut des Mate ´riaux Jean Rouxel.

(1) Kahn, O. Angew. Chem., Int. Ed. Engl. 1985, 24, 834. (2) Caneschi, A.; Gatteschi, D.; Sessoli, R.; Rey, P. Acc. Chem. Res. 1989, 22, 392. (3) Miller, J. S.; Epstein, A. J. Angew. Chem., Int. Ed. Engl. 1994, 33, 385. ( 4 Dcalc: 1.648 g cm -3 Z: 9 µ: 0.910 cm -1 R: a 7.90% 19 Data were corrected by an empirical absorption correction (ABSCOR). 19 The structure was solved by direct methods with SHELXS-86 20 and refined by full-matrix least-squares calculations on F 2 with SHELXL-93. 21 The refinement was performed on F 2 for all reflections including those generally believed to be unobserved [F < 4σ(F)]. All non-hydrogen atoms were refined anisotropically. The crystallographic data are summarized in Table 1; selected bond distances are listed in Table 2.

R w: b 17.76% a R ) ∑||Fo| -|Fc||/∑|Fo|. b Rw ) [∑[w(Fo 2 -Fc 2 ) 2 ]/∑[w(Fo 2 ) 2 ]] 0.5 . w ) 1/[σ 2 (Fo 2 ) + (0.0975P) 2 + 0.00P] where P ) ((Fo 2 ,0) + 2Fc 2 )/3.

Results and Discussion

The structure consists of corrugated honeycomb-like layers, as shown in Figure 1. The Nd III ions occupy the corners of the edge-sharing hexagons, and the Cu II ions occupy the middles of the edges. These edges are statistically made of Cu(opba) and Cu(ox) 2 groups, with a probability of 0.5 for each of them. The average values of the Nd-Cu and Nd-Nd separations along an edge are equal to 5.9 and 10.9 Å, respectively, and the average value of the diagonal of a hexagon is equal to 19.96 and 16.31 Å for Nd-Nd and Cu-Cu directions, respectively. Each Nd III ion is located on a 3-fold axis and is surrounded by nine oxygen atoms, six of them arising from the bidentate oxamato or oxalato groups, and three of them arising from DMF molecules. The coordination polyhedron shown in Figure 2 may be described as a tricapped trigonal prism. Each Cu II ion is in a square pyramidal environment, with two nitrogen and two oxygen atoms of two oxamato groups, or four oxygen atoms of two oxalato groups in the basal plane, and an oxygen atom of a DMF molecule occupying an apical position. The apical Cu-O bond length is equal to 2.4 Å. The corrugated layers are located with regard to each other in such a way that a Nd III ion of a layer projects at the center of a hexagon belonging to adjacent layers. The interlayer separations are Nd-Nd ) 9.6 Å, Cu-Cu ) 9.9 Å, and Nd-Cu ) 9.4 Å. The variation of the magnetic susceptibility per Nd 2 Cu 3 unit, χ M , as a function of temperature, T, was measured. The results are shown in Figure 3 in the form of the χ M T versus T plot. At room temperature, χ M T is equal to 4.6 emu K mol -1 , which corresponds to what is expected for three Nd III and two Cu II ions. As the temperature is lowered, χ M T decreases more and more rapidly; the χ M T value at 2 K is 1.15 emu K mol -1 , and the value extrapolated for T approaching the absolute value is close to zero. The compound has a quasi nonmagnetic ground state. The same behavior was observed for other compounds with the Nd 2 Cu 3 topology. 22 This behavior was attributed to an almost perfect but accidental compensation at low temperature between the two Nd III and the three Cu II magnetic moments. Such a compensation may append if the ratio F ) g′ Nd /g Cu is equal or close to a critical value which has been calculated as 1.73; g′ Nd is the Zeeman factor associated with the ground Kramers doublet arising from the 4 I 9/2 ground state of Nd III , and g Cu is the Zeeman factor for the Cu II Kramers doublet. If the Nd III and Cu II magnetic moments were coupled antiferromagnetically, but without accidental compensation, the behavior would be ferrimagnetic, and χ M T would not tend to zero as T approaches the absolute zero.

Conclusion

Our efforts to synthesize a honeycomb-like compound of formula Ln 2 [Cu(opba)] 3 were partly successful. The expected topology was obtained, but half of the oxamato groups were lost and replaced by oxalato groups. All our synthetic attempts strongly suggest that the target topology could not be reached without this partial hydrolysis. The reason why the partial hydrolysis favors the honeycomb topology is not clear to us, especially as we failed to synthesize compounds with the Ln 2 -[Cu(ox) 2 ] 3 formula containing only oxalato bridges. Actually, the two structures, one consisting of parallel ladder motifs, the other consisting of a honeycomb network, are very close to each other. One can pass from the former to the latter by the displacement of one of every two rungs of the ladders in such a way as to link the ladders to each other, as emphasized in Figure 4.

  ) Gatteschi, D. AdV. Mater. 1994, 6, 635. (5) Kahn, O. AdV. Inorg. Chem. 1995, 43, 179. (6) Ferlay, S.; Mallah, T.; Ouahe `s, R.; Veillet, P.; Verdaguer, M. Nature 1995, 378, 701. (7) Entley, W. R.; Girolami, G. S. Science 1995, 268, 397. (8) Kahn, O., Ed. Magnetism: A Supramolecular Function; NATO ASI Series C; Kluwer: Dordrecht, 1996; Vol. 484. (9) Iwamura, H.; Inoue, K.; Koga, N. New J. Chem. 1998, 10, 201. (10) Proceedings of the VIth International Conference on Molecule-Based Magnets. Mol. Cryst. Liq. Cryst. 1999, 33-34. (11) Kahn, O.; Larionova, J.; Ouahab, L. Chem. Commun. 1999, 945. (12) Stumpf, H. O.; Pei, Y.; Ouahab, L.; Le Berre, F.; Codjovi, E.; Kahn, O. Inorg. Chem. 1993, 32, 5687. (13) Stumpf, H. O.; Pei, Y.; Kahn, O.; Sletten, J.; Renard, J. P. J. Am. Chem. Soc. 1993, 115, 6738. (14) Cador, O.; Price, D.; Larionava, J.; Mathonnie `re, C.; Kahn, O.; Yakhmi, J. V. J. Mater. Chem.

( 19 )

 19 STOE IPDS Software Manual V2.75; STOE and Cie: Darmstadt, 1996. (20) Sheldrick, G. M. SHELXS 86: Program for Crystal Structure Solution; Universita ¨t Go ¨ttingen: Go ¨ttingen, 1986. (21) Sheldrick, G. M. SHELXL 93: Program for Crystal Structure Refinement; Universita ¨t Go ¨ttingen: Go ¨ttingen, 1993.

Figure 1 .

 1 Figure 1. View of a layer for {Nd2[Cu(opba)0.5(ox)]3'9DMF}'4.5DMF drawn at the 35% level.

Figure 2 .

 2 Figure 2. Coordination polyedron of the Nd III ion.

Figure 3 .

 3 Figure 3. χMT versus T curve for {Nd2[Cu(opba)0.5(ox)]3'9DMF}' 4.5DMF.

Table 1 .

 1 Crystallographic

	Data for {Nd2[Cu(opba)0.5(ox)1]3'9DMF}'4.5DMF
	molecular formula:	fw: 11998
	Nd12Cu18N99O184C356H522	space group: R3 (No. 146h)
	a: 16.3144(12) Å	temp: 298 K
	c: 52.470(2) Å	radiation: Mo KR
	V: 12094(4) Å 3

Table 2 .

 2 Selected Bond Distances

	atom 1 atom 2 distance (Å) atom 1 atom 2 distance (Å)
	Nd1	O101	2.319(5)	Cu1	O13	1.892(10)
	Nd1	O102	2.554(4)	Cu1	O14	1.861(13)
	Nd1	O103	2.499(5)	Cu1B	N11B	1.880(11)
	Nd2	O201	2.661(5)	Cu1B	O12B	1.829(12)
	Nd2	O202	2.458(5)	Cu1B	O13B	2.275(2)
	Nd2	O203	2.387(5)	Cu1B	N14B	1.937(8)
	Nd3	O301	2.451(9)	Cu2	O21	2.06(3)
	Nd3	O302	2.565(5)	Cu2	O22	1.883(6)
	Nd3	O303	2.551(6)	Cu2	O23	2.011(9)
	Nd4	O401	2.582(8)	Cu2	O24	2.349(7)
	Nd4	O402	2.452(4)	Cu2B	O21B	1.761(8)
	Nd4	O403	2.483(5)	Cu2B	N22B	1.888(9)
	Cu1	O11	1.897(7)	Cu2B	N23B	1.896(8)
	Cu1	O12	2.434(5)	Cu2B	O24B	1.891(2)

STOE (DISPLAY, INDEX, CELL, PROFILE, INTEGRATE).

Acknowledgment. The "Re ´gion Bretagne" is acknowledged for its financial support.

Supporting Information Available: Detailed crystallographic data, atomic position parameters, and bond lengths and angles in CIF format. This material is available free of charge via the Internet at http://pubs.acs.org.