Alexandros Kostopoulos

Ioannis P Chochliouros
email: ichochliouros@oteresearch.gr

Daniele Munaretto

Claudio Meani

Claus Keuker

Elisenda Temprado Garriga

Javier Fernandez Hidalgo

Miguel Catalan Cid

Hicham Khalifé

Fidel Liberal

Elisenda Temprado Garriga

Hicham Khalife

Use Cases for 5G Networks Using Small Cells

Keywords: Cloud-enabled Small Cell (CESC), Mobile Edge Computing (MEC), Network Functions Virtualization (NFV), Radio Resource Management (RRM)

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

5G ESSENCE [START_REF] Essence | 5G-PPP Project[END_REF] addresses the paradigms of Edge Cloud computing and Small Cell as-a-Service (SCaaS) by fuelling the drivers and removing the barriers in the Small Cell (SC) market, forecasted to grow at an impressive pace up to 2020 and beyond, and to play a "key role" in the 5G ecosystem. The 5G ESSENCE framework provides a highly flexible and scalable platform, able to support new business models and revenue streams by creating a neutral host market and reducing operational costs, by offering new opportunities for ownership, deployment, and operation.

As the telecom ecosystem moves towards the innovative 5G era, important performance factors such as end-to-end (E2E) latency critically depend on whether the mobile edge and the target applications reside in an edge cloud close to the user or not. Building upon these technological foundations [2]- [START_REF] Costa-Perez | Radio Access Network Virtualization for Future Mobile Carrier Networks[END_REF], very ambitious objectives are targeted, culminating with the prototyping and demonstration of the 5G ESSENCE system in three real-life use cases associated to vertical industries, that is: (i) Edge network acceleration in a crowded event; (ii) mission critical applications for public safety (PS) communications providers, and; (iii) in-flight entertainment and connectivity (IFEC) communications. In this paper, we discuss the aforementioned use cases by considering the involved actors, per case, as well as the deployment topology.

2

5G Edge Network Acceleration at a Stadium

Overall description

Broadcasters are looking for new ways to cover events, to offer exciting point-ofview perspectives to viewers on one hand, and to reduce production and delivery costs on the other. At the same time, network operators target to increase the usage of their networks and stadium owners have a strong interest in making the visitors' experience as pleasant as possible, as well as to promote sponsors increasing siderevenues apart from ticket sales. The reception of live content from cameras located in the playing field, replays, and additional contextual information on mobile devices, is a strong use case for all the above actors. The main challenges even with 4G networks are the delay in the delivery of such content in the range of milliseconds rather than seconds, and the considerable strain imposed on the backhaul network. By deploying a 5G ESSENCE-like network, these challenges can be efficiently addressed.

Fig. 1. 5G Edge Network acceleration at Stadium

5G ESSENCE delivers benefits to media producers and mobile operators as it enables them to offer a highly interactive fan experience and it optimises operations by deploying "key functionalities" at the edge, i.e., evolved Multimedia Broadcast Multicast Services (eMBMS) or local network services like real-time analytics together with multitenancy support by small cells. By leveraging the benefits of small cell virtualisation and radio resource abstraction, as well as by optimising network embedded cloud, it becomes possible to ease the coverage and capacity pressure on the multimedia infrastructure, and also to increase security since content will remain locally. Furthermore, additional benefits for the operators and the venue owners arise, such as: (a) lower latency, due to shortening the data transmission path; (b) maintained backhaul capacity, due to playing out the live feeds and replays locally that puts no additional strain on the backhaul network and upstream core network components. The aforementioned use case is illustrated in Figure 1.

2.2

Actors involved

The actors involved in this scenario are listed below:  Small Cell Network Operator (SCNO): Owner of the infrastructure deployed in the stadium.  Virtual Small Cell Operator (VSCNO): Users of the infrastructure available in the stadium to provide services to the end-users.  End-Users (EUs): Users of the networking services.  Mobile Operators (MOs): Responsible of bringing the network and communication services to the stadium.  Service Provider (SPs): Companies providing some of the Virtual Network Functions to the SCNO. Examples of key service providers for this use case could be football/sport society, live event organizer, municipality, video/content provider.  Spectrum Owner (SO): In the licensed spectrum case, a stadium that leases the spectrum from an operator or a mobile operator that offers a service.  Mission Critical -Public Safety (MC-PS): Public or private organizations in charge of performing, when needed, mission critical actions for the public safety (video surveillance, monitoring, autonomous local network).

Deployment topology

5G ESSENCE will demonstrate a combined 5G-based video production and video distribution towards delivering benefits to both media producers and mobile operators, who will be able to offer enriched event experience to their subscribers. The production/distribution of locally generated content through the 5G ESSENCE platform, coupled with value-added services and rich user context, will enable secure, high quality and resilient transmission in real-time, thus ensuring minimal latency.

In the context of the 5G ESSENCE infrastructure sharing support, each network operator will be in position to optimise his network usage, resulting in lower OPEX. Additionally, network operators will be able to rapidly deploy new services, to deliver directly to users higher Quality of Experience (QoE), and to offer "Content as-a-Service", increased bandwidth, and storage solutions to content providers and venue owners. The content providers will also benefit from reduced latency and improved user QoE by positioning content on mobile edge and, in addition, they can offer augmented services by leveraging the network information. Finally, the stadium owner will obtain additional benefits by leveraging the deployed 5G ESSENCE infrastructure and its functionalities, by capitalising live contents to spectators from many cameras, etc.

The scenario provides the logic for distributing the live video feeds received from the local production room to local spectators in a highly efficient manner. Different scales facilities can be used for the validation of the deployment topology. First, a small-scale facility as the municipal open swimming pool with a capacity of 500 spectators, secondly a medium-scale facility like the municipal indoor stadium (which is used for basketball, volleyball and handball games) with a capacity of 2,000 spectators and thirdly a large-scale facility as the municipal football stadium "Stavros Mavrothalasitis" which is located at the centre of Egaleo town (in Athens, Greece) and it is an open stadium with capacity of about 8,000 spectators.

Considering a proper selection from the aforementioned facilities, the selected facility will be covered with a cluster of multitenant, eMBMS enabled as CESCs (Cloud-enabled Small Cells) and, together with the CESCM (CSC Manager) and the Main DC (Data Centre), they will be connected to the core networks of multiple telecom operators. The video content from cameras will be sent for processing locally at the Edge DC (similar to the proposed use case by ETSI MEC [13]). Then the video streams will be broadcasted locally by using the CESCs. Spectators will be able to dynamically select between different offered broadcast streams. In this and in similar big event scenarios, massive data traffic will not affect nor overload the backhaul connection, as it will be produced, processed and consumed just locally (5G MEC scenario).

5G E2E Slicing for Mission Critical Applications

Overall description

