Pham Tran

Anh Quang

Abbas Bradai
email: abbas.bradai@univ-poitiers.fr

Deep Kamal

Singh

Yassine Hadjadj-Aoul
email: yassine.hadjadj-aoul@irisa.fr

Multi-domain non-cooperative VNF-FG embedding: A deep reinforcement learning approach

Network Function Virtualization (NFV) and service orchestration simplify the deployment and management of network and telecommunication services. The deployment of these services require, typically, the allocation of Virtual Network Function -Forwarding Graph (VNF-FG), which implies not only the fulfillment of the service's requirements in terms of Quality of Service (QoS), but also considering the constraints of the underlying infrastructure. This topic has been well-studied in existing literature, however, its complexity and uncertainty unveil many challenges for researchers and engineers. This issue is especially complex when it comes to placing a service on several non-cooperative domains, where the network operators hide their infrastructure to other competing domains. In this paper, we address these problems by proposing a deep reinforcement learning based VNF-FG embedding approach. The results provide insights into behaviors of non-cooperative domains. They also show the efficiency of proposed VNF-FG deployment approach having automatic inter-domain load balancing.

I. INTRODUCTION

Network Function Virtualization (NFV) promises to reduce the cost of deployment while allowing the operation of large network infrastructures. It provides the possibility to migrate complex network functions from dedicated hardware appliances to general purpose computing, storage, and networking solutions. This transition is also expected to provide significant benefits to the 5G mobile network architecture, by allowing flexible and scalable provisioning of new applications and network services. Moreover, since NFV allows multiple network services to share the same physical infrastructure, it enables new business models and/or economies of scale. In particular, the Network-as-a-Service (NaaS) business model is expected to play a pivotal role in 5G mobile networks, allowing Mobile Network Operators (MNOs) to tap into new revenue streams. In fact, virtualization will allow MNOs to abstract their physical network infrastructure into service specific slices, possibly operated by different mobile virtual network operators (MVNOs) [START_REF] Nakao | Application-Specific Slicing for MVNO and Traffic Characterization[END_REF] or over the top (OTT) providers.

Virtualization and adaptive network service orchestration are two of the main technical enablers that will allow Infrastructure Providers (InPs) to cope with the diverse range of requirements. This will characterize future applications and services. It is worth noticing that in this case, an InP could either be a traditional MNO that decides to open-up its networks to third parties or a new actor in the value chain that focuses only on the deployment and operation of the network infrastructure (the InP could even be a consortia of MNOs). Although a rich body of literature exists on VNF placement [START_REF] Moens | VNF-P: A model for efficient placement of virtualized network functions[END_REF], virtual network embedding [START_REF] Despotovic | VNetMapper: A fast and scalable approach to virtual networks embedding[END_REF], and component placement [START_REF] Jennings | Resource management in clouds: Survey and research challenges[END_REF], most of these works focus on the problem of mapping an input virtual network request onto a physical virtualized network substrate.

Machine learning (ML) techniques have been adopted, showing breakthroughs, in a number of application areas. One of the advantages of ML is that it can deal with complicated problems; thus it is intuitive to exploit ML in the network domain where the complex problems are common [START_REF] Wang | Machine learning for networking: Workflow, advances and opportunities[END_REF]. ML algorithms can be classified into three categories: supervised learning (SL), unsupervised learning (USL), and reinforcement learning (RL). While SL and USL focus on classification or regression tasks, RL algorithms can help in decision making and can learn to identify the best action policy in order to maximize a given objective function.

Early on, RL techniques have been exploited to solve routing optimization [START_REF] Boyan | Packet routing in dynamically changing networks: A reinforcement learning approach[END_REF]. They are also used in QoS routing [START_REF] Lin | Qos-aware adaptive routing in multi-layer hierarchical software defined networks: A reinforcement learning approach[END_REF]; however, table-based RL agents cannot provide efficient solutions for unseen network states and simply do not work in realistic environments with large actions space, which could even be infinite. Deep Reinforcement Learning (DRL) is able to cope with these issues, while overcoming the iterative improvement process of optimization and heuristics by having a DRL agent providing a near-optimal solution in one single step [START_REF] Stampa | A deep-reinforcement learning approach for softwaredefined networking routing optimization[END_REF]. Moreover, the performance of DRL has been improved by recent breakthroughs [START_REF] Li | Deep reinforcement learning: An overview[END_REF], [START_REF] Arulkumaran | A brief survey of deep reinforcement learning[END_REF]; thus paving a way for adopting DRL in the context of networking.

In this paper, we study VNF-FG deployment over noncooperative multiple domains. Each domain employs a DRL agent to learn from history of its actions and rewards. It learns a local action policy in terms of proposed prices for using its resource. A given client who requests VNF-FG embedding receives these prices and decides the final mapping between the VNFs and the substrate nodes plus links of the domains.

The rest of the paper is structured as follows. Section II reviews VNF-FG embedding and DRL in networking. Section III provides an overview of VNF-FG embedding problem. A DRL-based non-cooperative approach to deploy VNF-FGs in multi-domains is proposed in Section IV. The performance of the proposed approach is verified by simulations, presented in Section V. Finally, Section VI concludes our work.

II. RELATED WORKS

The need to dynamically deploy services on demand, through VNF-FG embedding, is identified as the core technology of 5G and post-5G networks. Therefore, this issue has been at the very centre of academic and industrial research in recent years. In this section, we review VNF-FG embedding works in single and multi-domains, as well as the use of DRL in networking and especially in VNF-FG embedding.

A. VNF-FG embedding

Different existing solutions for single domain VNF-FG embedding can be classified into two: one stage or two/multistages VNF-FG embedding. In [START_REF] Sahhaf | Network service chaining with optimized network function embedding supporting service decompositions[END_REF], [START_REF] Ye | Joint topology design and mapping of service function chains for efficient, scalable, and reliable network functions virtualization[END_REF], authors model the problem as an ILP and propose heuristics to map the virtual graph components on the physical resources, on the basis of a single stage. The main goal of these works is to maximize the revenue generated for the infrastructure providers in terms of bandwidth, computing, storage, radio and/or energy consumption. In [START_REF] Sahhaf | Network service chaining with optimized network function embedding supporting service decompositions[END_REF], authors propose a heuristic based on a backtracking mechanism, while authors in [START_REF] Ye | Joint topology design and mapping of service function chains for efficient, scalable, and reliable network functions virtualization[END_REF] take advantage of the feedback of mapping the VNF-FG to optimize the VNF-FG design. The objective of this work is to optimize the total bandwidth consumption.

The second class of single domain VNF-FG embedding solves the problem in two stages. Such that, the virtual nodes are first mapped based on certain criteria (mainly on the available resources), then the links are mapped in a second stage. Authors in [START_REF] Cheng | Virtual network embedding through topology-aware node ranking[END_REF] propose to rank and map the nodes based on a Markov random walk algorithm. They take into consideration the availability as well as the neighbors of the underlying nodes in their solution. Authors in [START_REF] Yu | Rethinking virtual network embedding: substrate support for path splitting and migration[END_REF] propose to dynamically map the virtual links into physical links based on the network conditions of the underlying network.

Recently, a few works tackled the multi-domain VNF-FG embedding [START_REF] Quang | Single and multi-domain adaptive allocation algorithms for vnf forwarding graph embedding[END_REF], [START_REF] Zhang | Service function chaining in multi-domain networks[END_REF]. In [START_REF] Zhang | Service function chaining in multi-domain networks[END_REF], the authors adopted distributed orchestrator based solutions where the local view of each orchestrator is replicated in the other orchestrators to build a global view of the network. Problems of complexity and confidentiality can be raised in such architectures. [START_REF] Quang | Single and multi-domain adaptive allocation algorithms for vnf forwarding graph embedding[END_REF] studied the cooperation between domains to determine the global optimal VNF-FG embedding. The original problem is converted into a factor graph and each domain control a part of this graph which relates to its networks. By adopting this approach, the convergence speed and the quality of solution can be enhanced.

B. Deep-reinforcement learning in networking

With Reinforcement Learning (RL), an agent learns by interacting with its environment. The agent learns to perform the best action for each state by performing actions and observing the rewards or penalties. Given enough observations, an optimal policy can be learned. Thus, the training data in reinforcement learning is a set of state-action-rewards. Some algorithms for RL are: Q-learning, State Action Reward State Action (SARSA), Deep Q-Network [START_REF] Sutton | Reinforcement learning: An introduction[END_REF], etc.

