The study of functional associations between ncRNAs and human diseases is a pivotal task of modern research to develop new and more e ective therapeutic approaches. Nevertheless, it is not a trivial task since it involves entities of di erent types, such as microRNAs, lncRNAs or target genes. Such a complexity can be faced by representing the involved biological entities and their relationships as a network and by exploiting network-based computational approaches able to identify new associations. However, existing methods are limited to homogeneous networks or can exploit only a limited set of the features of biological entities. To overcome the limitations of existing approaches, we proposed the system LP-HCLUS, which analyzes heterogeneous networks consisting of several types of objects and relationships, each possibly described by a set of features, and extracts hierarchically organized, possibly overlapping, multi-type clusters that are subsequently exploited to predict new ncRNA-disease associations. Our experimental evaluation shows that, according to both quantitative (i.e., TPR@k, ROC and PR curves) and qualitative criteria, LP-HCLUS produces better results.
High-throughput sequencing technologies and recent, more e cient computational approaches, have been fundamental for the rapid advances in functional genomics. Among the most relevant results, there is the discovery of thousands of non-coding RNAs (ncRNAs) with a regulatory function on gene expression.
In parallel, the number of studies reporting the involvement of ncRNAs in
the development of many di erent human diseases has grown exponentially. The
Copyright c 2020 for this paper by its authors. Use permitted under Creative
Commons License Attribution 4.0 International (CC BY 4.0). This volume is published
and copyrighted by its editors. SEBD 2020, June 21-24, 2020, Villasimius, Italy.
rst type of ncRNAs that has been discovered and largely studied is that of
microRNAs (miRNAs), classi ed as small non-coding RNAs in contrast with long
non-coding RNAs (lncRNAs), that are ncRNAs longer than 200nt. While
miRNAs primarily act as post-transcriptional regulators, lncRNAs have a plethora of
regulatory functions [
In this discussion paper, we describe the method LP-HCLUS [
LP-HCLUS exploits a combined approach based on hierarchical, multi-type clustering and link prediction. As we will detail in the next section, a multi-type cluster is actually a heterogeneous sub-network. Therefore, the adoption of a clustering-based approach allows LP-HCLUS to base its predictions on relevant, highly-cohesive heterogeneous sub-networks. Moreover, the hierarchical organization of clusters allows it to perform predictions at di erent levels of granularity, taking into account either local/speci c or global/general relationships. 2
In the following, we introduce the notation and some useful de nitions. De nition 1 (Heterogeneous attributed network). A heterogeneous attributed network is a network G = (V; E), where V is the set of nodes and E is the set of edges, and both nodes and edges can be of di erent types. Moreover: { T = Tt [ Ttr is the set of node types, where Tt is the set of target types, i.e. considered as target of the clustering/prediction task, and Ttr is the set of task-relevant types. Only nodes of target types are clustered and considered in the identi cation of new relationships. { Each node type Tv 2 T de nes a subset of nodes in the network, i.e., Vv V . { Each node type Tv 2 T is associated with a set of attributes Av = fAv;1; Av;2; :::; Av;mv g, i.e., nodes of the type Tv are described by the attributes Av. { R is the set of all the possible edge types. { Each edge type Rl 2 R de nes a subset of edges El E. C2 C3 C4 C5
C1, C2 C4, C5
C1, C2, C3 (b)
C1, C2, C3,
C4, C5 (a)
De nition 2 (Hierarchical multi-type clustering). A hierarchy of multitype clusters is de ned as a list of hierarchy levels [L1; L2; : : : ; Lk], where each Li consists of a set of overlapping multi-type clusters. For each level Li; i = 2; 3; :: : : : k, 8 G0 2 Li 9 G00 2 Li 1, such that G00 is a subnetwork of G0 (Fig. 1). According to these de nitions, we de ne the task considered in this work. De nition 3 (Predictive hierarchical clustering for link prediction). Given a heterogeneous attributed network G = (V; E) and the set of target types Tt, the goal is to nd: { A hierarchy of overlapping multi-type clusters [L1; L2; : : : ; Lk]. { A function (w): Vi1 Vi2 ![0; 1] for each hierarchical level Lw (w 2 1; 2; :::; k), where nodes in Vi1 are of type Ti1 2 Tt and nodes in Vi2 are of type Ti2 2 Tt. Each function (w) maps each possible pair of nodes (of types Ti1 and Ti2 ) to a score representing the degree of certainty of their relationship. In this paper LP-HCLUS has been used to solve the task formalized in De nition 3, by considering ncRNAs and diseases as target types. Hence, we determine two distinct set of nodes denoted by Tn and Td, representing the set of ncRNAs and the set of diseases, respectively. In the following subsections, we will describe the main steps executed by LP-HCLUS (see Fig. 2 for a general overview).
In the rst phase, we estimate the strength of the relationship among all the
possible ncRNA-disease pairs in the network G. In particular, we aim to
compute a score s(ni; dj ) for each possible pair ni; dj , by exploiting the concept of
meta-path. According to [
Estimation of the strength of relationships Predicted relationships d1 s(n1, d1) n1 d3 s(n1..,.d3) n1 di s(nk, di) nk
Extracted edges w1 w2 ... w|Ê| Prediction
Construction of the hierarchy of clusters Hierarchy of clusters
Therefore, by assimilating the score associated with an interaction to its degree of certainty, we compute s(ni; dj ) as the maximum value observed over all the possible meta-paths between ni and dj . Formally: s(ni; dj ) =
max
P 2metapaths(ni;dj)
pathscore(P; ni; dj )
(1)
where metapaths(ni; dj ) is the set of meta-paths connecting ni and dj , and
pathscore(P; ni; dj ) is the degree of certainty of the relationship between ni and
dj according to the meta-path P . In order to compute pathscore(P; ni; dj ), we
represent each meta-path P as a nite set of sequences of nodes. If a sequence
in P connects ni and dj , then pathscore(P; ni; dj ) = 1. Otherwise, following
the same strategy introduced before, it is computed as the maximum similarity
between the sequences which start with ni and the sequences which end with dj
(see Fig. 3). The intuition behind this formula is that if ni and dj are not directly
connected, their score represents the similarity of the nodes and edges they are
connected to. The similarity between two sequences seq0 and seq00 is computed
according to the the attributes of all nodes involved in the two sequences:
following [
The ordering relation <c de nes a greedy search strategy that guides the order in which pairs of clusters are analyzed. <c is based on the cluster cohesiveness h(c), that corresponds to the average score in the cluster, namely: h(C) = jpair1s(C)j P(ni;dj)2pairs(C) s(ni; dj ), where pairs(C) is the set of all the possible ncRNA-disease pairs that can be constructed from the set of ncRNAs and diseases in the cluster. Accordingly, if C0 and C00 are two di erent clusters, the ordering relation <c is de ned as follows: C0 <c C00 () h(C0) > h(C00).
The approach adopted to build the other hierarchical levels is similar to the
merging step performed to obtain L1. The main di erence is that we do not
obtain bicliques, but generic multi-type clusters. Since the biclique constraint is
removed, we need another stopping criterion for the iterative merging procedure.
Coherently with approaches used in hierarchical co-clustering and following [
In the last phase, we exploit each level of the identi ed hierarchy of multi-type clusters as a prediction model. In particular, we compute, for each ncRNAdisease pair, a score representing its degree of certainty on the basis of the multi-type clusters containing it. Formally, let Ciwj be a cluster identi ed in the w-th hierarchical level in which the ncRNA ni and the disease dj appear. We compute the degree of certainty of the relationship between ni and dj as:
(w)(ni; dj ) = h Ciwj , that is, we compute the degree of certainty of the new
interaction as the average degree of certainty of the known relationships in the
cluster. In some cases, the same interaction may appear in multiple clusters,
since the proposed algorithm is able to identify overlapping clusters. In this
case, Ciwj represents the list of multi-type clusters in which both ni and dj appear
and we aggregate their cohesiveness values according to four di erent strategies:
maximum, minimum, average and evidence combination [
LP-HCLUS has been run with di erent values of its input parameters. In
particular, following the results obtained in [
We compared LP-HCLUS with the following competitors:
i) HOCCLUS2 [
We adopted the 10-fold cross validation on the set of known ncRNA-disease relationships and, due to absence of negative samples, we evaluated the results in terms of TruePositiveRate@k curve. Moreover, we also report the results in terms of ROC and Precision-Recall curves by considering the unknown relationships as negative examples. We remark that ROC and PR curves can only be used for relative comparison and not as absolute evaluation measures because they are spoiled by the assumption made on unknown relationships.
In Figs. 4 and 5 we show some results obtained with the most promising
congurations. From the quantitative viewpoint, we can observe that the proposed
method LP-HCLUS, with the combination strategy based on the maximum, is
able to obtain the best performances, for all the considered measures. From a
qualitative point of view, we rst performed a comparative analysis between the
results obtained by LP-HCLUS against the validated interactions reported in
the updated version of HMDD (i.e., v3.2 released on March 27th, 2019). We
found 3,055 LP-HCLUS predictions con rmed by the new release of HMDD at
the hierarchy level 1, 4,119 at level 2 and 4,797 at level 3. Next, we conducted a
qualitative analysis of the top-ranked relationships predicted by LP-HCLUS
using ID dataset, selecting only those with a score equal to 1.0. For this purpose, we
exploited MNDR v2.0, which is a comprehensive resource including more than
260,000 experimental and predicted ncRNA-disease associations for mammalian
species. Also in this case, we found some associations in both MNDR and in the
list of predicted associations by LP-HCLUS. A more comprehensive analysis,
reporting several additional examples, can be found in the full paper [
In this paper, we have tackled the problem of predicting possibly unknown ncRNA-disease relationships. The proposed approach LP-HCLUS is able to take advantage from the possible heterogeneous nature of the attributed biological network analyzed. The results con rm the initial intuitions and show competitive performances of LP-HCLUS in terms of accuracy of the predictions, also when compared with state-of-the-art competitor systems. These results are also supported by a comparison of LP-HCLUS predictions with data reported in MNDR and by a qualitative analysis that revealed that several ncRNA-disease associations predicted by LP-HCLUS have been subsequently experimentally validated and introduced in a more recent release (v3.2) of HMDD. As future work, we will evaluate the performance of LP-HCLUS in other domains. 5
We acknowledge the support of Ministry of Education, Universities and Research (MIUR) through the PON project TALIsMAn - Tecnologie di Assistenza personALizzata per il Miglioramento della quAlita della vitA (ARS01 01116). Dr. Gianvito Pio acknowledges the support of Ministry of Education, Universities and Research (MIUR) through the project AIM1852414, activity 1, line 1.