Latest 3GPP releases address the key requirements expressed from the Public Safety (PS) domain for next generation broadband public safety networks [START_REF]The Third Generation Partnership Project (3GPP[END_REF]. Further improvements to the 3GPP standards to cope with mission critical communications requirements are being considered as a central topic in the 3GPP requirements study for 5G [START_REF]The Critical Communications Association (TCCA): 4G and 5G for Public Safety -Technology options (White Paper)[END_REF]. Regarding PS service delivery models, there is a clear trend towards different forms of network sharing models as opposed to building out dedicated PS networks. For example, the Emergency Services Network in the UK is going to use the RAN (Radio Access Network) infrastructure of a commercial provider; Blue Light Mobile service by PS operator Astrid in Belgium offers access through roaming agreements with commercial operators; FirstNet in the US, while it counts with spectrum dedicated to PS, is expected to enable secondary use by commercial applications. In this context, multitenancy becomes a cornerstone challenge at an international level. 5G ESSENCE common orchestration of radio, network and cloud resources is expected to significantly contribute to the fulfilment of the requirements of the PS sector, thus bringing new tools to share both radio and edge computing capabilities in localised/temporary network deployments between PS and commercial users. The challenge consists on allocating radio, network and cloud resources to the critical actors (e.g., the First Responders) who, by nature, require prioritised and high quality services.

Fig. 2. Mission Critical applications for Public Safety

Indeed, the public safety operators are "shifting" their business model from a completely owned infrastructure model to one playing the role of a Mobile Virtual Network Operator (MVNO) between multiple parties owning and operating mobile networks and PS end-users. From a broader perspective, such deployment can be seen as a dedicated mission critical slice spanning across multiple operators domains. In such configuration, the relevant public safety operator "buys" connectivity to multiple legacy mobile operators and guarantees to his public safety customers connectivity, resilience and required quality of service (QoS) for PS operations. In practice, such approach has multiple benefits to PS operators, as discussed below.

First, it reduces the costs of buying, installing and maintaining dedicated infrastructures. Note that these physical infrastructures are not exploited to their optimal capacity. Second, the flexibility offered by such solutions enables (at least theoretically) MVNOs to adapt their offers to their customers. However, this approach comes at the price of pre-negotiated contracts between the MVNOs and multiple legacy providers, in order to ensure a high availability and a 'guaranteed" throughput for PS users.

For an allocation like this in order to be efficient and so to "enable" E2E network slicing, the 5G ESSENCE solution shall be applied. The aforementioned use case is schematically illustrated in Figure 2.

Actors involved

Demonstrating the 5G ESSENCE impact on mission critical deployments is performed with the following actors:  A legacy mobile operator (Platform owner) offering its infrastructure to classical end-users as well as to Public Safety virtual operators. Note here that virtual operators can rely on multiple legacy operators for additional guarantee.  A public safety operator that offers connectivity services with "strict" QoS guarantee to First Responders. Note that in our situation we can have multiple virtual operators each one offering a "separate" slice for a different First Responder agency.  First Responder 1: firefighters are end-users exploiting the connectivity offered by public safety operator through a dedicated slice. For the sake of demonstration, firefighters will use Mission Critical Push-To-Talk (MCPTT) application for their communications.  First Responder 2: paramedics are another set of end-users relying upon the same public safety operator or another slice coming from a different operator, in order to exchange chat messages as well as pre-registered pictures for situation assessment.  Legacy end-users constitute classical user that have subscribed to the legacy operator communication and Internet data offers. They are not part of any first responder entity but exploit only the network of the legacy mobile operator without any intermediary.

3.3

Deployment topology

The 5G ESSENCE innovative platform will involve one -or more-PS communications providers that will use the resources offered by a deployed 5G ESSENCE platform for the delivery of communication services to PS organisations in a country/region. The 5G ESSENCE platform can be owned by, either a mobile (potentially virtual) network operator or even by a venue owner, such as in the Use Case 1. In the mission critical use case, the infrastructure owner will exploit the 5G ESSENCE system's capabilities to provide the required network/cloud slicing capabilities with dedicated Service Level Agreements (SLAs) to different types of tenants, thus prioritising the PS communications providers.

The corresponding Mission Critical (MC) use case will be organised in three main stages, described as below:

Stage 1: Under normal circumstances, the 5G ESSENCE platform owner is providing the required network slices to different tenants. Each network slice is composed of an allocated data rate over a coverage area (which is mapped by the cSD-RAN (centralised Software-Defined RAN) Controller to a portion of CESC radio resources) and an allocated of cloud resources (which is mapped to processing power/storage capabilities in the Edge DC). For the service of Public Safety organisations, normal operations require a certain amount of access capacity and communications features (e.g., group communications capabilities) supported in the area of the CESC cluster. This requirement will be "mapped" to a number of radio Key Performance Indicators (KPIs) in the CESCs and the deployment of Group Communication service instances at the edge for multimedia and missioncritical Application Servers (AS) for voice with enhanced responsiveness. In addition to the QoS guarantees for each tenant, the deployment owner has to assure the required levels of isolation in the provisioning of the network slices.

Stage 2: In the case where there is an emergency in the area, the CESCM will be able to react to the new service requirements. The PS communications provider may require additional service in order to "cope with" an increased number of First Responders or additional types of services, such as mission-critical video transmissions. Based on pre-arranged or on-demand service scaling policies, the CESCM will implement new elastic resource allocation schemes, giving priority access to First Responders and taking into account both radio (for the access connections) and cloud resources (for deploying more resource-consuming edge services). The deployment of edge service instances serves a two-fold objective: first, it enables close-to-zero delay in the mission-critical services; second, it allows maintaining the operability, even when the backhaul connection is damaged.

Stage 3: In case that ICT infrastructure is damaged during a natural disaster or a terrorist attack, the first action should "address" the need for radio coverage extension. In this stage, a deployable system to mitigate the damage in the macrobase stations, will be used. In the proposed use case, the deployable system will offer 5G connectivity to the First Responders in the field, consolidating the interoperability requirements. In order to "better orchestrate" the radio transmissions, the deployable system will be considered as a new CESC that can be dynamically integrated to the small cell cluster. In this way, the enhanced 5G ESSENCE SON (Self-Organising Networks) and RRM (Radio Resources Management) features can be applied to the coverage extension unit. The interconnection of the deployable unit with the CESC cluster will be made through a wireless backhauling technology.

5G In-flight Communications and Entertainment System

Overall description

Some years ago, only a single movie was available for all passengers to watch during a flight. Next, on-demand viewing options came, built onto the seats, where viewers could choose from an array of available television shows, movies and specials. Today, passengers bring their own devices on selected airlines. Thus, the wireless Inflight Entertainment (IFE) and broadband mobile connectivity increasingly have become actual commodity expectations both from airlines and passengers.

With the increasing demand for wireless IFE and passenger Bring-Your-Own-Devices (BYOD) connectivity, together with the demand for on board broadband mobile Internet connectivity, an important focus is laid on the on-board infrastructure. Current in-cabin wireless systems mainly rely on Wi-Fi technologies for the wireless IFE and broadband Internet connectivity (with backhaul connectivity offered through satellite links). Such solutions have several limitations such as prohibitive costs to the service providers, inability to support broadband cellular services, lack of flexibility for airlines operators, etc.

In order to offer cost-effective mobile broadband Internet connectivity, it is imperative to integrate on-board a neutral host solution that will allow multioperator connectivity to the passengers, also accounting for variable service offerings. Such host-neutral services are important for European airliners, since they traverse several regional boundaries served by a large variety of mobile operators. Regarding backhauling, terrestrial direct-air-to-ground (continental airspace) and satellite (oceanic airspace) solutions can used.

The unique architecture proposed in 5G ESSENCE (as schematically depicted Figure 3) which combines efficiently the virtualised and multi-tenant small cell networks with a multi-tier cloud edge infrastructure, is an essential and innovative step towards establishing a pioneering integrated In-Flight Entertainment and Connectivity (IFEC) system that will jointly deliver the required communication and network infrastructure for the wireless IFEC (to both the embedded IFE devices and the wireless BYODs).

Two different scenarios are envisaged in the corresponding IFEC use case. The first one consists of streaming and encoding to PErsonal Devices (PEDs) and aircraft devices (i.e., seat built-in screens). The purpose is about exploiting the Multi-Operator Core Network (MOCN) from 5G ESSENCE and LTE technologies so that to showcase multi-tenancy. That way, the Small Cell Network Operator -for instance the airline-can provide its proprietary IFEC services to the EUs (passengers) while leasing, at same time, the same infrastructure to different VSCNOs, who will re-use it to give access to the same EUs to different services, such as Netflix, Spotify, etc., provided by themselves or by external Service Providers (SPs). For this concrete scenario, it is planned to "add" LTE to the current on-board Wi-Fi architecture, in order to provide multiple services from different operators/providers at the same time and in the same network infrastructure.

The second scenario consists upon providing efficient wireless multicast onboard. Networking speaking, the cabin of an aircraft is a super "dense" scenario. As mentioned above, all wireless communications on-board are currently done via Wi-Fi technologies, which actually "face" many limitations, in particular when many devices "share" the same medium. It becomes even more challenging, when it is planned to wirelessly multicast the same content at high-data rates to multiple PEDs and aircraft devices (for instance, video at high resolution). Thus, this specific scenario aims at dealing with and solving this problem by combining the Evolved Multimedia Broadcast Services (eMBMS) from LTE with the 5G ESSENCE architecture for on-board applications. This way, the SCNO can lease his infrastructure to VSCNOs and SPs, so that all of them can simultaneously stream their feeds (for instance, sport events, documentaries, or TV soap operas). Like that, the passengers (EUs) can watch live TV content in high resolution while, flying to a new destination. Functions to the SCNO.  Spectrum Owner (SO): In the licensed spectrum case, it is the airline who leases the spectrum from an operator or a mobile operator that offers a service on-board (who provides the spectrum for free or for a charge).

Deployment topology

The 5G ESSENCE IFEC demo will test and validate the multi-tenancy enabled network solution for passenger connectivity and wireless broadband experience. The multi-RAT (Radio Access Technologies) CESCs will be implemented as a set of integrated access points to be deployed on-board. Afterwards, since IFE has to consider the explosive growth of multi-screen content consumption, the 5G ESSENCE CESCs will stream on-demand multi-screen video content (both from on-board 5G Edge DC servers and via satellite/air-to-ground links) to the wireless devices. The 5G ESSENCE CESCs will rely on broadcast links, in order to optimise the bandwidth usage. Following the specific requirements for future IFEC solutions, as also currently outlined by various airlines and service providers, this 5G ESSENCE prototype platform will be tailored for a mock cabin deployment. The IFEC demonstration will be performed over a mock-up aircraft communications testbed installed, with core network connectivity to be incorporated both as on-board option and as a remote option steered via an emulated satellite link.

The use case will demonstrate the multitenant CESC for on-board connectivity and the Edge DC capabilities for hosting airborne applications (such as video player applications and files that can be made available for in-flight streaming) and caches (a version of the in-flight portal -gateway with which passengers can connect to).

The video encoding and packaging service will support a wide range of input file formats, allowing easy integration with existing production systems, and a comprehensive array of output formats. Output parameters will be configurable, enabling precise tuning for the desired output devices.

The topology foreseen for this use case aims at combining the current on-board topology with the one provided by the 5G ESSENCE project. Currently, an aircraft is connected to the Internet via a broadband antenna which, at the same time, is connected an on-board server, which is connected to the multiple access points deployed around the cabin to provide the IFEC services to the clients.

The 5G architecture is be added to the current cabin topology as an additional server, which is connected to the broadband access and all the other onboard servers. This new server will contain 5G ESSENCE elements, such as the MOCN, the small cell manager or the EPC (Evolved Packet Core) on-board. The current access points are going to be replaced by small cells, which will also be connected to this 5G ESSENCE server. This way, they are going to provide the different services/applications to the on-board screens and PEDs.

Discussion

In this paper, we have discussed the main use cases in the context of the 5G ESSENCE actual research framework. The first use case is a 5G edge network acceleration at a stadium. In particular, 5G ESSENCE will demonstrate a combined 5G-based video production and video distribution towards delivering benefits to both media producers and mobile operators, who will be able to offer enriched event experience to their subscribers. The second use case is 5G end-to-end slicing for mission critical applications. In particular, 5G ESSENCE will involve one or more PS communications providers that will use the resources offered by a deployed 5G ESSENCE platform for the delivery of communication services to PS organisations in a country/region. Our third scenario is focused upon in-flight communications and entertainment system. This demo will test and validate the multi-tenancy enabled network solution for passenger connectivity and wireless broadband experience. For each use case, we investigated the involved actors, as well as the deployment topology. As a next step, we intend to focus upon the evaluation process, as well as upon the extraction of the main technical and non-technical requirements. Part of this work is already presented in [START_REF] Chochliouros | Using Small Cells from enhancing 5G Networks[END_REF]. Apart from the evaluation process, 5G ESSENCE will consider market and business aspects, since its architecture allows the sharing of existing and new infrastructure by many operators in a multitenant environment. Thus, it will enable new business models that will help new entrant market players to develop and analyse the perspectives of potential "win-win" strategies, based on the developed solutions ( [START_REF] Chochliouros | Challenges for Defining Opportunities for Growth in the 5G Era: The SESAME Conceptual Model[END_REF], [START_REF] Khan | Network sharing in the next mobile network: TCO reduction, management flexibility, and operational independence[END_REF]).

Fig. 3 .

 3 Fig. 3. Integrated In-flight Connectivity and Entertainment Systems

Acknowledgements. The paper has been based on the context of the 5G-PPP phase 2 "5G ESSENCE" ("Embedded Network Services for 5G Experiences") Project (GA No.761592), funded by the European Commission.


Michalis Stavridis
email: michailstavridis@yahoo.com

Aigli Korfiati
email: a.korfiati@insybio.com

Georgios Sakellaropoulos

Seferina Mavroudi
email: s.mavroudi@insybio.com

Konstantinos Theofilatos
email: k.theofilatos@insybio.com

Non-coding RNA sequences identification and classification using a multi-class and multi-label ensemble technique

Keywords: Multi-label classification, non-coding RNAs, multi-objective optimization, random forests, dimensionality reduction

High throughput sequencing RNA-sequencing technologies and modern in silico techniques have expanded our knowledge on short non-coding RNAs. These sequences were initially split into various categories based on their cellular functionality and their sequential, thermodynamic and structural properties believing that their sequence can be used as an identifier to distinguish them. However, recent evidence has indicated that the same sequences can act and function as more than one type of non-coding RNAs with a striking example of mature mi-croRNA sequences which can also be transfer RNA fragments. Most of the existing computational methods for the prediction of non-coding RNA sequences have emphasized on the prediction of only one type of noncoding RNAs and even the ones designed for multiclassification do not support multiple labeling and are thus not able to assign a sequence to more than one non-coding RNA type. In the present paper, we introduce a new multilabel-multiclass method based on the combination of multiobjective evolutionary algorithms and multi-label implementations of Random Forests to optimize the feature selection process and assign short RNA sequences to one or more non-coding RNA types. The overall methodology clearly outperformed other machine learning techniques which were used for the same purpose and it is applicable to data coming from RNA-sequencing experiments.

Introduction

Non-coding RNAs (ncRNAs) are RNA fragments that are not translated to proteins [START_REF] Costa | Uncovering the complexity of transcriptomes with RNA-Seq[END_REF]. Small ncRNAs typical size is of 18-35 nucleotides (nt) and long-noncoding RNAs (lncRNAs) can be more than 200 nt (e.g., enhancer RNA --eRNA) [START_REF] Kang | Computational pre-diction of miRNA genes from small RNA sequencing data[END_REF]. The transfer RNA (tRNA) or the ribosomal RNA (rRNA) have been the subject of several studies and this has established their well-accepted functional roles in cells. However, over the past few years, advances on sequencing biotechnologies and other improvements on experimental protocols led to the elucidation of more ncRNA categories, the most prominent being: microRNAs (miRNAs), small nuclear RNAs (snRNAs), small nucleolar RNAs (snoRNAs), small inferring RNAs (siRNAs), piwi-interacting RNAs (piRNAs), ti-RNAs, spli-RNA, tRNA fragments (tRfs) and others to be identified [START_REF] Veneziano | Noncoding RNA: current deep sequencing data analysis approaches and challenges[END_REF]. Recently, transcriptomics analysis using RNA-seq data has also become the stateof-the-art procedure for identifying and annotating functionally ncRNA molecules. However, since ncRNA transcripts are drastically different from mRNAs, the majority of 'general-purpose' bioinformatics programs face limitations and are not well suited for discovering effectively ncRNAs from RNA-seq [START_REF] Conesa | A survey of best practices for RNA-seq data analysis[END_REF]. To mitigate this problem, several computational methods have been tailored to the needs of ncRNA data analysis. NcRNAs were initially split into various categories based on their cellular functionality and their sequential, thermodynamic and structural properties believing that their sequence can be used as an identifier to distinguish them. However, recent evidence has indicated that the same sequences can act and function as more than one type of ncRNAs with a striking example of mature microRNA sequences which can also be transfer RNA fragments. Most of the existing computational methods for the prediction of non-coding RNA sequences have emphasized on the prediction of only one type of ncRNAs [START_REF] Li | Perfor-mance comparison and evaluation of software tools for microRNA deepsequencing data analysis[END_REF] and even the ones designed for multiclassification, do not support multiple labeling and are thus not able to assign a sequence to more than one non-coding RNA types. For each one of the aforementioned short non-coding RNA types, a variety of computational methods exists for their prediction [START_REF] Aghaee-Bakhtiari | miRandb: a resource of online services for miRNA research[END_REF]. These are split into the computational methods which are designed to be specific to one type of short ncRNAs and the ones which can predict more than one type of short ncRNAs [START_REF] Washietl | Computational analysis of noncoding RNAs[END_REF]. The first category of methods presents increased classification performances but their applicability is limited as they cannot be used to analyze on a single run a large transcriptomic dataset and to predict different types of short ncRNAs. Moreover, most of the methods belonging to the second category exclude from their analysis significant types of short ncRNAs, while others are based on data mining in existing repositories and thus they cannot extend the current knowledge on short ncRNAs. Finally, most of these methods use the same features for all the different types of short ncRNAs. Another important drawback of existing methodologies is that they consider the different types of non-coding RNAs as separate forcing every RNA sequence to be classified in only one type of non-coding RNAs. However, as already mentioned, recent evidence has proven that this does not hold since tRNA fragments can have the same sequence as miRNAs [START_REF] Venkatesh | tRFs: miRNAs in disguise[END_REF]. If we add this fact to the previously known one that several types of non-coding RNAs are generated from pruning other types of non-coding RNAs, as in the case of pre-miRNAs and mature miRNAs, then a need for a multilabel computational method is raised to treat these data effectively. In the present paper, we introduce a new multilabel, multiclass method called Multi-label GARF, which combines multi-objective evolutionary algorithms with multi-label Random Forest implementations. In particular, it uses a Pareto-based multi-objective optimization to select the optimal subset of features to be used as inputs, to select the most suitable implementation of Random Forests for every dataset and to optimize its parameters. This optimization process is being guided by 7 fitness functions which are evaluating the solutions based on the classification performance of the Random Forest models extracted from them, and based on their simplicity in terms of the number of selected inputs and their number of random trees. The multi-objective optimization framework, by design avoids local optimal solutions promoting the optimal exploration of the search space. For the problem of classifying the RNA sequences to non-coding RNA types, for the purposes of the present manuscript, a new dataset was constructed with pre-miRNAs, mature miRNAs, snoRNAs, tRNAs, tRFs, rRNAs, pseudo hairpins and random RNA sequences. All these sequences were pairwise compared to locate similar sequences and for some of them multiple labels were assigned by this process. For all the sequences of the dataset, 58 sequential, thermodynamical and structural features were calculated including most significant features from existing non-coding RNA classification methods. The proposed solution was applied on this dataset and its performance was compared with existing state-of-the-art multi-label methods. Multi-label GARF significantly outperformed other methods in terms of classification performance on the testing dataset. Its performance surpassed 60% of the very strict multi-label accuracy metric which considers a sample to be classified correctly only if all its labels have been predicted correctly. It is noteworthy than none of the random RNA sequences were assigned to any of the non-coding RNA types and this makes the final predictive models suitable for screening RNA-seq reads for non-coding RNA sequences.

Materials and Methods

RFAM database [START_REF] Griffiths-Jones | Rfam: annotating non-coding RNAs in complete genomes[END_REF] was used to download mature miRNA (1865), pre-miRNA (2547), tRNA (12522), rRNA (25723) and snoRNA (12522) sequences. Moreover, tRNA fragments (tRFs) were downloaded from MINTbase [START_REF] Pliatsika | MINTbase v2.0: a comprehensive database for tRNAderived fragments that includes nuclear and mitochondrial fragments from all The Cancer Genome Atlas projects Nucleic Acids Res[END_REF] and tRFdb [START_REF] Kumar | tRFdb: a database for transfer RNA fragments[END_REF]. In order to train and test effectively the machine learning classifiers, the random undersampling method was applied randomly selecting only 1865 sequences of each category to be included in the final dataset since this is the plurality of the minority class. The produced dataset was extended with 1865 pseudo hairpin sequences constructed following the method described in [START_REF] Kleftogiannis | YamiPred: A novel evolutionary method for predicting pre-miRNAs and selecting relevant features[END_REF] and 1865 random RNA-sequences of lengths from 20 to 200. These sequences were pairwise compared to identify equal or similar sequences allowing total 2 mismatches belonging to more than one categories or sequences which can be found within other sequences. This analysis was conducted to assign multiple labels to these types of sequences. As a next step for all of these sequences 58 structural, sequential and thermodynamic features were calculated using InSyBio ncRNAseq tool [START_REF] Korfiati | InSyBio ncRNASeq: A web tool for analyzing non-coding RNAs[END_REF]. The final dataset was split in training and testing set with 2/3 of its sequences being assigned to the training set and the remaining 1/3 to the test set. This split was conducted randomly but reassuring that 1:1 proportion is maintained for every class in the dataset. The proposed designed and implemented method is a hybrid method which solves on parallel the problems of dimensionality reduction and multiple labels classification. In specific the proposed method, Multi-Label GARF, is an ensemble dimensionality reduction technique which utilizes a multiobjective evolutionary algorithm [START_REF] Abraham | Evolutionary Multiobjective Optimization[END_REF] for the identification of the optimal feature subset to be used as input to the classifiers as well as for the selection of the most suitable type of Random Forests classifier [START_REF] Breiman | Random forests[END_REF] to be used and its optimal parameters. The multi-objective evolutionary framework used for this implementation was based on the multi-objective evolutionary algorithm initially applied in [START_REF] Corthesy | An adaptive pipeline to maximize isobaric tagging data in large-scale MS-based proteomics[END_REF] for the optimization of the preprocessing pipeline for the analysis of Mass Spectrometry data. This is based on a Pareto-optimization technique to allow fast convergence to good exploration properties and effective handling of the contradictory goals of minimizing the number of used features, maximizing the accuracy of the classifiers and minimizing the complexity of the classifier to achieve better generalization properties. The algorithm starts by randomly initializing a first population of solutions which are represented as float vectors. These vectors consist of i) float variables for the parameter number of random trees to be used and the minimum number of samples assigned per leaf to control the splitting process on Random Forests, ii) a float variable to choose between the two alternative multi-label Random Forest algorithms (a value greater than 0.5 indicates the selection of method 2 and a value less than 0.5 indicates the selection of method 1) and 58 float variables for deciding if a feature will be selected as input or not (values greater than 0.5 forces a feature to be used as input). The float vectors of the population are initialized randomly with values from the normal distribution with mean equal to min_value+ (max_value-min_value)/2 and variance (max_value-min_value)/2, where max_value is the maximum allowed value of an optimization variable and min_value is its minimum allowed value. For the variation of the population of solutions in order to create new solutions, crossover and mutation operators are sequentially applied. Regarding the crosso-ver operators, two crossover methods are used with probabilities which are also provided by the user (45% probability for two-point crossover operator, 45% probability for arithmetic crossover and 10% for not applying crossover operator were used for this implementation). For the mutation, the Gaussian mutation operator is applied since it is the most suitable operator for the float representation scheme which is adopted in the proposed algorithm with mutation probability 1%. To better handle the multiple objectives of the current problem, the selection process was based on a multi-objective optimization method. The first step is to calculate the number of Pareto frontiers (sets of solutions where no solution is better than other solutions in the same set to all optimization goals). To calculate the Pareto frontiers, the efficient and fast solution described in [START_REF] Mishra | A Fast Algorithm for Finding the non Dominated Set in Multiobjective Optimization[END_REF] was used. An initial fitness value is then assigned to every solution equal to the reverse order of the parent front to which it has been assigned by the previous step. Next, the method calculates solution niches by grouping together solutions according to their similarity. The fitness values of every solution in a given niche are divided by the variable m (average similarity of every solution) which is calculated by performing pairwise comparisons of all solutions of the niche calculating their geometrical distances and calculating the mean pairwise distance of them. These fitness values are then tuned according to the number of solutions belonging to each niche. Roulette Wheel Selection is then used to select the population of the next generation. The best solution passes as it is to the next generation. The total fitness value is calculated with the weighted sum of the optimization goals with the weights pre-defined by the user. The specific fitness functions (FF) which were used for multi-label GARF algorithm were the following: Fitness function 1 aims at the minimization of the selected features in order to increase the interpretability of the classifier. Fitness functions 4 and 5 were used to promote solutions which lead to simpler models to present better generalization properties. The rest of the fitness functions are employed to increase the algorithm's classification performance. The algorithm was terminated when the population of solutions is deemed as converged (the similarity among the solutions surpasses a predefined threshold) or when the maximum number of generations is reached.