Recently, some works proposed RL-based approaches for VNF-FG embedding [START_REF] Haeri | Virtual network embedding via monte carlo tree search[END_REF] [START_REF] Mijumbi | Design and evaluation of learning algorithms for dynamic resource management in virtual networks[END_REF]. In [START_REF] Haeri | Virtual network embedding via monte carlo tree search[END_REF], authors map the VNF-FG in two stages: node mapping stage then link mapping stage.

They propose two approaches for link mapping: MaVEnM and MaVEn-S, based on Multi-Commodity Flow algorithm and the shortest-path algorithm, respectively. Regarding the node mapping, the authors propose an MDP based approach. The node mapping algorithm is called for each node embedding request. Consequently, this approach is time consuming and not adapted for real time embedding. Authors in [START_REF] Mijumbi | Design and evaluation of learning algorithms for dynamic resource management in virtual networks[END_REF] propose a multi-agent based reinforcement learning approach for virtual network embedding. These agents evaluate the feedback to learn the best policy to adopt in order to optimally allocate the required resources to the virtual nodes and links. However, they only tackle single domain scenario.

To the best of our knowledge, we are the first to propose a RL-based approach for multi-domain VNF-FG embedding.

III. VNF-FG EMBEDDING PROBLEM

In this paper, we consider a system with a number of VNF-FGs. Each VNF-FG consists of VNFs connected by virtual links. Each VNF requests a specific amount of resources, which mainly depends on the number of supported users and the type of services. The resources requested by VNFs could be the amount of central processing units (CPUs), Random Access Memory (RAM), Storage, Radio, etc. The number of resource types is K VNF . Each type of resource is indexed by 0, 1, . . . , K VNF -1. We denote h n ,k as the amount of resource k requested by VNF n and h n = [h n ,0 , ..., h n ,KVNF-1 ] as the vector of requested resources of VNF n . Without loss of generality, we consider the core network where computing tasks are major; thus the requests of VNFs are computing resources (i.e. CPU, RAM, and storage) (K VNF = 3). Note that it is expected that the proposed mechanism can be exploited with more complicated VNF resources, by extending the input of the DRL as discussed in next section. The VNFs are connected by virtual links (VLs). Each VL is characterized by K VL network oriented metrics (e.g. bandwidth, latency, loss rate, etc.). The request of metric k of VL l is denoted as h l ,k and h l = [h l ,0 , . . . , h l ,KVL-1 ] as the vector of request resources of VL l . We consider bandwidth, latency, and packet loss rate as the metrics of VLs (K VL = 3).

Let us denote the set of VNFs and VLs as N and L , then the number of VNFs and the number of VLs are |N | and |L |, respectively. The sets of nodes and links of the substrate network are N and L, therefore the number of substrate nodes and substrate links are |N | and |L|, respectively. A VNF is successfully deployed when its host has enough resources, i.e.

n φ n n h n ,k ≤ r n,k , ∀n, k (1)
where φ n n is a binary variable which is 1 if n is deployed at substrate node n and r n,k is the available amount of resource k at substrate node n. Note that each VNF is deployed at only one substrate node n; thus

n φ n n ≤ 1, ∀n . (2)
A VL is successfully deployed when its ends (VNFs) are deployed and its QoS requirements are met. We have

l φ l l h l ,bw ≤ r l,bw , ∀l, (3)
h l ,delay ≤ D(φ l ) (4)
h l ,loss ≤ R(φ l ) (5)
where φ l l is a binary variable which is 1 if l is deployed at the substrate link l, r l,bw is the available amount of bandwidth at the substrate link l, and D(φ l ) and R(φ l ) are the actual latency and loss rate corresponding to a given mapping φ l = φ l 0 , φ l 1 , ..., φ l |L|-1 . The requests of VNF-FGs are described by a 3D-array of

|N | × |N | × (2 × K VNF + K VL ). This 3D-array is a (2 × K VNF + K VL )-channel of |N | × |N | matrices.
The first K VL channel describes VLs requirements. The next 2 × K VNF channels express the resource requests of the source and destination VNFs respectively. As convolutional layers are able to extract mutual impacts between links in a network (shown in [START_REF] Pham | Deep Reinforcement Learning based QoS-aware Routing in Knowledge-defined networking[END_REF]), this form of VNF-FG requests enables us to apply convolutional layers to learn the mutual impacts between VLs.

VNF-FG requests are sent by the client who is the owner of the VNF-FG as the state to different domains. Then, each domain inputs it into a DRL network in order to determine an action which expresses the mapping of VNF-FGs to its substrate network. Even though we can define a discrete action space for this problem, its size could be enormous. For instance, each VL can be mapped to an ordered subset of substrate links, thus we have the number of actions for only

mapping VLs is |L | × k=|L| k=0 |L|! (|L|-k)! .
In [START_REF] Pham | Deep Reinforcement Learning based QoS-aware Routing in Knowledge-defined networking[END_REF], the continuous link weights were adopted as the action space of routing problems since it reduces the size of action space to |L| and improves the performance of learning process. Then, the deep deterministic policy gradient (DDPG) method was utilized to deal with continuous action space thanks to its performance [START_REF] Lillicrap | Continuous control with deep reinforcement learning[END_REF]. We exploit this idea to our problem and the action space becomes the prices proposed to the client to satisfy the request.

The price of resource m at substrate node n of VNF n is denoted as c m n,n . The price vector of VNF

n is c n = c 0,n , c 1,n , ..., c |N |-1,n , where c i,n = c 0 n,n , ..., c KVNF-1 n,n
. Therefore, it needs |N | × |N | × K VNF entries in the action to express the prices of computing resources. Moreover, we need |L | × |L| entries in the action to express the price of using a unit of bandwidth of substrate links for each VL. The price vector of VL l is c l = c 0,l , c 1,l , ..., c |L|-1,l , where c i,l is the price of a unit of bandwidth for VL l . These prices are determined by each domain, which are then sent to the client. We limit the lowest price in order to guarantee it is greater or equal to the actual deployment cost. The client who wants to deploy VNF-FGs observes the prices proposed by domains and makes a final decision so as to minimize its deployment cost. This process will be detailed in next section.

IV. MULTI-DOMAIN NON-COOPERATIVE VNF-FG EMBEDDING

A. The framework

In this section, we propose a framework for multi-domain non-cooperative VNF-FG embedding. As a non-cooperative framework, each domain does not have information of the topology as well as the available resources of other domains. Moreover, they do not communicate to each other to determine the global optimal solution. Each domain only exposes the prices of resources to the client, then the client makes a final decision based on these prices. Fig. 1 describes the framework that we propose in this paper. Recall, the state is a 3D-array representing VNF-FG requests, which is input to the DRL module present in the domain. The action determined by DRL is the price sent by a domain to the client. The client then decides where to finally embed the VNF-FG as the final action. The final action also determines the reward to different domains bidding to embed the VNF-FG. The framework comprises rounds of 3 steps:

• Step 1: The client who owns the VNF-FGs translates the requests of VNF-FGs (CPU, RAM, Storage, bandwidth, latency, and loss rate) to a 3D-array and sends it to domains. It represents the state of VNF-FGs. We assume that a unique request of VNF-FGs arrives and is also finally embedded in each round if resources are available. • Step 2: Each domain uses state to compute the action through the actor network. Note that the action of domain i (A i ) is the price proposed to the client which in turn is a function of the cost of using its resources, i.e., c k n,n , ∀n ∈ N i and c l,l , ∀l ∈ L i , where N i and L i represent, respectively, the sets of nodes and links of the substrate network of the domain i.

B. Deep RL agent model

The proposed approach adopts an off-policy, actor-critic, deterministic policy gradient algorithm (DDPG) [START_REF] Silver | Deterministic policy gradient algorithms[END_REF] RL agent that interacts with the data network through states, actions, and rewards [START_REF] Sutton | Reinforcement learning: An introduction[END_REF]. The state is the requests of VNF-FGs, which is sent by the client in step 1. Each domain determines the prices of its resources corresponding to the request and sends them to the client (step 2). Thus actions are like bids of domains for selling their resources. Client then makes the Final Decision. After receiving the Final Decision from The client observes the performance and gives the reward to domains according to their offered prices. The reward of domain i can be determined as follows