The multi label Random Forest classifiers implementation was based on sklearn python library [18] using two different approaches regarding the function used to measure the quality of a split in the process of generating the trees of random forests. The first method is called Gini and uses the Gini impurity function [START_REF] Modarres | A Cautionary Note on Estimating the Standard Error of the Gini Index of Inequality[END_REF] and the second method uses the information gain function [START_REF] Liu | MLRF: Multi-label Classification Through Random Forest with Label-Set Partition[END_REF]. The overall pipeline of the multi-label GARF is depicted in Figure 1.

Experimental Results

All features of the dataset were arithmetically normalized to the interval [-1, 1] and missing values were imputed using KNN-Impute method [START_REF] Zhang | Nearest neighbor selection for iteratively kNN imputation[END_REF]. Then the Multi-label GARF and other multi-label methods were used to train multi-label classification models using the training dataset. The trained classification models were applied on the testing dataset and Table 1 presents the Accuracy and Hamming-Loss metric for every model. The state of the art multi-label models which were used for comparison reasons were the Random Forest implementation of sklearn library, the extra trees algorithm [START_REF] Geurts | Extremely randomized trees[END_REF], the multi-label KNN [START_REF] Zhang | ML-KNN: A lazy learning approach to multi-label learning[END_REF], a Decision Tree algorithm [START_REF] Vens | Decision trees for hierarchical multi-label classification[END_REF] and the Binary Relevance algorithm [START_REF] Luaces | Binary relevance efficacy for multilabel classification[END_REF]. For all these algorithms, all features were used as inputs and they were tested using their default parameters. Regarding the Multi-label GARF algorithm, after extensive testing in the training set, a population of 50 individuals was used and a maximum number of 200 generations was set for the termination criterion. Further increase in the number of generations did not improve the results. Mutation Probability was set to 1%. Moreover, during its training phase internal 5-fold cross validation was applied using the training dataset. In order to take into account, the stochastic nature of this method we run the experiments 25 times and the results of Table 1 are the mean values together with their standard deviation (SD). The goal significances for the fitness functions 2, 3, 6, 7 were set to 1.5 and for the other goals to 1. By this way we are setting for the final ordering of the solutions, classification performance to be twice as significant as the goals of minimizing the classification model's complexity. The best solution uncovered by Multi-label GARF method among all runs used the Gini metric for splitting criterion on the random tree nodes, 8637 number of random trees, 3 as minimum number of samples assigned per leaf and 27 features were selected. Moreover, a closest examination on the results indicated that none of the random RNA sequences was assigned to any of the non-coding RNA types by the multi-label GARF method.

Multi-label GARF significantly outperformed the other examined methods in terms of classification performance on the testing dataset. Its performance was over 60% of the very strict multi-label accuracy metric which considers a sample to be classified correctly only if all its labels have been predicted correctly. None of the other examined methods presented accuracy more than 30%. Finally, it is noteworthy than none of the random RNA sequences were assigned to any of the non-coding RNA types and this makes the final predictive models suitable for screening RNA-seq reads for non-coding RNA sequences.

Discussion

Predicting and classifying short ncRNAs is of crucial importance for systems biology and translational medicine to: i) allow the prediction of new ncRNA molecules for human or other not well studied organisms (including the human microbiome), ii) ease the analysis of high throughput sequencing experiments by allowing for the efficient identification and quantification of non-coding RNAs without the need of analyzing them separately by modifying samples with specialized libraries and iii) enable the understanding of ncRNAs functionality. To the best of our knowledge, most existing methods are offering prediction of very limited number of non-coding RNA categories with most of them emphasizing on miRNAs. Moreover, all existing methods do not take into account the fact that some sequences may be assigned to more than one ncRNA categories while some ncRNA sequences are being generated from pruning other ncRNAs.

In the present work, we have attempted to overcome these difficulties by proposing a unified multi-label multi-classification algorithmic framework which combines multi-label Random Forests with a multi-objective optimization algorithm to find the optimal classification model with the minimum number of inputs. To test the proposed solution, we generated the first multi-label dataset for non-coding RNAs mining information from several databases and compared the proposed solution with other state-of-the-art multi-label classification models. The multi-label GARF clearly outperformed all other methods in both classification metrics used. Moreover, on this specific dataset none random RNA sequence was assigned to any type of non-coding RNAs. Furthermore, the additional labels which are assigned by it in some of the sequences which maintained the strict metric of multilabel accuracy in approximately 60% should be further explored in the future as meaningful information could reside on them about other functionalities that could be performed by the same sequences or parts of them. The fact that the proposed technique was able to train models that can predict noncoding RNAs within longer RNA sequences makes it appropriate for being applied directly on the reads extracted from deep RNA-sequencing experimental techniques. As an example, in the case of identifying miRNAs from RNAsequencing, a common problem is whether to search for pre-miRNAs or for ma-ture miRNAs since both types of RNA sequences can be detected in a biosample. The extracted predictive models from the present paper can solve efficiently this problem as well as the problem that non-coding RNAs are most of the time only a subset of a read being generated by sequencing technologies. Thus, an interesting future direction includes testing and validating the performance of the proposed method directly on sequences exported from RNA-sequencing experiments. Moreover, despite the promising results of the proposed model, its performance can be further improved by including even more features as potential inputs (e.g. existence of clover structure). Finally, the current implementation can be expanded to allow for the prediction of other types of non-coding RNAs such as scRNAs and diRNAs.

  of trees used by Random Forests 𝐹𝐹5 = Average number of samples per node Split in Random Trees Total Number of samples 𝐹𝐹6 = Recall Classification Metric 𝐹𝐹7 = Precision Classification Metric

Fig. 1 .

 1 Fig. 1. Flowchart of Proposed Method: Multi-Label GARF

Table 1 . Comparative results on the classification of non-coding RNA sequences using

 1 the proposed technique and other existing machine learning techniques compatible with multi-label datasets.

	Method	Accuracy (mean -SD)	Hamming-Loss Metric (mean -SD)
	Multi-label GARF	61% -0.3461	0.051 -0.002529
	Random Forest	28% -0.0002	0.010 -0.000061
	Extra Trees	12% -0.0002	0.009 -0.000062
	Multi Label KNN	1% -0.0008	0.010 -0.000006
	Decision Tree	29% -0.0004	0.010 -0.000007
	Binary Relevance	22% -0.0005	0.012 -0.000005


Ilias Kalamaras
email: kalamar@iti.gr

Nikolaos Kaklanis

Kostantinos Votis
email: kvotis@iti.gr

Dimitrios Tzovaras
email: tzovaras@iti.gr

Towards big data analytics in large-scale federations of semantically heterogeneous IoT platforms

Keywords: Internet-of-things, big data analytics, semantic interoperability, healthy ageing

The technological advances in the Internet-of-Things (IoT) have led to the generation of large amounts of data and the production of a large number of IoT platforms for their management. The abundance of raw data necessitates the use of data analytics in order to extract useful patterns for decision making. Current architectures for big data analytics in the IoT domain address the large volume and velocity of the produced data. However, they do not address the semantic heterogeneity in the data models used by diverse IoT platforms, which emerges when large-scale deployments, spanning across multiple deployment sites, are considered. This paper proposes an architecture for big data analytics in the context of large-scale IoT systems consisting of multiple IoT platforms. A Semantic Interoperability Layer (SIL) handles the interoperability among the data models of the individual platforms, using semantic mappings between them and a unified ontology. Data queries to the SIL and result collection is handled by a cloud-based data management layer, namely the Data Lake, along with storage of metadata needed by data analytics methods. Based on this infrastructure, webbased data analytics and visual analytics methods are used to analyze the collected data, while being agnostic of platform-specific details. The proposed architecture is developed in the context of healthcare provision for older people, although it can be applied to any IoT domain.