r i = n ∈N n∈Ni k∈Kc ω n n c k n,n h n ,k + l∈Li l ∈L ω l l c l,l h l ,bw (6)
where ω n n = 1 (ω l l = 1) if and only if φ n n = 1 (φ l l = 1) and the requested resources (QoS) are satisfied.

In DDPG, two neural networks are maintained to learn the policy (the actor network) and the Q-value (the critic network) separately. Fig. 2 presents the operation of DDPG algorithm. The state s t is observed by the DRL agent of each domain. An action is determined by the actor with its current parameters. This action could be added with noise N to explore the environment better. The critic network assess the advantages of an action and leads the actor to a better policy. The client collects actions of domains (bidding prices), decides a final action and executes it. Each domain receives its rewards in return to providing resources to the client. These rewards are fed into DRL agent to compute the loss and update the parameters of DRL agent.

The objective of domain i is to identify the optimal policy µ i mapping the requests of VNF-FGs to the local action A i , µ i : S → A i , that maximizes its reward presented in Eq. [START_REF] Boyan | Packet routing in dynamically changing networks: A reinforcement learning approach[END_REF]. It is done by repeatedly enhancing its knowledge of the connections between the requests, actions, and rewards through the means of deep neural network consisting in the actor and the critic networks. Meanwhile, the objective of the client is to maximize the number of allocated VNFs and VLs with the lowest cost. A lightweight heuristic algorithm will be discussed in the next section to handle this task. The actor and critic networks are composed of different layers used to extract useful information from the state as shown in Fig. 3. We use three convolutional layers (ConvLayers). The number of filters and the kernel size of ConvLayer i are C i and (F i , F i ). In addition, we add average pool layers to reduce the amount of parameters and control overfitting. The output of ConvLayers expresses the mutual impacts between VLs taking into account all properties of VLs. Also, we use Fully Connected (FC) layers to map mutual impacts to the action. The number of units of FC i is D i . Note that we also convert the action by a FC layer in the critic. After collecting the prices from the different domains (A i ), the client has to make a decision in order to deploy its VNF-FGs. While it is difficult to guarantee that a path will meet the required QoS of virtual links, it is possible to guarantee the needs of resources of VNFs. Consequently, the decision has to consider the capabilities of substrate nodes when deploying VNFs as well as the cost of deployment. We revise First Fit algorithm, a well-known resource allocation algorithm, into the Cost-based First Fit (CFF) algorithm in order to address the needs of a decision.

Alg. 1 describes the CFF algorithm. The global action A * formed by actions of domains is split into the costs related to VNFs A * ,vnf and the cost related to VLs A * ,vl . For VNF i, a dot product between the cost of VNF i (A * ,vnf [i] = c i ) and its request resource (h i ) provides the deployment cost corresponding to each substrate node (line 6). From line 8 to line 12, the substrate node that has sufficient resources and the lowest deployment cost will be selected. The client sends request to the domain D(j) which has the substrate node j. Domain D(j) checks if it can provide the resources and replies to the client. If D(j) accepts the request, CFF algorithm moves to the next VNF. Otherwise, it checks the next lowest cost substrate node. CFF algorithm continues until all VNFs are considered. The CFF algorithm outputs a mapping between VNFs and the substrate nodes. The VNF mapping obtained by CFF algorithm identifies the locations of VNFs. To map VL l , we exploit A * ,vl [l ] as the weight of links, then executing Dijkstra algorithm to find the lowest cost path of l .

V. SIMULATION RESULTS

To assess the performance of the proposed approach we use a network topology BtEurope [START_REF]The internet topology zoo[END_REF] of 24 nodes and 37 full-duplex links. The capacity of links are assigned one of following values randomly: 20 Mbps, 30 Mbps, 50 Mbps or 100 Mbps. The OMNeT++ discrete event simulator [START_REF] Varga | Discrete event simulation system[END_REF] (v5.4.1) was used to obtain the latency and packet loss rate to assess the quality of deployed VLs.

For each configuration, we execute 10 simulations with random numbers, sizes, and shapes of VNF-FGs. Each VNF-FG has from 3 to 6 VNFs and the connectivity of 0.5. The requested resources of VNFs are normalized and distributed uniformly. The amounts of available resources of each substrate node are random in the range (0.3, 2.0). Each virtual links arbitrarily requests a bandwidth in range of ; thus its mean of deployed of VLs is a bit better than of domain 1. Generally, the domain with higher resources will host more VNFs and VLs. In other words, DRL-agents are able to balancing the load between them even though they acts selfishly while determining the actions.

VI. CONCLUSIONS In this paper, we studied the multi-domain non-cooperative VNF-FG embedding problem. We introduced a framework in which each domain determines the bidding price of using its own resources selfishly, then the final decision is made by the owner of VNF-FGs by executing CFF, a light-weight heuristic algorithm. The results confirmed embedding VNF-FG in noncooperative multi-domain offers gains to the owner of VNF-FGs by reducing the bidding prices thanks to competitions between domains while the successful deployment of VNFs and VLs is slightly improved. The analysis of each domain confirmed the inter-domain load balancing capabilities in order to achieve the best performance. A thorough study will be conducted in future to compare the performance of this proposed approach with more approaches.

Fig. 1 :

 1 Fig. 1: Non-cooperative Multidomain VNF-FG embedding framework

•

  Step 3: A Final Decision is made by the client and domains are informed about it. Each domain follows the Final Decision to deploy VNFs and VLs and this final action also results in a reward for the domain.

Fig. 2 :

 2 Fig. 2: DDPG in non-cooperative multidomain VNF-FG embedding

Fig. 3 :

 3 Fig. 3: Neural networks

Fig. 7 :

 7 Fig. 7: Mean of deployed VNFs and deployed VLs of each domain the limitation in one of resources may cause the failure in deploying VNFs. Consequently, domain 2 can host more VNFs than other domains as shown in Fig. 7a. The limitations in storage resource of domain 3 prevents it from deploying VNFs, thus it can host less VNFs than domain 1. Fig.7bshows the mean of deployed VLs over time of each domain. Domain 2 has the best network capacity, thus it can host more VLs than other domains. Domain 3 has slightly better capacity than domain 1; thus its mean of deployed of VLs is a bit better than of domain 1. Generally, the domain with higher resources will host more VNFs and VLs. In other words, DRL-agents are able to balancing the load between them even though they acts selfishly while determining the actions.

1

  Mbps to 30

	Domain	1	2	3
	CPU	7.93	8.14	8.35
	RAM	8.21	8.29	8.72
	Storage	8.53	7.82	6.95
	Capacity 540 Mbps 710 Mbps 570 Mbps

TABLE I :

 I Resources of domains

Mbps, latency of 1 ms to 100 ms, and loss rate of 0% to 0.5%. An Ornstein-Uhlenbeck process is used for the exploration noise [START_REF] Lillicrap | Continuous control with deep reinforcement learning[END_REF].

Adam [START_REF] Kingma | Adam: A method for stochastic optimization[END_REF] is used for learning the neural network parameters. The learning rates of actor and critic networks are 10 -4 and 10 -3 , respectively. The discount factor γ is 0.99. The parameter of target network is updated with the coefficient of τ = 0.001. The batch size is 32. The number of units of fully-connected layers is 300. The numbers of features of 3 ConvLayers are 16, 64, and 128 respectively. The kernel sizes of ConvLayers are (4, 4), (2, 2), and [START_REF] Wang | Machine learning for networking: Workflow, advances and opportunities[END_REF][START_REF] Wang | Machine learning for networking: Workflow, advances and opportunities[END_REF].