Introduction

The technological advances of the Internet-of-Things (IoT) have led to the development of human-centric IoT applications, such as e-Health and intelligent transportation systems. Such applications allow the collection of valuable domain information, assisting human operators and decision makers in providing services for the well-being of individuals and communities. In the context of e-Health, for example, IoT systems can be used to collect data from a large number of patients, allowing a close monitoring of their health and the provision of (automatic or not) interventions, or the formation of health management policies. Currently running European research projects, such as ACTIVAGE [START_REF]European project ACTIVAGE[END_REF] and FrailSafe [START_REF]European project FrailSafe[END_REF], in an attempt to address the healthcare needs of the increasing number of ageing population, provide promising solutions towards the use of IoT technologies for older people monitoring and assistance.

The extensive use of IoT technologies has led to two outcomes. First, there is a very large volume of data (collected by a wide variety of sensors, such as wearables, environmental sensors, appliance usage monitors, etc.), which exceeds the storage and processing power limits of stand-alone applications (big data). Second, there is a growing number of developed IoT platforms providing off-theself solutions for the development and deployment of IoT applications, without the need for extensive programming. However, in large-scale applications, spanning a large number of different installations, maybe across different countries, each installation may use a different IoT platform, having its own data model for describing the IoT devices and collected data. These models are often incompatible with each other in terms of semantics, making the necessity of semantic interoperability apparent. There is a need to have a common semantic model for describing the concepts of all IoT platforms, in order for large-scale data analytics methods to perform.

This paper proposes an architecture that allows big data analytics methods to perform on large-scale IoT deployments, spanning multiple diverse IoT platforms. Interoperability among the IoT platforms is handled by the introduced Semantic Interoperability Layer (SIL), providing a unified data model and semantic mappings. Data analytics methods are supported by the introduced Data Lake, which is based on the SIL and maintains its own cloud storage for extracted features, trained models and any metadata that are needed by analytics methods. The architecture is developed in the context of the ACTIVAGE project [START_REF]European project ACTIVAGE[END_REF], whose goal is to support large-scale IoT applications in deployment sites across European countries, in order to exploit the large volume of collected data. Towards this goal, existing IoT platforms already deployed in different sites are used, as well as various sensing systems, such as the behavioural monitoring systems developed in the FrailSafe project [START_REF]European project FrailSafe[END_REF]. Providing an infrastructure for combining the diverse platforms and data models can provide large-scale data analytics for assisting older people, clinicians and researchers.

The rest of this paper is organized as follows. Section 2 presents background, work regarding big data analytics and semantic interoperability. Section 3 describes the proposed architecture, covering the Semantic Interoperability Layer, the Data Lake, and the data analytics and visualization components. Section 4 describes scenarios for the preliminary evaluation of the proposed architecture, while Section 5 concludes the paper, providing information about the next steps.

Background

Big data analytics

Data analytics aim at analyzing raw data, in order to extract information that is more meaningful and valuable to the human operator in order to under-stand the data and make decisions. In the context of IoT, data analytics are mostly concerned with classification, clustering and high-level data representation [START_REF] Marjani | Big iot data analytics: Architecture, opportunities, and open research challenges[END_REF]. Classification methods assign an observation to one of multiple classes, after being trained using data with known classes. Common classification methods currently used include Support Vector Machines (SVM) [START_REF] Soualhi | Bearing health monitoring based on hilbert-huang transform, support vector machine, and regression[END_REF], and Random Forests [START_REF] Chen | A parallel random forest algorithm for big data in a spark cloud computing environment[END_REF]. Anomaly detection methods detect unusual circumstances by classifying observations as normal or abnormal, e.g. Local Outlier Factor (LOF) [START_REF] Papadopoulos | A brpca based approach for anomaly detection in mobile networks[END_REF] and Bayesian Robust PCA (BRPCA) [START_REF] Ding | Bayesian robust principal component analysis[END_REF]. Clustering methods split observations in groups of similar characteristics, without using training information [START_REF] Rokach | Clustering methods[END_REF]. Hierarchical clustering proceeds by recursively joining or separating observations, until a tree-like structure is formed, while partitioning clustering, such as kmeans and k-medoids, considers an arbitrary starting split, iteratively updating it to best represent the data. Methods to construct high-level representations for raw data can remove unnecessary or redundant dimensions. Principal Component Analysis (PCA) [START_REF] Wold | Principal component analysis[END_REF], Multi-Dimensional Scaling (MDS) [START_REF] Cox | Multidimensional scaling[END_REF] and graph embedding methods [START_REF] Yan | Graph embedding and extensions: A general framework for dimensionality reduction[END_REF], attempt to find subspaces (manifolds) of maximum information and minimum dimension inside the raw data space. In the context of time series analysis, ARMA models [START_REF] Kalpakis | Distance measures for effective clustering of arima time-series[END_REF] and variants are used to extract high-level information, such as trends and periodicities, from the raw data.

Several architectures for big data analytics in IoT applications have been proposed. The authors of [START_REF] Marjani | Big iot data analytics: Architecture, opportunities, and open research challenges[END_REF] provide a related review and propose an architecture where the data collected by sensors are stored in cloud databases, allowing large-scale data analytics methods to operate on them, using cluster computing frameworks, such as Apache Spark [START_REF]Apache Spark[END_REF] and Hadoop [START_REF]Apache Hadoop[END_REF]. The authors of [START_REF] Strohbach | Towards a big data analytics framework for iot and smart city applications[END_REF] propose a framework for off-line and on-line analysis of IoT data of large volume and velocity, by computing model parameters off-line and using them for real-time analysis. The authors of [START_REF] Rathore | Urban planning and building smart cities based on the internet of things using big data analytics[END_REF] propose a 4-tier architecture, covering data generation by sensors, communication between sensors and gateways, data analysis using cluster computing, and finally data interpretation by human operators. Most big data analytics architectures in the IoT domain are concerned with handling the large volume and velocity of the produced data, without addressing the variety and heterogeneity in their semantics.

Semantic interoperability

There is a large number of IoT platforms for managing devices and data, each using a different ontology to describe its semantics [START_REF] Bajaj | A study of existing ontologies in the iot-domain[END_REF]. The SSN (Semantic Sensor Network) ontology [START_REF] Compton | The ssn ontology of the w3c semantic sensor network incubator group[END_REF] describes sensors in terms of their functionalities, measurements and deployments, although it has limitations regarding real-time data collection. The oneM2M ontology [START_REF] Alaya | Toward semantic interoperability in onem2m architecture[END_REF] has been supported by IoT standardization bodies, although it also has limitations in terms of contextual data annotation. The IoTivity platform [START_REF]IoTivity[END_REF] is based on the models of the Open Connectivity Foundation (OCF) [START_REF]Open Connectivity Foundation[END_REF], which aims at providing a common framework for communication among IoT devices and gateways. The OpenIoT ontology [START_REF] Soldatos | OpenIoT: Open source internet-of-things in the cloud[END_REF], utilized by the OPENIoT platform [START_REF]OPENIoT[END_REF], is based on the SSN ontology and adds concepts related to IoT applications and testbeds. The IoT-Lite ontology [START_REF] Bermudez-Edo | Iotlite: a lightweight semantic model for the internet of things[END_REF], used by the FIWARE platform [START_REF]FIWARE[END_REF], is a recent attempt to collect existing concepts of the IoT domain in a common ontology. Ad-hoc data models have also been built for the purposes of various existing open-source IoT platforms, including sensiNact [START_REF]sensiNact[END_REF], universAAL [START_REF]universAAL[END_REF], Sofia2 [START_REF]Sofia2[END_REF] and SENIORSome [START_REF]SENIORSome[END_REF].

This abundance of IoT ontologies creates interoperability issues in large-scale applications, where IoT platforms with different ontologies must cooperate. Semantic interoperability ensures that all components have a common understanding of the meaning of the information being exchanged [START_REF] Veer | Achieving technical interoperability-the etsi approach, european telecommunications standards institute[END_REF]. Attempts have been made to promote semantic interoperability by unifying existing ontologies. The SAREF (Smart Appliance REFerence) ontology [START_REF] Daniele | Created in close interaction with the industry: the smart appliances reference (saref) ontology[END_REF] is such an attempt, unifying concepts from several ontologies in the smart appliances domain, in order to cover larger applications. The authors of [START_REF] Agarwal | Unified iot ontology to enable interoperability and federation of testbeds[END_REF] use the ontology interconnection methodology of [START_REF] Noy | Ontology development 101: A guide to creating your first ontology[END_REF], in order to unify existing ontologies in the IoT domain, within the context of the FIESTA-IoT European project [START_REF]European project FIESTA-IoT: Federated Interoperable Semantic IoT Testbeds and Applications[END_REF].

The above review suggests that architectures for big data analytics in IoT systems do exist, but they focus on handling the large data volume and velocity, without addressing the heterogeneity of the available data models. Attempts to address heterogeneity are being made, but they are not targeted to providing a basis for large-scale data analytics methods. The current paper aims to contribute to this direction, by proposing an architecture for large-scale IoT data analytics, based on semantic interoperability across diverse IoT platforms.

The ACTIVAGE data analytics architecture

The proposed architecture for large-scale data analytics is depicted in Fig. 1b. It is based on the structure of existing IoT frameworks, as depicted in Fig. 1a, forming a stack of layers ranging from the IoT devices at the bottom, towards data analytics and visualization at the top. However, instead of a single IoT platform to handle the devices at the bottom, there are now many platforms, each operating separately, with its own devices, data storage and component semantics. The following IoT platforms are considered in ACTIVAGE, although any number of platforms is supported: FIWARE [START_REF]FIWARE[END_REF], sensiNact [START_REF]sensiNact[END_REF], universAAL [START_REF]universAAL[END_REF], IoTivity [START_REF]IoTivity[END_REF], Sofia2 [START_REF]Sofia2[END_REF], SENIORSome [START_REF]SENIORSome[END_REF] and OPENIoT [START_REF]OPENIoT[END_REF]. The next layer is the Semantic Interoperability Layer (SIL), which unifies the ontologies of the IoT platforms and offers common semantics for their components. The presence of the SIL eliminates any issues of compatibility between inter-platform hardware and software, as each platform manages its own hardware and software, in order to collect data. Interoperability in ACTIVAGE happens in a conceptual level, by ensuring the compatibility between different data representations, using the SIL semantic mappings. Above the SIL is the Data Lake, which, through its Data Integration Engine, directs the queries coming from the upper layers towards the SIL and collects the data retrieved from the IoT platforms. The Data Lake also contains a Metadata Storage component, for storing metadata (models, etc.) produced and needed by the data analytics methods. The Data Lake components are cloud-based, offering Web APIs for their usage. Based on the infrastructure of the SIL and the Data Lake, the top layers, data analytics and information visualization, can operate, extracting patterns and producing visualizations through Web APIs and graphical interfaces.

Semantic interoperability layer

The Semantic Interoperability Layer (SIL) is responsible for providing an abstraction for the representation of devices, attributes and data, that is agnostic of any IoT platform-specific details and naming conventions. In order to provide interoperability, the SIL maintains a common ontology describing the components of an IoT platform, namely the ACTIVAGE ontology. This ontology unifies the ontologies of the participating IoT platforms, so that common names are given for concepts with the same semantics. Platform-specific data representations may be both structured (schema-based databases), or unstructured (schema-less databases). The SIL provides semantic mappings between the common unified model and these individual data models of the IoT platforms. The ACTIVAGE ontology is based on existing IoT ontologies, such as SSN [START_REF] Compton | The ssn ontology of the w3c semantic sensor network incubator group[END_REF], SAREF [START_REF] Daniele | Created in close interaction with the industry: the smart appliances reference (saref) ontology[END_REF], oneM2M [START_REF] Alaya | Toward semantic interoperability in onem2m architecture[END_REF], IoT-Lite [START_REF] Bermudez-Edo | Iotlite: a lightweight semantic model for the internet of things[END_REF] and OpenIoT [START_REF] Soldatos | OpenIoT: Open source internet-of-things in the cloud[END_REF], and aims to combine and extend them. It defines basic concepts of IoT platforms, such as Device (a physical object able to communicate with its environment), Service (a software component able to perform some functionality) and Measurement (a piece of information collected by a device). Some concepts, such as "Device", are widely used across many existing IoT ontologies, while others, such as "Service" and "Measurement", are defined only in some of them. The ACTIVAGE ontology aims at gathering both widely used and less used concepts, in order to cover the types of applications built on top of ACTIVAGE, such as data analytics. The ACTIVAGE ontology is currently under development and is meant to be constantly developed as the proposed architecture is evaluated in real-world scenarios and further IoT platforms are integrated.

Data Lake

The Data Lake acts as an intermediate layer between the Semantic Interoperability Layer and the data analytics and visualization methods above. It consists of the following components:

-The Data Integration Engine, which directs queries from data analytics methods towards the SIL and collects the results from the IoT platforms. -The Metadata Storage Component, a database of metadata produced by the data analytics algorithms, which are necessary for their on-line operation.

In ACTIVAGE, the data collected by the IoT sensors and used for data analytics are stored in the storage facilities of each separate IoT platform. This facilitates the registration of new platforms, since it avoids switching to a different database and duplicating data. It also promotes data security and privacy, since the sensitive raw data remain in the deployment site's premises and under any site-specific privacy-related restrictions. However, the Data Lake does offer additional central storage, dedicated to metadata necessary for the operation of data analytics. These include produced features and analysis results, e.g. trained classification models, anomaly detection thresholds, etc., which may be necessary for their operation. Metadata are usually produced off-line, at regular intervals, using historical data, in order to be later used for real-time analytics.

The operation of the Data Lake and it connection to the SIL is described in Fig. 2. Data analytics methods (e.g. anomaly detection) need raw data stored in the distributed storages of the IoT platforms (e.g. the most recent sensor measurements), as well as specific metadata (e.g. pre-computed anomaly detection thresholds). The raw data are requested from the Data Integration Engine, while the metadata from the Metadata Storage Component. In order to collect the raw data, the Data Integration Engine submits a query to the SIL, written with the naming conventions of the unified ACTIVAGE ontology. The SIL translates the query to the platform-specific data models. The IoT platforms retrieve the requested data from their storage and return them to the SIL, which translates them to the ACTIVAGE ontology and sends them back to the Data Integration Engine. The latter combines the multiple sets of returned results and sends them to the data analytics component. At the same time, the Metadata Storage Component retrieves the requested metadata and sends them to the data analytics component as well. The data analytics method now has all the necessary information to produce the requested output (e.g. the detected anomalies).

Data analytics and information visualization

The top layers in the ACTIVAGE architecture are the data analytics and information visualization layers, which provide meaningful representations of the raw data to the human operator. IoT applications are usually targeted at monitoring an environment, e.g. a person, a house, a city, etc, in order to facilitate decision making. In the context of e-health for older people, which is the primary target of the ACTIVAGE project, the purpose is to facilitate clinicians in monitoring Fig. 2: Operation of the ACTIVAGE Data Lake. k-partite graphs [START_REF] Drosou | An enhanced graph analytics platform (gap) providing insight in big network data[END_REF], multi-objective visualization [START_REF] Kalamaras | Multi-objective optimization for multimodal visualization[END_REF] an individual's health and taking proper actions, or to facilitate researchers in monitoring large sets of individuals and discover correlations. The focus of data analytics is thus on methods that extract representative features, find correlations, detect anomalies in usual behavior (e.g. to trigger alarms), and cluster objects (patients, devices, etc.) in groups of similar characteristics.

Existing data analytics methods are used in ACTIVAGE, covering the tasks outlined in Section 2: feature extraction, dimensionality reduction, anomaly detection and clustering. Table 1 summarizes the data analytics methods used in ACTIVAGE. This is not an exhaustive list, since other methods may be included as needed by IoT applications. Information visualization aims to produce descriptive graphical summaries of the raw data, allowing the operator to have a comprehensive overview of the data and explore them in order to detect interesting patterns. Table 1 summarizes the visualization methods used in ACTI-VAGE. Commonly used visualization methods, such as bar charts and line plots are used, as well as more sophisticated graph-based visualizations for visualizing similarities and differences among objects.

Preliminary evaluation

The proposed architecture is currently being evaluated using a smart home scenario and a smart mobility scenario. The purpose of the smart home scenario is to monitor the health status of older people as they perform activities of daily living, and assist the clinician in decision making through data analytics services. Environment and activity detection sensors are installed in the older person's home, constantly measuring temperature/humidity, CO levels, person motion and door/window opening. Two medical devices, a blood pressure monitor and a blood glucose measurement device, are also used at specific times within the day. All devices are connected to the gateways via Bluetooth, ZigBee and ZWave protocols, while the universAAL [START_REF]universAAL[END_REF] and IoTivity [START_REF]IoTivity[END_REF] platforms are used for their management. The scenario is currently being installed in testhomes, in order to be further deployed in several Greece municipalities, during the next period, with 500 scheduled participants in total. The purpose is to allow centralized management and analysis of the collected data by healthcare professionals.

In the mobility scenario, the purpose is to monitor and assist the older person while moving in a city, providing information and alerts when needed. The sensors involved include Bluetooth detectors installed at intersections for detecting bypassing devices, connected traffic signals, taxi data collectors, environmental pollutant detectors and pedestrian presence detectors. The FIWARE [START_REF]FIWARE[END_REF] IoT platform is being used for device and data management, with the aim to use more IoT platform types in the future, as part of a larger deployment. The scenario is currently being installed in test sites, with the purpose of being further deployed in Greece municipalities, with 500 scheduled participants. The purpose is to monitor the environment and the participants' movements, analyzing the collected data to provide notifications when certain patterns are detected.

Conclusion and next steps

This paper proposes an architecture for big data analytics in the IoT domain, in the context of large-scale federations of IoT platforms with heterogeneous data models. The semantic interoperability issue is addressed by introducing the Semantic Interoperability Layer (SIL), which maintains a common ontology describing relevant IoT concepts, as well as semantic mappings with the platform-specific ontologies. In this way, the upper layers can be agnostic of platform-specific naming conventions and semantics. The architecture also introduces the Data Lake layer, for directing external queries and results to and from the SIL, as well as for storing analysis metadata (extracted features, trained models, etc.) which are needed for real-time data analytics. The architecture is being tested in laboratory environments, and is about to start being tested in real-world deployment sites. The architecture has been developed in the context of health assistance for older people, although it is generic enough to be applied in any application domain, such as smart cities, traffic monitoring, etc.

The next steps will be focused on implementation, integration and large-scale deployment. The proof-of-concept of the proposed architecture has been demonstrated in laboratory settings with a limited part of the whole architecture functioning. In the next period, the SIL ontology will be defined and implemented in detail, the Data Lake infrastructure will be completed to provide the basis for all data analytics methods, and the implementation of data analytics and visual analytics as Web services will be performed. In the meantime, integration issues will be resolved in order for the whole data analytics workflow to perform end-to-end. Finally, as mentioned in Section 4, the architecture is going to be tested in large-scale deployment sites in Greece municipalities, with a large number of participants, in order to use and evaluate it in real-world conditions. During evaluation, fine-tuning of ontology entities and data/visual analytics will be performed, in order to identify those concepts and methods that best fit in large-scale applications.

Fig. 1 :

 1 Fig. 1: The proposed ACTIVAGE architecture (b) extends existing IoT solutions (a), by adding layers regarding platform interoperability and data management.

Table 1 :

 1 Data analytics and visualization methods used in ACTIVAGE.

	Visualization category	Methods
	Time-related visualizations	Line plot
	Relative size comparison	Bar/pie/stacked bar/sunburst chart, treemap
	Multi-variate comparison	Scatterplot, parallel coordinates, spider web, heatmap
	Graph-based visualizations

Data analytics category Methods

Feature extraction PCA [9], MDS [10], Graph embedding [11] Anomaly detection SVM, Random Forests, LOF [6], BRPCA [7] Clustering Partition-based (k-means, k-medoids), hierarchical