We compare four configurations: single domain with CFF (CFF-SD), three domains with CFF (CFF-3D), simulated annealing algorithm (SA) [START_REF] Kirkpatrick | Optimization by simulated annealing[END_REF], simulated annealing algorithm with CFF (SA-CFF). First, we compare the average reward of CFF-SD and CFF-3D. The results are presented in Fig. 4a. Generally, both CFF-SD and CFF-3D are able to obtain better reward over time. In CFF-SD, there is no competition; thus the DRL agent can increase the price to the upper limit in order to achieve better rewards. In CFF-3D, each domain attempts to achieve better rewards by competing with other domains to provide resources and increasing the prices. When there are limitations of resources in several domains, there may be only one domain can host VNFs and VLs. Then, the price will increase due to the lack of competitions. We confirm the above claim by considering the average normalized price in two cases: (i) default available resources (amounts of resources of each substrate node in range (0.3, 2.0)) and (ii) high available resource (CFF-SD-HR and CFF-3D-HR) where the lower bound of available resources is 1 instead of 0.3. It means each substrate node in high available resource scenario can host at least one VNF. Fig. 4b describes the normalized prices in these scenarios. The price in CFF-SD increases faster than CFF-3D due to the lack of competitions. The normalized price in CFF-3D also increases because of the limitations of resources at substrate nodes. When we loose these limitations, the normalized price is much lower thanks to the competitions between domains (CFF-3D-HR).

Generally, CFF-3D offers lower prices than CFF-SD while providing a slightly better percentages of deployed VNFs and 5. This may be because each DRL agent in CFF-3D manages a smaller networks compare to the DRL agent in CFF-SD. Consequently, both the state and the action space of DRL agents in CFF-3D are smaller of DRL agents in CFF-SD. The smaller state and action spaces help DRL agents obtain better solutions.

The comparison of the performance of CFF-SD and CFF-3D, with SA and SA-CFF is presented in Fig. 6. Note that we consider single domain scenario when applying simulated annealing. The very large action state of VNF-FG embedding problem causes challenges for simulated annealing method in searching good solutions. Consequently, the percentage of deployed VNFs of SA is much lower than of CFF-3D and CFF-SD. CFF algorithm can help SA in finding the capable substrate nodes; however, it cannot guarantee these VNF placements can lead to a good VL deployment. Consequently, the percentage of deployed VLs of SA and SA-CFF are similar and remarkable lower than of CFF-3D and CFF-SD.

The next simulations are to confirm the load balancing capabilities of DRL-agents. Table I shows the average resources of domains. Domain 1 has the lowest CPU and RAM resources, while domain 3 has the lowest storage resource. Note that


David López-Escardó

Purificación López-García

David Moreira

Iñaki Ruiz-Trillo

Guifré Torruella

Parvularia atlantis Gen. et Sp. Nov., a Nucleariid Filose Amoeba (Holomycota, Opisthokonta)

Keywords: Protist evolution, nucleariid amoeba, protist diversity, filosea, taxonomy, phylogeny

The opisthokonts constitute a eukaryotic supergroup divided into two main clades: the holozoans, which include animals and their unicellular relatives, and the holomycotans, which include fungi, opisthosporidians and nucleariids. Nucleariids are phagotrophic filose amoebae that phenotypically resemble more their distant holozoan cousins than their holomycotan phylogenetic relatives. Despite their evolutionary interest, the diversity and internal phylogenetic relationships within the nucleariids remain poorly studied. Here we formally describe and characterize by molecular phylogeny and microscopy observations Parvularia atlantis gen. et sp. nov. (formerly Nuclearia sp. ATCC 50694), and compare its features with those of other nucleariid genera. Parvularia is an amoebal genus characterized by radiating knobbed and branching filopodia. It exhibits prominent vacuoles observable under light microscopy, a cyst-like stage, and completely lacks cilia. P. atlantis possesses one or two nuclei with a central nucleolus, and mitochondria with flat or discoid cristae. These morphological features, although typical of nucleariids, represent a combination of characters different to those of any other described Nuclearia species. Likewise, 18S rRNA-based phylogenetic analyses show that P. atlantis represents a distinct lineage within the nucleariids.

2009), also known as Nucletmycea [START_REF] Brown | Phylogeny of the "forgotten" cellular slime mold, Fonticula alba, reveals a key evolutionary branch within Opisthokonta[END_REF]. Holomycota contains Fungi [START_REF] Moore | Taxonomic proposals for the classification of marine yeasts and other yeast-like fungi including the smuts[END_REF][START_REF] Spatafora | A Phylum-Level Phylogenetic Classification of Zygomycete Fungi Based on Genome-Scale Data[END_REF], the parasitic Opisthosporidia [START_REF] Karpov | Morphology, phylogeny, and ecology of the aphelids (Aphelidea, Opisthokonta) and proposal for the new superphylum Opisthosporidia[END_REF]) and the freeliving nucleariid amoebae [START_REF] Cavalier-Smith | Kingdom Protozoa and Its 18 Phyla[END_REF]. The nucleariid amoebae comprise only two genera confirmed by molecular phylogeny. One is Nuclearia Cienkowski, 1865 [START_REF] Patterson | The genus Nuclearia (Sarcodina, Filosea): Species Composition and Characteristics of the Taxa[END_REF], which includes species with typical spherical cell morphology that feed on filamentous cyanobacteria in freshwater environments. Half a dozen Nuclearia species have been properly described, and are relatively easy to find and grow in culture conditions (e.g. [START_REF] Yoshida | Nuclearia thermophila sp. nov. (Nucleariidae), a new nucleariid species isolated from Yunoko Lake in Nikko (Japan)[END_REF]. Recently, several additional Nuclearia strains have been isolated and thoroughly studied both from morphological and molecular phylogeny standpoints. These strains harbor endo-and/or ectosymbionts, which pose interesting ecological and evolutionary questions [START_REF] Dirren | Promiscuous and specific bacterial symbiont acquisition in the amoeboid genus Nuclearia (Opisthokonta)[END_REF]. The second described genus, Fonticula, is sister to Nuclearia and contains only one species, Fonticula alba [START_REF] Worley | Fonticula alba: a new cellular slime mold (acrasiomycetes)[END_REF]). This species presents an aggregative behavior during its life cycle in which amoebae crawl together to become a multicellular fruiting body; accordingly, F. alba was first considered to be a slime mold. In addition to these two genera, another genus of filose amoebae Vampyrellidium Zopf, 1885 [START_REF] Surek | The Filose Amoeba Vampyrellidium Perforans Nov. Sp (Vampyrellidae, Aconchulinida): Axenic Culture, Feeding Behaviour and Host Range Specifity[END_REF][START_REF] Patterson | The Ultrastructure of Vampyrellidium Perforans Surek & Melkonian and Its Taxonomic Position Among the Naked Filose Amoebae[END_REF]) has been morphologically associated with nucleariids. Vampyrellidium has only two species described. However, these species are not available in culture and we lack sequenced molecular markers for them. In addition to a phagocytic feeding mode, Vampyrellidium amoebae are able to penetrate the cell wall of algae using a specialized flattened pseudopodium. Other genera morphologically associated to nucleariids (no sequences available) are the scale-bearing Pinaciophora Greef, 1869, Pompholyxophrys Archer 1869 and Lithocolla Shulze 1874 [START_REF] Mikrjukov | Taxonomic Revision of Scale-Bearing Heliozoon-like Amoebae (Pompholyxophryidae, Rotosphaerida)[END_REF].

Morphologically, all nucleariid genera lacking scales (Nuclearia, Fonticula and Vampyrellidium) consist of non-flagellated amoebae, with radiating thin hyaline pseudopods (i.e., branching filopodia). Cell shape is typically spherical when floating and flattened when adhering to the substrate although these amoebae are extremely plastic and can adopt elongated forms. The cytoplasm contains one or more prominent nuclei, dictyosomes, mitochondria with flat cristae and at least one big digestive vacuole that can occupy most of the cell body. Cysts have also been observed in some Nuclearia species (N. pattersoni, N. simplex and N. rubra) [START_REF] Yoshida | Nuclearia thermophila sp. nov. (Nucleariidae), a new nucleariid species isolated from Yunoko Lake in Nikko (Japan)[END_REF]) and in F. alba, but not in Vampyrellidium perforans. Nucleariids differ widely from other holomycotan lineages, such as the parasitic Opisthosporidia [START_REF] Karpov | Morphology, phylogeny, and ecology of the aphelids (Aphelidea, Opisthokonta) and proposal for the new superphylum Opisthosporidia[END_REF], the ancestor of which was most likely able to penetrate cell walls of various eukaryotic species to phagocytize them; or the ancestrally osmotrophic fungi, which feed by secreting extracellular enzymes to process complex food sources and absorb simpler molecules [START_REF] Richards | Horizontal gene transfer in osmotrophs: playing with public goods[END_REF].