Acknowledgments

This work is supported by the EU funded projects ACTIVAGE (H2020-IOT-2016, grant agreement no. 732679) and FrailSafe (H2020-PHC-2015-single-stage, grant agreement no. 690140).


Georgios Drakopoulos

Dimitrios Tsolis
email: dtsolis@upatras.gr

Antonia Stefani
email: stefani@eap.gr

Phivos Mylonas
email: fmylonas@ionio.gr

The Biomolecular Computation Paradigm: A Survey In Massive Biological Computation

Keywords: biomolecular computation, DNA computation, computing paradigm, computational media, parallel computing, CREW PRAM, TSP, Boolean circuits, nondeterministic Turing machine

Biomolecular computation is the scientific field focusing on the theory and practice of encoding combinatorial problems in ordinary DNA strands and applying standard biology lab operations such as cleansing and complementary sequence generation to them in order to compute an exact solution. The primary advantage offered by this computational paradigm is massive parallelism as the solution space is simultaneously searched. On the other hand, factors that need to addressed under this model are the DNA volume growth and computational errors attributed to inexact DNA matching. Biomolecular computation additionally paves the way for two-and three-dimensional self assemblying biological tiles which are closely linked at a theoretical level to a Turing machine, establishing thus its computational power. Applications include medium sized instances of TSP and the evaluation of the output of bounded fan-out Boolean circuits.

Introduction

The seminal paper [19] is widely known for essentially establishing the field of quantum computing. However, a lesser known offshoot is biomolecular computing, alternatively known as DNA computing. The founding notions of this computational paradigm were presented in [START_REF] Adleman | Molecular computation of solutions to combinatorial problems[END_REF], where it was proposed that regular DNA strands can represent combinatorial inputs instead of the functions of a living organism. Then standard lab operations can be applied to these strands in order to extract strands containing a solution. As a concrete application, the TSP was solved exactly through a brute force methodology in a medium sized graph G = (V, E) in O (|V | + |E|) elementary operations and O (log |V |) DNA strands, indicating the potential of massive parallelism. This was repeated in [START_REF] Lipton | Speeding up computations via molecular biology[END_REF] with a different algorithmic approach though in the sequence of lab operations, establishing the fact that novel and efficient algorithms are also necessary in this computational paradigm.

The primary objective of this survey is to concisely summarize the principles and notions of the paradigm of biomolecular computing with an emphasis on the potential for massively parallel computations. The latter may well serve in the dawn of the big data and 5V era as an unconventional inspiration for the designers of parallel algorithms or distributed systems.

The remaining of this survery is structured as follows. Section 2 summarizes the principal concepts of biomolecular computing, the connections to known computational models, and describes computational applications not examined elsewhere in this survey. The elementary operations, advantages, and disadvantages of the biomolecular paradigm are explained in section 3. The most important application, namely TSP, is described in 4. The parallelism potential is explored in section 5, while factors working against the computation scale up are investigated in sections 6 and 7. The main points are summarized in 8 and certain conclusions are drawn. Finally, table 1 summarizes the survey notation. Strands s1 and s2 match completely s1 s2

Strand s2 matches to the right side of s1 s1 s2

Strand s2 matches to the left side of s1 s1 s2

Strand s2 matches to a middle segment of s1 s1 s2

Strands s1 and s2 do not match

s1 ∩ s2 = k Strands s1 and s2 overlap in k bases |S| Cardinality of set S E [X] Mean value of random variable X Var [X]
Variance of random variable X

Previous Work

As stated earlier, the groundwork for the paradigm of biomolecular computing was laid in [START_REF] Adleman | Molecular computation of solutions to combinatorial problems[END_REF] followed by [START_REF] Lipton | Speeding up computations via molecular biology[END_REF]. Soon, notions and applications emerged as noted in the early surveys [START_REF] Reif | The emergence of the discipline of biomolecular computation in the US[END_REF], [START_REF] Pisanti | DNA computing: A survey[END_REF], and [START_REF] Rooß | Recent developments in DNA computing[END_REF]. The computational power of the paradigm is explored in [START_REF] Boneh | On the computational power of DNA[END_REF] and [START_REF] Beigel | Solving intractable problems with DNA computing[END_REF] and its limits in [START_REF] Dunne | P.: There is plenty of room at the bottom[END_REF]. The enormous potential for parallelism is highlighted in [START_REF] Gehani | Micro flow bio-molecular computation[END_REF], [START_REF] Reif | Parallel biomolecular computation: Models and simulations[END_REF], [START_REF] Gusfield | Algorithms on strings, trees and sequences: Computer science and computational biology[END_REF], [START_REF] Henaut | Computation with DNA[END_REF], and [START_REF] Gorban | Liquid Brain: The proof of algorithmic universality of quasichemical model of fine-grained parallelism[END_REF]. The notion of self assembly was applied to this paradigm in [START_REF] Adleman | Combinatorial optimization problems in self-assembly[END_REF], [START_REF] Rothemund | The program-size complexity of self-assembled squares[END_REF], and [START_REF] Labean | Construction, analysis, ligation, and self-assembly of DNA triple crossover complexes[END_REF]. According to this principle, which is reminiscent of non-supervised learning, DNA tiles in a test tube given proper mobility conditions and time can attach themselves to tiles or strands containing fully or partial complementary sequences without human intervention in two [START_REF] Yan | Directed nucleation assembly of DNA tile complexes for barcode-patterned lattices[END_REF][50] or three dimensions [START_REF] Kao | DNA self-assembly for constructing 3D boxes[END_REF]. Issues pertaining to complexity of the biomolecular paradigm are examined from various viewpoints in [START_REF] Amos | The complexity and viability of DNA. Biocomputing and emergent computation[END_REF], [START_REF] Reif | The design of autonomous DNA nanomechanical devices: Walking and rolling DNA[END_REF], and [START_REF] Karp | Error resilient DNA computation[END_REF].

Another way to examine the potential and the complexity of biomolecular computation is through the simulation of the operation of sequential, bounded fan-in Boolean circuits with DNA strands as first shown in [START_REF] Amos | DNA simulation of Boolean circuits[END_REF] and [START_REF] Ogihara | DNA-based self-propagating algorithm for solving boundedfan-in Boolean circuits[END_REF] and described in detail in the follow up work [START_REF] Ogihara | Simulating Boolean circuits on a DNA computer[END_REF]. Questions regarding the complexity of constructing and evaluating the output of such circuits are addressed in [START_REF] Ogihara | Circuit evaluation: Thoughts on a killer application in DNA computing[END_REF], [START_REF] Ogihara | The minimum DNA computation model and its computational power[END_REF], and [START_REF] Ogihara | Relating the minimum model for DNA computation and Boolean circuits[END_REF], whereas self assembling circuits are investigated in [START_REF] Ogihara | Executing parallel logical operations with DNA[END_REF].

Among the algorithmic applications of biomolecular computation are the brute force parallel solution of k-SAT in [START_REF] Díaz | A DNA-based random walk method for solving k-SAT[END_REF] and in [START_REF] Baum | Running dynamic programming algorithms on a DNA computer[END_REF], dynamic programming on the Cell Matrix architecture [START_REF] Wang | Implementation of a dynamic programming algorithm for DNA Sequence alignment on the Cell Matrix architecture[END_REF], and splicing systems [START_REF] Dassen | Molecular computation and splicing systems[END_REF]. Shortest path algorithms implemented in biomolecular elementary operations are presented in [START_REF] Narayanan | DNA algorithms for computing shortest paths[END_REF] and in [START_REF] Reif | Paradigms for biomolecular computation[END_REF]. Length bounded computing with DNA strands and its connections to space complexity are explored in [START_REF] Fu | Length bounded molecular computing[END_REF]. An evolutionary algorithm also expressed these operations is described in [START_REF] Deaton | A DNA based implementation of an evolutionary search for good encodings for DNA computation[END_REF].

Finally, steps regarding the implementation of a DNA computer are given in [START_REF] Hoheisel | DNA chip technology[END_REF], [START_REF] Qiu | Take advantage of the computing power of DNA computers[END_REF], [START_REF] Reif | Successes and failures[END_REF], and [START_REF] Hinze | Towards an in-vitro implementation of a universal distributed splicing model for DNA computation[END_REF], although these proposals vary. DNA operations can be also simulated over Neo4j with properties in edges corresponding to physical or chemical DNA properties in an approach similar to the one presented in [START_REF] Kontopoulos | A space efficient scheme for graph representation[END_REF] for implementing persistent data structures. Concerning software, a fully functional graphical computing environment for biomolecular computation is described in [START_REF] Carroll | A complete programming environment for DNA computation[END_REF]. It also includes DNA C, a C variant which is a combination of the C constructs pertaining to integers with an extension implementing the fundamental operations of biomolecular computing. The exclusion of floating point arithmetic should not come as a surprise, since biomolecular computation is discrete in nature and has been so far applied only in combinatorial problems. Nonetheless, should the need arise, floating point numbers can be approximated fairly well by rationals or by continued fractions. For instance, the golden ratio ϕ is represented by the infinite fraction

4 ϕ = 1 + 1 1 + 1 1 + 1 1 + . . . (1)
4 OEIS sequence A000012.

3 Paradigm Notions

Definition

Knowledge transfer and inspiration between computer science and biology has been fruitful. This relationship has already resulted in bioinformatics, connectomics, and computational biology. One of them, with direct reference to the everyday laboratory handling of DNA strands, is the paradigm of biomolecular computation which can be formally defined as Definition 1. Biomolecular computing is the art and science of using DNA strands as computational medium to appropriately encode candidate solutions to (possibly intractable for a Turing machine) combinatorial problems and using standard biological laboratory techniques in order to select an exact solution.

From definition 1 follows that any DNA encoding corresponds strictly to candidate solutions of a combinatorial problem and not to the design and functions of a living being. Also, the difference from the fields of bioinformatics and computational biology should be clear. Although the inspiration, terminology, and implementation are biological, the paradigm is definitiely computational as the objective is to codify and efficiently solve instances of intractable, at least under the conventional Turing machine model, combinatorial problems.

Abstract DNA Operations

Under the biomolecular computation paradigm the elementary operations applied to the DNA strands in the test tube are the follwing.

-Initialize(T 0 ): Crate a test tube T 0 containing each admissible candidate solution for a combinatorial problem according to a probability distribution, usually the uniform one. -Copy(T 0 , T 1 ): Copy the contents of T 0 to the tube of T 1 .

-Merge(T 0 , T 1 ): Mix the contents of T 0 and T 1 to T 0 .

-Detect(T 0 ): Examine whether T 0 is empty.

-Select(T 0 , s 0 ): Extract s 0 , if present, from T 0 .

-Extract( ): Extract strands of length . -Cleavage(s 0 , σ 0 ): Slice s 0 according to the shorter template strand σ 0 . -Anneal(s 0 ): Create double DNRA strands from a single one. -Denature(s 0 ): Create single DNA strands from a double one.

-Ligate(T 0 ): Create bonds between double strands inside tube T 0 .

The basic storage unit in this paradigm is the test tube which may contain a fixed volume of DNA strands. The latter are not necessarily of the same type. In fact, the opposite is quite common as the tube contains the results of a sequence of lab operations applied to a set of candidate solutions. It is only after the end of these operations where the solution, if any, to the instance at hand is extracted and cultivated that a test tube may contain only copies of a single strand.

TSP

Perhaps the most well known biomolecular algorithm is the one shown in algorithm 1 for solving TSP for a graph G = (V, E). Notice this is a brute force method which can be used among others to discover community structure in graphs as in [START_REF] Drakopoulos | Tensorbased semantically-aware topic clustering of biomedical documents[END_REF] and [START_REF] Kanavos | Graph community discovery algorithms in neo4j with a regularization-based evaluation metric[END_REF]. However, this approach could not be a basis for heuristic techniques such as those in [START_REF] Drakopoulos | A Neo4j implementation of fuzzy random walkers[END_REF] and [START_REF] Drakopoulos | Fuzzy random walkers with second order bounds: An asymmetric analysis[END_REF]. The primary characteristic of algorithm 1 is that all paths of length j are created in j steps. Assume that each vertex is encoded with b v and each edge with b e bases. Each vertex v k has a unique coding s k in DNA bases, while the edge (v i , v j ) is encoded as the concatenation of si and sj .

Algorithm 1 TSP expressed in biomolecular operations

Parallelism

Theoretically, the biomolecular computation paradigm can be reduced to simulating a CREW PRAM, a version of RAM with P > 1 processors and M memory locations where multiple processors can read the same memory address but only one can write any given time at a given memory address. The CREW PRAM operation set LOAD, READ, WRITE as well as the memory configuration of this machine can be simulated by a sequence of biomolecular operations as shown in [START_REF] Reif | The design of autonomous DNA nanomechanical devices: Walking and rolling DNA[END_REF] through a sequence of successive configurations of length O (log (P M )) each. Starting from a random configuration, mixing a sequence of admissible configurations, at the expense of a multiplicatively growing volume, finally yields one superconfiguration of concatenated configurations representing a desired sequence of computation, assuming that one can be found. By repeatedly applying cleavage operations, the individual configurations are extracted.

Another way to quantify the actual parallelism offered by the biomolecular paradigm is to use Amdahl's law as a benchmark

Γ = 1 (1 -γ 0 ) + γ 0 s , 0 ≤ γ 0 < 1 ( 2
)
where Γ is the actual speedup, γ 0 is the parallelizable part of the task, and s is the speedup of that part. Thus, the size of the parallelizable part plays a crucial role and essentially defines how much can be actually sped up as for infinite s

Γ → 1 1 -γ 0 ( 3
)
6 Error Free Computations

Overview

Errors in the biomolecular computation can be classified into two broad categories. The first source of errors lies in the encoding of candidate solutions as there can be partial DNA matches which may eventually create false final solutions, in other words creating false positives. Moreover, the elementary operations described above may not be executed with absolute sucess due to a number of factors. This might create depending on the nature of the operations involved either false positives or false negatives.

Encoding

Concerning the solution encoding, an obvious approach might be to choose an encoding with controllable redundancy β 0 . Namely, each bit of information is expressed with α 0 = 1 + β 0 bits in total and on average. Thus, the ratio ρ 0 of original to redundant information is

ρ 0 = 1 β 0 = 1 α 0 -1 < 1 (4)
For instance, in a graph problem with |V | if each vertex normally requires log |V | bits to encode, then it would require α 0 times as much.

Regarding the number of false negatives or false positives, it can be argued that it is proportional to the partial matches of DNA strings. While there is a case where an intended match of two DNA strands s 1 and s 2 fails, strand mismatches denoted by s 1 s 2 can be considered accurate for the most part. On the contrary, partial matches either from left or from right are with high probability indicators of failed operations, especially if the two strands overlap in only a few bases. For a single biomolecular step in the same test tube T 0 , let

u = |s 1 s 2 | u r (k) = |s 1 s 2 , s 1 ∩ s 2 = k| u l (k) = |s 1 s 2 , s 1 ∩ s 2 = k| u m = |s 1 s 2 | u o = |s 1 s 2 | (5)
denote respectively the number of DNA perfect matches, right and left matches in k bases, middle matches and no matches. Thus, in a single biomolecular step the ratios of true matches Q + and true mismatches Q -are

Q + = u + u m u + u m + |s2| k=1 u r (k) + |s2| k=1 u l (k) Q -= u o u o + |s2| k=1 u r (k) + |s2| k=1 u l (k) (6)
Another way to assess the reliability of a sequence of n 0 biomolecular operations is the following. Let π k be the success probability of each operation. The success probability π + by the product rule, assuming operation independence, is

π + = n0 k=1 π k = π 1 . . . π n0 (7)
Thus, if µ 1 ≤ π k ≤ µ 2 , then the following bounds can be derived

e -n0µ2 ≤ π + ≤ e -n0µ1 (8)
Perhaps a more accurate way to assess the average value of π + is to consider the geometric mean of the sequence

π = n0 k=1 π k 1 n 0 = µ 1 n0 k=1 1 + η k µ 1 1 n 0 , π k = µ 1 + η k (9)

Trials

Due to the nature of the actual biological operations, they are not always executed with abolute correctness. This can be attributed to a number of reasons including the age, technology, and condition of lab equipment, the chemistry and quantity of DNA strands themselves, the nature of bonds between strands, and lab conditions such as radiation and electomagnetic pulses of various frequences. As a result, a strand encoding an invalid solution can emerge from the test tubes or a strand containing the solution can be missed in them [8][7].

The geometric distribution models sequences of test outcomes where the probability of success is p 0 . Its probability mass function is defined as

prob {X = k} = p 0 (1 -p 0 ) k , k ∈ Z + (10)
The interpretation of X is that it models the number of failed attempts of an experiment before the single successful outcome of that experiment. The mean value of this distribution is readily calculated in equation [START_REF] Dassen | Molecular computation and splicing systems[END_REF].

E [X] = +∞ k=0 k prob {X = k} = 1 -p 0 p 0 = e logit(1-p0) (11)
The logit (•) function is the inverse of the sigmoid function extensively used to train deep recurrent and tensor stack networks [START_REF] Drakopoulos | Knowledge mining with tensor algebra[END_REF] expresses the logarithm of the odds of a single Bernoulli trial. Also is a special case of a link function to the generalized linear model and leads to the logistic regression, commonly found in deep learning applications.

The variance of X is its mean value scaled by the success probabilty p 0 . This is coherent with intuition, since the larger p 0 , the fewer attempts are required to achieve success and the number of failed attempts will be close to zero.

Var [X] = +∞ k=0 (k -E [X]) 2 prob {X = k} = 1 -p 0 p 2 0 = E [X] p 0 (12)

Volume Considerations

The major practical limitation of biomolecular computation is the volume necessary to represent each candidate solution. This is limited not only by the volume of the test tube, but also by the encoding which, in turn, implies a redundancy rate to ensure higher operation success probabilites. If V 0 is the hard limit for the test tube volume, α 0 the encoding redundancy factor, n is the number of candidate solutions, and 0 the solution length, then

V 0 ≥ (a 0 n 0 ) 1+ ⇔ n ≤ 1 a 0 0 V 1 1+ 0 0 ( 13
)
where 0 is a constant which depends on a number of diverse factors such as lab temperature and tube technology. If a biomolecular computation requires J 0 steps to complete, then the required volume grows exponentially. Then, the above limit should be modified as

n ≤ 1 a 0 0 V 1 J 0 (1+ 0 ) 0 (14)

Conclusions

This survey explores the foundations, applications, and limits of biomolecular computation which represents an alternative computational paradigm. The latter is based on the handling of potentially very long strands of ordinary DNA using standard biology lab operations such as annealing, generating a complementary strand, selecting a strand, or concatenating two strands. These strands do not codify the inner workings of any living organism. Instead, they contain a suitably selected representation of a computational problem. By selecting an appropriate representation of an input instance, a plethora of various output instances are created by a series of biological operations. Although a fraction of the abovementioned output instances may contain incomplete operations and must be removed by cleansing operations, their majority will contain with high probability a solution.

7 :

 7 Require: tubes T0, Tv with encoded vertices; tube Te with encoded edges Ensure: a Hamilton circle is found 1: initialize(T0) 2: for j ← 1 to |V | do 3: merge(T0, Te) extract(|V | (bv + be)) 8: denature(T0) 9: return detect(T0)

Table 1 .

 1 Survey notation.

	Symbol	Meaning
	=	Definition or equality by definition
	s , s	DNA strand s in 5-3 and 3-5 direction respectively
	s	Complementary DNA strand of s in 5-3 direction
	|s|	Length (number of bases) of DNA strand s
	s1 s2

Drakopoulos, Tsolis, Stefani, and Mylonas

Acknowledgments

The financial support by the European Union and Greece (Partnership Agreement for the Development Framework 2014-2020) under the Regional Operational Programme Ionian Islands 2014 -2020 for the project "Smart vine variety selection and management using ICT -EYOINOS" is gratefully acknowledged.