The systematics of the nucleariid filose amoebae is still not clear. In addition, other amoebae have been proposed to be candidate "nucleariids" based solely on morphological characters [START_REF] Mikrjukov | Taxonomic Revision of Scale-Bearing Heliozoon-like Amoebae (Pompholyxophryidae, Rotosphaerida)[END_REF][START_REF] Patterson | Amoebae of Uncertain Affinities. An illustrated guide to the Protozoa[END_REF]. Molecular phylogenetic analyses place the nucleariid amoebae in a pivotal position as an early-branching lineage close to the root of the Opisthokonta, which makes this group of primal importance to understand the early evolution of this eukaryotic supergroup. Therefore it is essential to have first a robust reference phylogenetic tree with the widest possible representation of the diversity of the lineages involved. The starting point of this process is accurately describing species and placing them in a molecular phylogenetic framework. In this study, we describe the isolate called Nuclearia sp. ATCC 50694, which we classify into the new genus and species Parvularia atlantis gen. et sp. nov. Together with several environmental sequences, this genus represents the sister lineage to Nuclearia.

Material and Methods

Culturing Parvularia atlantis

The original strain was obtained from the American Type Culture Collection (ATCC, Teddington, UK) under the name Nuclearia sp. ATCC 50694, deposited by TK Sawyer and originally isolated in 1997 from a freshwater sample in Atlanta, GA, USA (see comments on the taxonomic description section for a list of papers where this species was used under this undetermined name). The culture grows in liquid ATCC Medium 802 (Sonneborn's Paramecium medium) bacterized with Klebsiella pneumoniae subsp. pneumoniae (ATTC 700831). Cultures were grown and monitored at room temperature during several weeks, usually up to a month, before transferring them to fresh medium.

Molecular phylogenetic analyses

The sequence of the Parvularia atlantis small subunit ribosomal gene (18S rRNA gene) was obtained after RNA extraction using TRizol reagent™ (Invitrogen, Carlsbad, CA, USA) and retrotranscription with Superscript® II (Invitrogen) using the 18S rRNA reverse primer Euk-B (5′-GATCCTTCTGCAGGTTCACCTAC-3′) [START_REF] Medlin | The Characterization of Amplified Eukaryotic 16S-like rRNA-Coding Regions[END_REF]. Two overlapping fragments of the 18S rRNA gene were subsequently amplified by PCR using the primer combination A (5′-AACCTGGTTGATCCTGCCAGT) with 1055R (5′-CGGCCATGCACCACC); and 528F (5′-CGGTAATTCCAGCTCC) with B (5′-TGATCCTTCTGCAGGTTCACCTAC) [START_REF] Medlin | The Characterization of Amplified Eukaryotic 16S-like rRNA-Coding Regions[END_REF][START_REF] Carr | Molecular Phylogeny of Choanoflagellates, the Sister Group to Metazoa[END_REF]. The amplified DNA fragments were cloned (TOPO TA, Invitrogen) and Sanger sequenced (Genomics facility UPF, Barcelona, Spain). We obtained a consensus 18S rRNA gene sequence of 1,675 bp deposited in GenBank with accession number KY113120. Next, we compared its sequence identity to other nucleariid representative sequences: Fonticula alba FJ816018, Nuclearia pattersoni AY364635 and Nuclearia thermophila AB433328, using BLASTn pairwise alignments. We included this sequence in an 18S rRNA dataset containing sequences from known nucleariid species and all available environmental nucleariid sequences identified in GenBank. To retrieve the latter, we carried out BLAST+ [START_REF] Camacho | BLAST plus: Architecture and Applications[END_REF]) searches with the four mentioned nucleariid sequences as queries and retrieved the 200 first hits for each one. We merged all the hits and extracted all unique sequences to build a phylogenetic tree together with representative sequences of opisthokonts and other eukaryote groups (i.e. Apusomonadida, Breviatea, Amoebozoa, SAR, Archaeplastida and Excavata) to verify the ascription of these sequences to the nucleariids. Once we identified all nucleariid sequences, we discarded most outgroup and identical nucleariid clone sequences. We then defined operational taxonomic units (OTUs) applying a 98% identity threshold and retained the longest sequence for each OTU. We also included four environmental sequences from a recent molecular survey of freshwater systems [START_REF] Simon | Marked Seasonality and High Spatial Variability of Protist Communities in Shallow Freshwater Systems[END_REF], and 85 marine environmental sequences with nucleariid affinity from the BioMarks project [START_REF] Del Campo | Diversity and distribution of unicellular opisthokonts along the European coast analysed using high-throughput sequencing[END_REF]. Our final 18S rRNA dataset comprised a total of 131 sequences (see Table S1). We aligned them using MAFFT [START_REF] Katoh | MAFFT: a novel method for rapid multiple sequence alignment based on fast Fourier transform[END_REF] with the E-INS-i algorithm and obtained a multiple sequence alignment of 2,348 sites. After manually trimming sequence ends, indels and spuriously aligned sites we ended up with a total of 1,595 sites. We inferred phylogenetic trees from this alignment using both Bayesian Inference (BI) and Maximum Likelihood (ML) methods. We performed BI analysis with MrBayes 3.2.6 [START_REF] Ronquist | MrBayes 3: Bayesian phylogenetic inference under mixed models[END_REF] using the GTR model of nucleotide substitution, taking into account rate variation amongst sites with a gamma distribution (approximated by four categories) plus an invariable sites category. Four chains ran for 4,400,000 generations and were analyzed after a burn-in of 25%. For ML analyses, we used RAxML v8 [START_REF] Stamatakis | RAxML version 8: a tool for phylogenetic analysis and post-analysis of large phylogenies[END_REF]) with the same model parameters as in the Bayesian analysis to search for the best tree out of a thousand, and to perform 1000 non-parametric bootstraps. All trees were visualized using FigTree v1.4.2 (http://tree.bio.ed.ac.uk/software/figtree/) and modified with Inkscape vector graphics software (inkscape.org). The trimmed alignment and phylogenetic trees can be found in https://figshare.com/s/1b8a7f7806816eb0e1c1.

Light Microscopy

Differential interference contrast images (DIC) were taken in an Axioplan 2 microscope with DIC objective Plan-NEOFLUAR 100x/ 1.3 oil (Zeiss, Goettingen, Germany) and captured with the software AxioVision v4.8.2. Phase contrast (PH) images were taken in an Axio Observer.Z1 microscope with 63x objective Plan-Apochromat 63x/1.4 oil (Zeiss) and captured with ZEN software v2012. Images obtained were edited with Fiji v1.47 [START_REF] Schindelin | Fiji: an open-source platform for biological-image analysis[END_REF]. Time-lapses at low magnification (400x) were done on a Nikon Eclipse TS100 microscope (Nikon, Tokyo, Japan). Movies can be found in https://figshare.com/s/ 1b8a7f7806816eb0e1c1.

Transmission electron microscopy

An actively growing culture (15 days old) was centrifuged at 10,000 g during 5 minutes at 10 ºC. Lower speeds for extended times did not produce concentrated pellets suitable for posterior observation. Samples were cryoimmobilized using a Leica EMPACT High-Pressure Freezer (Leica Microsystems, Vienna, Austria). Planchettes containing the frozen samples were transferred to cryotubes containing 2% OsO 4 (EMS, Hatfield, PA, USA) 0.1% uranyl acetate (EMS) in acetone under liquid nitrogen and freeze-substitution was performed at -90 °C for 85 h in a EM AFS (Leica Microsystems). Samples were warmed up to 4 °C with a rate of 5 °C/h, kept at 4 °C for 2 h, and then they were transferred to room temperature and kept for 2 h in darkness. They were rinsed with acetone, then infiltrated and embedded in Epon-812 resin (EMS). Sample sections of 60 nm in thickness were obtained using a UCT ultramicrotome (Leica Microsystems), and then stained with methanolic 2% uranyl acetate and lead citrate. Sections were observed in a Tecnai Spirit microscope (EM) (FEI, Eindhoven, The Netherlands) equipped with a LaB6 cathode. Images were acquired at 120 kV with a 1376 x 1024 pixel CCD camera (FEI).

Scanning electron microscopy

As above, we used an actively growing culture (15 days old). The bottom of the culture flask was scrapped softly in order to obtain both adherent and floating cells. Cells were fixed by adding directly 250 μl of OsO 4 4% (Sigma-Aldrich, Saint Louis, MO, USA). The sample remained 90 minutes in the dark, and the solution was passed through a Whatman Nucleopore filter membrane (0.8 μm pore-diameter filter, previously treated with Poly-LLysine (Sigma-Aldrich)) to capture the fixed cells. The filter was submerged overnight at 4 ºC in phosphate buffer saline (PBS, 0.01 M phosphate buffer saline, NaCl 0.138M, KCl 0.0027M at pH 7.4, Sigma-Aldrich). Then the sample was dehydrated through a graded ethanol series (30%, 50%, 70%, 80%, 90%, 95% (twice) and 100% (twice) for 15 minutes each), critical point dried with CO 2 (Critical Point Dryer, Bal-Tec CPD 030) and sputtercoated with gold. Finally, the sample was examined under a Hitachi S-3500 N microscope (Hitachi, Tokyo, Japan) operating at 5 kV.

Fluorescent cell staining

The bottom of a 15-days old culture was carefully scraped and 2 ml were transferred to a glass bottom dish (LabClinics, Barcelona, Spain) for confocal microscopy observation. The culture was left overnight in order to let Parvularia atlantis cells properly adhere to the bottom of the dish. Then the medium was removed by pipetting carefully and cells were fixed with 6% acetone and 4% formaldehyde for 5 minutes. Cells were rinsed with PBS for 5 minutes prior to the addition of a solution containing Alexa Fluor®phalloidin 488 (Thermo Scientific, Waltham, MA, USA) and DRAQ5 (Thermo Scientific) in the following proportions: 1/40 and 1/100. Cells were incubated with the dyes for 30 minutes in dark conditions. After two PBS washes, the samples were mounted with Dako medium (Agilent Technologies, Santa Clara, CA, USA) for microscopy observation on a Leica TC5 SP5 confocal microscope (Leica microsystems, Germany).

Results

Morphological observations

Parvularia atlantis gen. et sp. nov. (formerly Nuclearia sp. ATCC 50694) presents two different cellular forms in our culture conditions: amoeba and cyst-like. These forms are not easy to distinguish using low magnification (200x and 400x). In order to reveal particular cellular structures of each form we imaged P. atlantis at 630x and 1000x magnification using light microscopy, with phase contrast (PH) and differential interference contrast (DIC) techniques. We also carried out transmission and scanning electron microscopies (TEM and SEM).

Parvularia atlantis cells are filose amoebae with a quasi-spherical cell body (Fig. 1A). Cell diameter (without pseudopodia) varies between 3.36 and 5.92 μm with a mean of 4.34 μm; n = 114 cells. Filopodia radiate from the cell body in all directions, often branching but never anastomosing. Although density, length and direction can be variable, short filopodia are abundant and long ones are scarce and several times longer than the cell body (Fig. 1B,C,S1A). Phalloidin staining, applied for the first time in nucleariids, clearly showed the actinbased cytoskeleton extending inside these long fine filamentous pseudopods in fixed P. atlantis cells (Fig. 1D,S2). Cells can be floating or attached to the substrate either by the whole cell body (Fig. 1B) or only by the filopodia (Fig. 1C). When amoebae cells are fully attached, they can adopt elongated crawling forms (Fig. 1B,S1B). Light microscopy images show that P.atlantis amoeboid cells can have two nuclei (Fig. 1E). The nuclei contain a clearly visible central nucleolus (Fig. 1F). Furthermore, amoebae present a big vacuole (Fig. 1G,S1B) and several smaller vesicles. P. atlantis cells feed on rod-shaped bacteria. Amoebae cells often appear surrounded by many bacterial cells (Fig. 1H, Movie S1), with a kind of halo between the amoebae and the bacteria.

Cyst-like forms are also frequent in P. atlantis cultures. This cyst-like form is spherical as seen both in PH and DIC, with a thicker silhouette and a bright side in opposition to an intense shadow, respectively, and lacks filopodia. In consequence, cysts do not attach but float or rest on the substrate (Fig. 1I,S1C,D). The cyst cell is less translucent than in amoebae preventing a good observation of its content, although sometimes vesicles can be seen in DIC and PH. Time-lapse videos (Movie S2) show that while amoebae actively crawl on the surface feeding on bacteria, cyst-like forms remain still, without active movement. These videos also show a transition from a cyst-like to the active amoeba form (Movie S3). Transmission electron microscopy (TEM) images from centrifuged cyst-like forms always show an extracellular envelope; i.e., a cell wall separated from the main cell body (Fig 2). The limited quality of our TEM observations revealed few details of the P. atlantis ultrastructure. Basically, all cells have a big vacuole and some smaller vesicles (Fig. 2A) and the few mitochondria observed in detail had flat or discoidal cristae (Fig. 2C). Also, TEM observations provided snapshots of cell division, probably closed since nuclear membranes are always intact (Fig. 2B, D-F). Interestingly, the cell in Fig. 2D shows the cleavage furrow, and Fig. 2F and2E show two and three cells within the same extracellular envelope. No other ultrastructural cell features, such dictyosomes or microtubules, were observed.

Molecular phylogeny

We determined the P. atlantis 18S rRNA gene sequence, which was 92%, 89% and 86% identical to Nuclearia pattersoni (AY364635), N. thermophila (AB433328) and Fonticula alba (FJ816018), respectively. Logically, pair-wise identity between N. pattersoni and N. thermophila was the highest: 95%. The similarity between F. alba and N. pattersoni and N. thermophila was much lower, 90% and 91%, respectively. The multiple sequence alignment showed that all available Nuclearia 18 rRNA sequences exhibit two exclusive insertions in the variable regions V4 and V7, absent in the sequences from P. atlantis, F. alba and the rest of opisthokont lineages (Fig. S3).

Then, we inferred the phylogenetic position of P. atlantis by reconstructing an 18S rRNA gene tree (Fig. 3). After mining different databases (see methods), we retrieved all publicly available nucleariid 18S rRNA gene sequences, including both cultured species and environmental sequences, in order to use the broadest possible molecular diversity. Maximum Likelihood (ML) and Bayesian Inference (BI) analyses of the gathered dataset resulted in the same backbone for the opisthokont phylogenetic tree. The statistical support for the monophyly of the nucleariids was high in BI analysis (0.96 posterior probability (pp)) but weak in ML trees (only 23% bootstrap support (bs)); see Fig. 3, S4, S5. Yet, this topology agreed with previous phylogenomic analyses where Nuclearia spp. and F. alba [START_REF] Liu | Phylogenomic analyses predict sistergroup relationship of nucleariids and fungi and paraphyly of zygomycetes with significant support[END_REF]) on the one hand, and F. alba and P. atlantis ("Nuclearia sp. ATCC 50694") on the other hand [START_REF] Torruella | Phylogenomics Reveals Convergent Evolution of Lifestyles in Close Relatives of Animals and Fungi[END_REF], branched together. In our phylogenetic analyses (Fig. 3), F. alba was sister to the marine environmental clade called MAFO (del Campo et al. 2015).

However, the low statistical support for this relationship (0.62 pp and 14% bs) did not allow to reliably conclude the monophyly of the two groups. The Nuclearia clade, with a better statistical support (0.98 pp and 61% bs), contained all the Nuclearia species for which the 18S rRNA gene sequence is available plus some related environmental sequences. In addition, a group of four environmental nucleariid sequences (env NUC-1) branched as sister of Nuclearia spp. (Fig. 3, S3, S4). The Parvularia clade, previously referred to as FRESHOP (see del Campo and Ruiz-Trillo 2013), contains not only the species described in this study but also five environmental sequences forming a clear monophyletic group with high statistical support (1.0 pp and 100% bs). In our tree, the Parvularia clade branched within a group of environmental nucleariid sequences (env NUC-2), albeit with very low statistical support (0.81 pp and 16% bs).

Discussion

Our 18S rRNA gene phylogenetic analysis clearly show that Parvularia atlantis gen. et sp. nov. represents a distinct phylogenetic lineage from the other described nucleariids (Fig. 3). This is further supported by the fact that the Parvularia 18S rRNA gene sequence shares similar low pairwise identities with Fonticula and Nuclearia spp. and does not show the V4 and V7 insertions present in Nuclearia sequences (Fig. S3). All these results concur to support the erection of the new genus Parvularia. This is important, because the characterization of this new genus enriches the limited diversity known for the group and helps clarifying the taxonomy and phylogeny of the nucleariids. P. atlantis was originally deposited without formal description as Nuclearia sp. ATCC 50694, then sequenced and tentatively named as such [START_REF] De Mendoza | Transcription Factor Evolution in Eukaryotes and the Assembly of the Regulatory Toolkit in Multicellular Lineages[END_REF][START_REF] Suga | Earliest Holozoan Expansion of Phosphotyrosine Signaling[END_REF][START_REF] Torruella | Phylogenomics Reveals Convergent Evolution of Lifestyles in Close Relatives of Animals and Fungi[END_REF]. The misidentification of opisthokont amoebae as Nuclearia sp., followed by their reclassification after molecular phylogenetic analysis, is not infrequent. For instance, the filasterean Capsaspora owczarzaki was initially described as Nuclearia sp. [START_REF] Zettler | The Nucleariid Amoebae: More Protists at the Animal-Fungal Boundary[END_REF] until it was properly placed as a unicellular holozoan relative of animals [START_REF] Hertel | The symbiont Capsaspora owczarzaki, nov. gen. nov. sp., isolated from three strains of the pulmonate snail Biomphalaria glabrata is related to members of the Mesomycetozoea[END_REF][START_REF] Ruiz-Trillo | Capsaspora Owczarzaki Is an Independent Opisthokont Lineage[END_REF]). Regarding the diversity of nucleariids, our data show that, in addition to Fonticula, Nuclearia and Parvularia, there are other nucleariid groups currently composed only by environmental sequences, such as the marine MAFO (del Campo et al. 2015) and the freshwater env-NUC1 and env-NUC2 (Fig. S4,S5). These environmental groups likely correspond to undescribed genera, highlighting a wider diversity than previously thought for the group. Determining the proper phylogenetic boundaries of nucleariids, also requires the molecular study of other filose amoebae of uncertain affinities, e.g., genera such Vampyrellidium, Pinaciophora, Pompholyxophrys or Lithocolla (Mirkjukov 1999[START_REF] Patterson | Amoebae of Uncertain Affinities. An illustrated guide to the Protozoa[END_REF]. As mentioned before, without molecular phylogenetic data, some genera of filose amoebae have been originally assigned to nucleariids based on morphology (e.g., Cavalier-Smith and Chao 2012) but subsequently shown to be members of other eukaryotic supergroups, such the rhizarian vampyrellids [START_REF] Hess | Shedding light on vampires: the phylogeny of vampyrellid amoebae revisited[END_REF]; not to confuse with Vampyrellidium Zopf, 1885 [START_REF] Surek | The Filose Amoeba Vampyrellidium Perforans Nov. Sp (Vampyrellidae, Aconchulinida): Axenic Culture, Feeding Behaviour and Host Range Specifity[END_REF]. Finally, our 18S rRNA phylogenetic results show limited phylogenetic signal (Fig. 3, S4, S5), so in order to confirm the monophyly of nucleariids and to properly solve their internal evolutionary relationships, more markers and more isolates should be included in phylogenetic analyses.

Phenotypic traits used to classify nucleariids may be inadequately defined or differently interpreted by distinct researchers. Recently, Dirren and Posch [START_REF] Dirren | Promiscuous and specific bacterial symbiont acquisition in the amoeboid genus Nuclearia (Opisthokonta)[END_REF] noted that all morphological characters typically associated with the genus Nuclearia can be observed or not depending on the culture and observation conditions. For example, the cell size can vary during long culture periods. Morphologically, P. atlantis clearly resembles a nucleariid, but differs from all previously characterized nucleariid species in several of the features traditionally used for Nuclearia classification [START_REF] Patterson | The genus Nuclearia (Sarcodina, Filosea): Species Composition and Characteristics of the Taxa[END_REF][START_REF] Yoshida | Nuclearia thermophila sp. nov. (Nucleariidae), a new nucleariid species isolated from Yunoko Lake in Nikko (Japan)[END_REF]). One of the most obvious differences refers to the size range: Vampyrellidium perforans ranges from 4 to 25 μm, the smaller F. alba from 7 to 13 μm, and Nuclearia spp. from a few to a hundred micrometres. In fact, the smallest described Nuclearia species (for which sequence data are not available) is N. leuckarti (cell diameter around 10 μm or less) [START_REF] Yoshida | Nuclearia thermophila sp. nov. (Nucleariidae), a new nucleariid species isolated from Yunoko Lake in Nikko (Japan)[END_REF]). However, P. atlantis never reaches cell sizes over 6 microns, even in elongated forms (Fig. 1B,S1B). In addition, P. atlantis presents a cyst-like form, and cells can contain two nuclei, features that are not found in N. leuckarti. Other Nuclearia species for which we also lack sequence data, such as N. polypodia, N. flavescens, N. radians, N. flavocapsulata and N. rubra, are all described as uninucleate, and only the latter was described as able to form cysts. Even the genus Vampyrellidium [START_REF] Surek | The Filose Amoeba Vampyrellidium Perforans Nov. Sp (Vampyrellidae, Aconchulinida): Axenic Culture, Feeding Behaviour and Host Range Specifity[END_REF] seems to be morphologically more similar to Nuclearia species than to Parvularia, being uninucleate, around 20 μm in cell diameter and unable to encyst. Therefore, P. atlantis is molecularly and morphologically divergent from any nucleariid species known so far. Associating unambiguous morphological features to species confidently placed in molecular phylogenetic trees is crucial to understand macroevolution. Phenotypic characters shared by P. atlantis and other nucleariids can be used to reconstruct ancestral character states for this group. For example, P. atlantis shares many features with other nucleariids. All of them are plastic amoebae with branching filopodia that can have spherical to flattened cell shapes [START_REF] Surek | The Filose Amoeba Vampyrellidium Perforans Nov. Sp (Vampyrellidae, Aconchulinida): Axenic Culture, Feeding Behaviour and Host Range Specifity[END_REF][START_REF] Patterson | The genus Nuclearia (Sarcodina, Filosea): Species Composition and Characteristics of the Taxa[END_REF][START_REF] Brown | Phylogeny of the "forgotten" cellular slime mold, Fonticula alba, reveals a key evolutionary branch within Opisthokonta[END_REF][START_REF] Yoshida | Nuclearia thermophila sp. nov. (Nucleariidae), a new nucleariid species isolated from Yunoko Lake in Nikko (Japan)[END_REF]). The prominent nucleus with a conspicuous central nucleolus is also a common feature in Vampyrellidium perforans (Fig. 16 in [START_REF] Surek | The Filose Amoeba Vampyrellidium Perforans Nov. Sp (Vampyrellidae, Aconchulinida): Axenic Culture, Feeding Behaviour and Host Range Specifity[END_REF], Fonticula alba (Fig. 2B in [START_REF] Brown | Phylogeny of the "forgotten" cellular slime mold, Fonticula alba, reveals a key evolutionary branch within Opisthokonta[END_REF]) and most Nuclearia species (Yoshida et al. 2011). P. atlantis amoeba stage can be binucleated as also described in F. alba, N. delicatula, Nuclearia sp. strain A5 and N. thermophila [START_REF] Dirren | Promiscuous and specific bacterial symbiont acquisition in the amoeboid genus Nuclearia (Opisthokonta)[END_REF]. The presence of cysts or cyst-like forms is also recurrent in nucleariids, and assumed to be ancestral in Nuclearia spp. [START_REF] Dirren | Promiscuous and specific bacterial symbiont acquisition in the amoeboid genus Nuclearia (Opisthokonta)[END_REF]. Since F. alba and P. atlantis also produce cysts or cyst-like structures (Fig. 1I, S1C, S1D), we can assume that this capacity is ancestral to the whole nucleariid group. The ontology of these cysts has never been studied in detail. Whether they represent a resting or dormant form under adverse conditions, a digestive form that does not need filopodia to prey, or a sexual (i.e., sporocyst) or division stage of the life cycle, is unknown. In P. atlantis, light microscopy observations suggest that cyst-like forms are passively motile. Unfortunately, the cell body is opaque, such that inner activity cannot be monitored (e.g., live staining molecules such phalloidin do not penetrate). On the other hand, TEM images show that cyst-like forms, with a dense cell envelope (i.e., cell wall), can be in process of division (Fig. 2B,D,F). It is worth mentioning that despite the lack of molecular data for Nuclearia spp., it seems unlikely that any of these coats could contain chitin as in other holomycotan lineages [START_REF] James | No jacket required--new fungal lineage defies dress code: recently described zoosporic fungi lack a cell wall during trophic phase[END_REF], since the necessary chitin synthase classes were not found in genomic data of F. alba and transcriptomic data of P. atlantis [START_REF] Torruella | Phylogenomics Reveals Convergent Evolution of Lifestyles in Close Relatives of Animals and Fungi[END_REF]. Both the cell wall composition and cyst-like state physiology should be further explored in nucleariids. Another interesting external character in nucleariids is the secretion of extracellular material embedding the trophic cells. In F. alba, this extracellular material is used to build the elevated stalk that constitutes the multicellular fruiting body [START_REF] Deasey | Role of Golgi Apparatus in Sorogenesis by the Cellular Slime Mold Fonticula alba[END_REF], and in Nuclearia spp. it has been recently proposed to host symbiotic bacteria that may protect the amoeba from cyanobacterial toxins [START_REF] Dirren | Promiscuous and specific bacterial symbiont acquisition in the amoeboid genus Nuclearia (Opisthokonta)[END_REF]. In P. atlantis, the presence of this extracellular coat is not clear. Amoebae in culture conditions are often surrounded by a translucent perimeter space surrounded by bacteria (Fig. 1H). Although observations under higher magnification have not clearly revealed a mucus sheath as seen in other nucleariids, it can be hypothesized that P. atlantis produces hyaline extracellular material under particular conditions.

In summary, we can conclude that the last common ancestor of nucleariid-like genera was an unciliated amoeboid cell with thin branching filopodia, binucleated and encysted at some point of its life cycle. To further validate such evolutionary scenario, further cultivation, description and molecular phylogenetic identification of new nucleariids will be needed. Even without culturing, cell isolation followed by transcriptome or genome sequencing by the use of single cell 'omics' techniques will increase the data needed to perform thorough comparative studies between extant living species. Linking phenotypes and genotypes of protists representing a good taxonomic sampling will help unveiling the deep history of opisthokont evolution.

Taxonomical description

Based on the presented data we formally describe the Nuclearia sp. Spherical cell, diameter between 3 to 5 μm excluding the pseudopodia. Fine hyaline pseudopods radiate from any part of the cell body in variable density, length and direction, usually branching, never anastomosing. It feeds upon rod-shaped bacterial cells, not being able to feed on large cells such filamentous cyanobacteria or algae as Nuclearia spp. do.

Slow motile trophic cells are uni-or binucleated with a big vacuole occupying most of the cell volume and smaller vesicles. Nuclei with a clearly visible central nucleolus. Cyst-like form has spherical shape embedded within a more or less opaque cell wall. Mitochondria with flat cristae.

  ATCC 50694 strain as a new genus and species, Parvularia atlantis López-Escardó & Torruella, gen. et sp. nov. within Nucleariidae, Holomycota, Opisthokonta. Parvularia López-Escardó & Torruella, gen. nov. Fresh-water free-living nucleariid: small spherical to elongated filose amoeba with cyst-like forms. Phylogenetically distant from Fonticula and Nuclearia genera, 18S rRNA gene sequence having less than 95% pair-wise identity with Fonticula and Nuclearia sequences and lacking the V4 and V7 insertions characteristic of Nuclearia spp. Etymology: Parvularia, from Latin Parvus (small); related to Nuclearia. Type species: P. atlantis López-Escardó & Torruella sp. nov. Zoobank registration: urn:lsid:zoobank.org:act:D177D3E9-09A8-46ED-91C2-BE1A33881F7C Parvularia atlantis López-Escardó & Torruella sp. nov.

Fig. 1 .

 1 Fig. 1. Morphology of Parvularia atlantis gen. et sp. nov. (A) living culture observed by light microscopy (phase contrast, 630x), the arrow indicates the cyst-like form, the other cells are amoebae. (B) Adherent filose amoeba, arrows indicate branching filopodia (DIC, 1000x). (C) Filopodia of P. atlantis cells attached to the slide bottom (DIC, 1000x). (D) Composite of 4 images (630x magnification) taken at different focus distances in order to represent together the different cell planes of filose amoebae stained with Phalloidin Alexa Fluor® 488 (related to Fig. S1 in supplementary material). (E) Amoeba with two nuclei

Fig. 2 .

 2 Fig. 2. Ultrastructure of Parvularia atlantis gen. et sp. nov cyst-like forms. (A) Cyst-like cell with the extracellular coat (arrow). (B) Cell with two nuclei. (B, D, F) Cell division in cystlike forms. (C) Mitochondrion with flat or discoid cristae. (D) Cell undergoing cytokinesis. (F) Two cells within the same extracellular coat. (E) Three cells under the same extracellular coat. Mitochondrion (m), nucleus (n), vacuole (v). Scale bar = (A, B, D, E, F) 500 nm; (C) 200 nm.

Fig. 3 .

 3 Fig. 3. 18S rRNA gene-based Bayesian phylogenetic tree showing the position of Parvularia atlantis gen. et sp. nov. The tree contains a representation of opisthokonts as outgroups and all nucleariid OTUs retrieved from GenBank. The tree was inferred using 1,595 conserved nucleotide positions. Statistical supports are shown only at deep nodes; Bayesian posterior probabilities (pp) are displayed on the left and Maximum Likelihood bootstrap (bs) values on the right. Black dots represent supports higher than 0.8 pp and 70% bs.

J Eukaryot Microbiol. Author manuscript; available in PMC 2019 March 01.

Acknowledgments

Research leading to these results received funding from the European Research Council under the European Union's Seventh Framework Program ERC Grant Agreement 322669 "ProtistWorld". IRT acknowledges support by ICREA, a European Research Council Consolidator (ERC-2012-Co-616960) grant, a grant (BFU2014-57779-P) from Ministerio de Economía y Competitividad (MINECO) and FEDER funds. IRT and DLE also acknowledge financial support from Secretaria d'Universitats i Recerca del Departament d'Economia i Coneixement de la Generalitat de Catalunya (Project 2014 SGR 619). GT has been funded by the European Marie Sklodowska-Curie Action (704566 AlgDates). The authors want to acknowledge the original isolators of the Nuclearia sp. ATCC 50694, Xavi Florenza for electron microscopy manipulation; Sergey Karpov, Yana Eglit and Alastair Simpson for ultrastructure discussion; Helena Parra for confocal microscopy manipulation; and the anonymous reviewers for their constructive criticism and corrections.

Etymology: atlantis, from Atlanta (Georgia, USA), name of the original isolation site. Type: Fig. 1 López-Escardó et al., this publication. Nuclearia sp. ATCC 50694 strain was informally deposited in culture collection on 1997 by TK Sawyer. As reported by the culture collection: it was isolated from a liquid freshwater sample obtained by Barry Fields in the CDC, Atlanta, 339 Georgia, USA. Comments: This organism was originally submitted as Nuclearia sp. to the American Type Culture Collection, so this undetermined name was tentatively used in the RNAseq BioSample SRS725006 and in previous articles (de [START_REF] De Mendoza | Transcription Factor Evolution in Eukaryotes and the Assembly of the Regulatory Toolkit in Multicellular Lineages[END_REF][START_REF] Suga | Earliest Holozoan Expansion of Phosphotyrosine Signaling[END_REF][START_REF] Torruella | Phylogenomics Reveals Convergent Evolution of Lifestyles in Close Relatives of Animals and Fungi[END_REF]. The authors have tried to contact the people who originally isolated it without success; therefore more details on its ecological origin could not be clarified. Gene sequence data: The nearly complete 18S rRNA sequence has been deposited in GenBank under Accession Number KY113120.

Supporting Information

Refer to Web version on PubMed Central for supplementary material.