BACKGROUND
one of the major challenges in systems biology is to combine in a meaningful way the large corpus of molecular biology knowledge recapitulated in the form of large interaction networks together with high-throughput omics data  <cit> .
there exist numerous methods using biological networks for making insightful high-throughput data analysis  <cit> .
these methods can be separated in three large groups, concentrating on:  mapping the data on top of a pre-defined biological network layout,  identifying subnetworks from a global network possessing certain properties computed from the data , and  using biological network structure for pre-processing the high-throughput data .
quantitative omics data can be mapped on top of a pre-defined biological network layout.
currently, most of the pathway databases  already provide these features using simple and advanced data visualization tools.
omics data visualization tools onto networks are constantly improving and become more elaborated  <cit> .
for example, the vanted tool  <cit>  creates a classification tree according to the kegg pathway hierarchy and shows a biological network with omics data as barplots or pie-charts attached to the nodes allowing the visualization of complex data with other means than simple node coloring.
navicell  <cit>  and related pathway database atlas of cancer signalling network  together with standard heat maps and barplots provide more flexible data visualization tools such as glyphs  and map staining   <cit> .
an interesting approach for data visualization using biological networks was developed in netgestalt online tool  <cit> .
this tool is based on a netsam r package to create modules by hierarchical ordering of the network in one dimension and visualizes high-throughput data according to a chosen track as a combination of barplots and heat maps.
omics data are used to identify overexpressed or enriched subnetworks.
for example, in  <cit> , expression data were combined with network information in order to identify under- or overexpressed subnetworks in huntington’s disease and breast cancer.
inspired by this method, several cytoscape plug-ins were developed and applied to various omics data in order to find connected sub-components where most of the genes were differentially expressed or co-expressed  <cit> .
a recent review presents the integration of molecular profiles with networks in order to find “network modules”  <cit> .
projection of the high-throughput data into the basis of smooth functions defined on a biological network graph was suggested in  <cit> .
recently, biological networks were used to regularize the genome-wide mutational landscapes  in cancer, applying network smoothing methods  <cit> .
however, none of the methods cited above had the purpose to visualize high-throughput data by computing a specific network layout based on the omics data themselves, which would combine both the network structure and the data associated to the network node attributes.
some of the existing cytoscape layout algorithms  allow exploiting the values of single node attributes, but this possibility is currently under-developed.
we believe that using networks for visualizing and analyzing data requires methods that would be able to create more suitable biological network layouts adapted for a particular task.
mathematically speaking, molecular entities exist in two metric spaces.
the first one is the space of biological functions, where the distance between two molecules can be defined by the number of steps  in a graph defining pairwise functional relations  along the shortest path connecting them.
the other metric space is the data space, where the distance between two molecules is defined by the proximity of the corresponding numerical descriptors .
the network distances are usually visualized by designing a 2d or 3d layout, representing the network structure.
visualization of distances in data space is achieved by data dimension reduction methods  projecting multidimensional vectors in 2d or 3d space.
dimension reduction techniques were already used for producing biological network layouts.
for example, golorize cytoscape plugin computes the layout of a biological network using the results of go enrichment analysis  <cit> .
some existing methods apply multidimensional scaling to the distance matrix defined by the graph path distance  <cit> .
these methods have the purpose to construct more appealing network layouts.
however, they usually do not use the multidimensional data attached to the network nodes.
therefore, they can not be adapted for visualization of a particular dataset.
on the other hand, there exist a number of convenient software allowing the construction and visualization of the structure of correlation graphs, computed from multidimensional data, e.g., biolayout express3d  <cit>  or arena3d  <cit> .
however, these representations do not use the knowledge of the structure of real biological networks since they are not inferred from the data by correlation analysis.
we believe that in certain analyses, it could be insightful to construct the biological network layout based simultaneously on the network structure and the associated multidimensional data.
one possible solution consists in applying data dimension reduction techniques.
in order to allow cytoscape users to conveniently apply linear and non-linear dimension reduction methods accompanied by network-based data regularization, we have developed dedal, a cytoscape  <dig> app for computing and mixing data-driven and structure-driven network layouts.
unlike many other methods, the purpose of dedal is not to improve the visual appeal of the biological network layout, but to modify it in such a way that the trends in the associated data and exceptions from these trends would be detectable more easily.
implementation
dedal is a simplified cytoscape  <dig> app implemented in java language.
for computing linear and non-linear principal manifolds, dedal uses vdaoengine java library .
for computing the eigenvectors of a symmetric laplacian matrix, the parallelized colt library has been used .
internal graph implementation is re-used from binom cytoscape plugin .
the source code of dedal is available at http://bioinfo-out.curie.fr/projects/dedal/.
producing data-driven network layouts
data-driven network layout  is produced by dedal by positioning the nodes of the network according to their projection from the multidimensional data space of associated numerical vectors into a 2d space.
dedal implements three algorithms for performing this dimension reduction:  projection onto a plane of two selected principal components;  projection onto a non-linear 2d surface approximating the multidimensional data distribution, i.e.
principal manifold, computed by the method of elastic maps ; and  use of  or  preceded by network-based regularization  of the data, based on computing the k first eigenvectors of the laplacian matrix of the network graph and projecting data into this subspace .
dedal implements specific data pre-processing and resulting layout post-processing steps.
pre-processing steps include  selecting only nodes whose associated numerical vectors  are sufficiently complete and  optional double centering of the data matrix.
post-processing of the resulting layout includes  avoiding overlap between node positions by moving them in a random direction at a small distance;  moving the outliers  closer to the barycenter of the data distribution; and  placing the nodes with missing data into the mean point of the position of their network neighbours.
in future work, an effort will be made to project the data in the three dimensional space, or exploit the concept of multi-level  <dig> d network representation  <cit> .
we would like to let the user rotate the network layout in order to better visualize the network substructures which are difficult to represent in 2d space, as it is done in biolayout 3d software  <cit> .
we also plan to implement in dedal more flexible dimension reduction algorithms such as multidimensional scaling which will extend the data representation possibilities, better answering to specific user’s needs .
finally, more sophisticated strategies of network layout morphing will be developed, taking into account the data.
we will also improve the function for avoiding extensive node overlapping.
manipulating network layouts in dedal
in order to allow the comparison of the resulting ddls with standard layouts produced by cytoscape and to transform one into another, dedal implements simple layout morphing and aligning methods.
morphing of two network layouts is performed by a linear transformation, moving matched nodes along straight lines.
dedal provides a convenient user dialog for morphing one layout into another so that the user can immediately appreciate the morphing result.
the morphing operation provides poor results if one layout is systematically rotated or flipped with respect to the node positions in another one.
dedal allows aligning two network layouts by rotating, mirroring, and minimizing the euclidean distance between two layouts.
double-centering the data matrix
the data matrix is optionally double-centered by subtracting from each matrix entry the mean value calculated over the corresponding matrix row and the mean value calculated over the matrix column, followed by adding the global mean value computed over all matrix entries.
this procedure eliminates some global biases in the data such as the global differences in average fluorescence intensity of different probes in microarray data.
network-based smoothing of data
dedal perfoms network data smoothing, as suggested in  <cit> .
for a graph representing the biological network, its laplacian and all its eigenvectors are computed.
these vectors define a new orthonormal basis in the multidimensional data space.
to smooth the values of the data matrix, the initial multidimensional vector associated to a datapoint is projected into the subspace spanned by the first smallest k eigenvectors of the graph’s laplacian.
dedal smoothing parameter is defined by pns=1−k−n−,pns∈, where nc is the number of connected components in the graph and n is the number of nodes on the graph.
therefore, pns= <dig> corresponds to k=n, i.e.
when no smoothing is performed and all eigenvectors are used, while pns= <dig> corresponds to k= and the first two non-degenerated eigenvectors are used to smooth the data.
in the latter case, the data become effectively three-dimensional, with the first dimension corresponding to the average value of the data matrix computed over each connected component of the graph.
exporting the pre-processed data
the results of pre-processing the data for a given network can be exported to a file.
actually, two files are created: one in a simple tab-delimited format suitable for further analyses in most of statistical software packages and another file in the “.dat” format, suitable for analyses in vidaexpert multidimensional data visualization tool  <cit> .
that way, network smoothing of an expression dataset can be done for further application in any machine learning algorithms .
for this purpose, dedal can be also used in a command line mode .
computing principal components and principal manifolds
the principal components in dedal are computed using singular value decomposition by the method that allows the treatment of missing data values without pre-imputing them, as it is described in  <cit> .
data points, containing more than  <dig> % of missing values are filtered out from the analysis.
dedal computes the  <dig> first principal components if there are more than  <dig> data points, and k principal components if there are k+ <dig> data points, with k< <dig>  after computing the principal components, dedal reports the amount of variance explained by each of the principal components.
time-efficient method of elastic maps for computing principal manifolds  also allows dealing with missing data without pre-imputing them.
in this case, a 2d rectangular manifold is computed, and the amount of variance explained by it is reported.
continuous layout morphing
morphing two network layouts is performed by a simple linear transformation.
a node having position  in the initial layout and the position  in the target layout is placed during the morphing procedure in the position x <dig> p×x22+x12), where p∈  is the morphing parameter representing the fraction of distance between the initial and target node positions along the straight line.
aligning two network layouts by rotation and mirroring
morphing between two network layouts might be meaningless if all nodes in one layout are systematically rotated or flipped with respect to the node positions in another layout.
this situation is often the case when producing the pure data-driven layout and comparing it to the initial structure-driven layout.
in this case, dedal allows minimizing the euclidean distance between two layouts defined as the sum of squared euclidean distances between all matched nodes with respect to all possible rotations and mirroring of one of the layouts.
dedal provides an option to align networks before morphing them.
also, a user can align several network layouts to one chosen reference network layout, using a separate “layout aligning” dialog.
for example, it is usually useful to align the structure-driven layouts to the pca-based data-driven layout.
using dedal in command line mode
dedal can be used separately from the cytoscape environment, in the command line mode, as it is explained on the dedal website with several examples.
this is especially recommended for computing data-driven layouts for large networks containing more than ten thousand nodes.
command line mode allows applying all data pre-processing steps, including double-centering and network smoothing, saving the resulting network layout as a xgmml file and saving the eigenvector decomposition of the laplacian of the network graph for future use.
RESULTS
using tcga transcriptome data and hprd network
we used the cancer genome atlas  transcriptomic dataset for breast cancer  <cit>  and human protein reference database  database  <cit>  as a source of protein-protein interaction network.
firstly, as an example of a small subnetwork, we selected proteins involved in fanconi dna repair pathway  <cit>  as it is defined in atlas of cancer signaling network  <cit> .
for node coloring, we mapped the value of the t-test computed for the gene expression difference between the basal-like  and non basal-like breast tumors.
we have imported the tcga data in cytoscape and applied dedal for the transcription levels of the genes in the subnetwork .
fig.
<dig> using dedal for visualizing fanconi pathway in breast cancer.
top row: standard organic layout , pca-based ddl , morphing two previous layouts at half-distance .
bottom row from left to right: pca-based ddl computed only for basal-like tumors , pca applied to network-smoothed profile, ddl computed using elastic map  algorithm for computing non-linear principal manifold.
red color denotes larger positive values of the t-test computed for the difference between basal-like and non basal-like groups of samples, green color corresponds to negative values of the t-test
one can see  that the first principal component sorts the nodes according to the t-test, because in this case the first principal component is associated with the basal-like breast cancer subtype.
the second principal component gives additional information such as the fact that the expression levels of brca <dig> and fance are differently modulated, though both are upregulated in the basal-like subtype.
morphing the organic network layout  with the pca-based layout moves the position of some of the genes, keeping the general pattern of pca preserved, while better reflecting the network structure .
we have also applied pca-based ddl to the subset of basal-like breast tumors  which showed the specific role of brca <dig> gene in this subtype confirming a known fact.
also, the position of usp <dig> gene has significantly changed with respect to the pca-based ddl produced for the whole set of samples.
this demonstrates the ability of dedal to produce network layouts specific for a particular cancer subtype.
application of network smoothing is demonstrated in fig.
<dig>  bottom middle.
the layout preserves the general pattern of the pca-based ddl, while better visualizing the network structure, and moving some proteins into a different position.
for example, brca <dig> gene is moved to the left because it is connected to several genes overexpressed in basal-like breast cancer subtype.
figure  <dig>  bottom right, shows the application of non-linear pca to data dimension reduction.
this network layout better resolves the relations between some gene expression levels such as fancf and hes <dig> and the roles of brca <dig> and brca <dig> in fanconi dna repair pathway.
visualizing rna-seq tissue expression data onto the network of tissue-specific genes
in order to illustrate the added value of dedal for visualizing expression data on top of relatively large networks, we constructed a tissue-specific subnetwork from hprd global network of protein-protein interactions  using the following approach.
rna-seq data containing transcriptomes for  <dig> healthy human tissues were obtained from  <cit> .
replicate measurements were averaged in order to obtain a single transcriptomic profile per tissue.
in each profile, the genes were ranked according to their expression and the most significant largest connected component  of the global ppi network directly connecting the top ranked genes  was identified using binom plugin  <cit>  .
after this step, the tissue-specific subnetworks that showed a significant score for the size of lcc were merged.
this resulted in a network containing  <dig> nodes, representing the top genes that are highly expressed in at least one tissue type, and  <dig> edges representing direct ppis between them.
dedal was applied to this network and the whole set of tissue transcriptomes.
double-centering and network smoothing with retaining only  <dig> % of smallest eigenvectors was applied at the pre-processing step, and the non-linear principal manifold was computed for dimension reduction.
even without application of morphing to a structure-driven network layout, this procedure produced an insightful visualization of the network containing several clusters and connections between them .
mapping transcriptomes of different tissues  clearly highlights different network clusters with this layout.
the configuration of the clusters reflects the proximity of them in the data space of healthy tissue transcriptomes.
fig.
<dig> using dedal for visualizing the network and rna-seq expression data of tissue-specific genes.
rna-seq dataset for  <dig> healthy human tissues was used to defined a subnetwork of hprd ppi database enriched in tissue-specific genes .
network smoothing followed by computation of principal manifold was applied to produce the data-driven network layout .
patterns of gene expression for two selected tissues  are shown on top the constructed ddl, red color denotes higher expression, green color corresponds to lower expression.
the sizes of the nodes are proportional to their connectivity degree in this network.
on the left top panel application of the force directed layout is shown for comparison.
on the left bottom panel results of quantitative comparison between multidimensional distance representation in dedal and force directed layout are shown.
the most representative distances between the genes in the initial multidimensional space  are ranked here from the largest to the smallest values
in order to objectively evaluate the advantage of using dedal for data visualization, we quantified how well the distances between the genes in the multidimensional space were reproduced on the 2d plane.
we computed the correlations between gene pair-wise euclidean distances in multidimensional space and in their configuration in a 2d network layout.
we compared dedal with force directed layout frequently used to layout large networks.
since the full distance matrix contains many dependent distance values, one has to select the most representative distances for computing these correlations .
such approach was applied before to quantify the goodness of between-point distance representation after projecting them into a low-dimensional space   <cit> .
application of this approach in this case study showed improved pearson correlation between the distances from  <dig>   to  <dig>  , leading to increase of correlation coefficient statistical significance by  <dig> orders of magnitude .
the absolute value of the correlation remains moderate because projection of multidimensional data into 2d leads to significant loss of information.
force directed layout produces significant  correlation because in this case, the biological network was specifically constructed to match the variance in the dataset.
the later underlines the importance of carefull biological network selection for data visualization purposes.
visualizing genetic interactions
genetic interaction between two genes reflects their synergistic  or mutually alleviating  functions the strength of genetic interactions is characterized by an epistatic score which quantifies deviation from a simple multiplicative model  <cit> .
in the global network of genetic interactions, each gene can be characterized by its epistatic profile, i.e., a vector of epistatic scores with all other genes  <cit> .
it is shown that the genes with similar epistatic profiles tend to have similar cellular functions.
we applied dedal to create a ddl layout for a group of yeast genes involved in dna repair and replication.
the genetic interactions between these genes and the epistatic profiles  were used from  <cit> .
the definitions of dna repair pathways were taken from kegg database  <cit> .
figure  <dig> shows the difference between application of the standard organic layout for this small network of genetic interactions and pca-based ddl .
pca-based ddl, in this case, groups the genes with respect to their epistatic profiles.
firstly, local hub genes rad <dig> and pol <dig> have distinct position in this layout.
secondly, pca-based ddl roughly groups the genes accordingly to the dna repair pathway in which they are involved.
for example, it shows that non-homologous end joining  dna repair pathway is closer to homologous recombination  pathway than to the mismatch repair  pathway.
it also underlines that some homologous recombination genes  are characterized by a different pattern of genetic interactions than the “core” hr genes rad <dig>  rad <dig>  rad <dig>  rad <dig>  rad <dig>
fig.
<dig> using dedal for visualizing network of genetic interactions between yeast genes involved in dna repair.
red and green edges denote positive and negative genetic interactions correspondingly.
different node colors indicate three distinct dna repair pathways in yeast
visualizing attractors of a boolean model
in this example, we used the boolean model of cell fate decisions between survival, apoptosis and non-apoptotic cell death  published in  <cit> , to group the nodes of the influence diagram according to their co-activation patterns in the logical stable states.
the table of stable states was taken from  <cit>   and used to compute the pca-based ddl .
in this ddl, nodes in close positions have similar pattern of activation in stable states .
we used morphing pca-based ddl and the initial layout of the model  to visualize several stable states corresponding to different cell fates .
in this layout co-activated nodes tend to form compact groups.
therefore, dedal can be used to design layouts of mathematical models of biological networks, using the solutions of the model.
applying dedal in this analysis highlighted the functional importance of different interactions in the model and identified dynamical modules composed of variables participating in the same fate decision.
fig.
<dig> using dedal for visualizing results of a boolean model simulation.
table of computed stable states is used to group the nodes with similar states in similar conditions .
in the influence diagram green edges signify inhibitory and red edges - activating relations.
the model network layout is produced by applying morphing of a data-driven layout with the initial layout suggested by modeler
fig.
<dig> using dedal for visualizing results of a boolean model simulation.
visualization of three stable states of the model, with green and red denoting inactive  and active  states of the node correspondingly
scalability of dedal for large networks
dedal scales very well with respect to computing data projections into 2d space .
even for the networks containing ten thousand nodes and more , dedal computes linear and non-linear data projections for few hundreds of samples in less than few tens of seconds on an ordinary laptop.
fig.
<dig> scalability of dedal for large networks.
the figure shows the number of seconds needed for dedal to compute network smoothing , first ten principal components  and the principal manifold  for a set of  <dig> ovarian cancer transcriptomes and a series of networks with increasing number of nodes .
network smoothing scaling is separately shown for the case of de-novo computation of the eigenvector decomposition of the network laplacian  and for the case of using the pre-computed eigenvector decomposition .
the benchmarking was done in the command line mode of dedal
however, the network smoothing data pre-processing step implemented in dedal requires eigenvector decomposition of the laplacian matrix of the network graph which scales in time as the third power of the number of nodes.
while this computation remains relatively fast for relatively large networks , it drastically slows down when the size of the network grows above several thousands of nodes.
in our benchmark example, eigenvector decomposition of the laplacian of the whole hprd ppi database required  <dig> hours on a regular laptop, which makes application of network smoothing data pre-processing not convenient for large networks.
however, eigenvector decomposition of the laplacian for a large graph can be done once and saved on the disk for future reuse.
for example, on the dedal website we provide the pre-computed eigenvector decomposition for the laplacian of the graph representing the whole hprd database, and other decompositions for large ppi networks will be provided in the future.
using pre-computed eigenvector decomposition allows applying data network smoothing with large networks containing tens of thousands nodes in a reasonable time .
use of dedal with large networks containing tens of thousands of nodes is recommended in command line mode .
the computed network layout can be imported into cytoscape environment and used for mapping high-throughput data on top of them.
CONCLUSIONS
dedal cytoscape plugin combines the classical and advanced data dimension reduction methods with the algorithms of network layouting inside cytoscape environment.
this ability can be used in a number of ways and for many applications, some of them are suggested in this paper.
the application of dedal is not limited to producing data-driven network layouts.
more generally, dedal allows the application of dimension reduction of the multivariate data associated with the nodes of any cytoscape network, optionally using the structure of the network, and exports the results for further analyses by any suitable algorithms.
availability and requirements
project name: dedal: data-driven network layoutingproject home page:http://bioinfo-out.curie.fr/projects/dedal/operating system: platform independentprogramming language: javaother requirements: java  <dig>  or higher, cytoscape  <dig>  or higherlicense: gnu lgplany restrictions to use by non-academics: free for any non-commercial use
competing interests
the authors declare that they have no competing interests.
authors’ contributions
az and uc developed the algorithm.
uc and az wrote the application code.
uc, lc and az provided the examples of using dedal.
az and uc wrote the manuscript.
az, lc, eb have read and revised the manuscript.
all authors read and approved the final manuscript.

 one of the major challenges in systems biology is to combine in a meaningful way the large corpus of molecular biology knowledge recapitulated in the form of large interaction networks together with high-throughput omics data. there exist numerous methods using biological networks for making insightful high-throughput data analysis. these methods can be separated in three large groups, concentrating on: mapping the data on top of a pre-defined biological network layout, identifying subnetworks from a global network possessing certain properties computed from the data, and using biological network structure for pre-processing the high-throughput data. quantitative omics data can be mapped on top of a pre-defined biological network layout. currently, most of the pathway databases already provide these features using simple and advanced data visualization tools. omics data visualization tools onto networks are constantly improving and become more elaborated. for example, the vanted tool creates a classification tree according to the kegg pathway hierarchy and shows a biological network with omics data as barplots or pie-charts attached to the nodes allowing the visualization of complex data with other means than simple node coloring. navicell and related pathway database atlas of cancer signalling network together with standard heat maps and barplots provide more flexible data visualization tools such as glyphs and map staining. an interesting approach for data visualization using biological networks was developed in netgestalt online tool. this tool is based on a netsam r package to create modules by hierarchical ordering of the network in one dimension and visualizes high-throughput data according to a chosen track as a combination of barplots and heat maps. omics data are used to identify overexpressed or enriched subnetworks. for example, in, expression data were combined with network information in order to identify under- or overexpressed subnetworks in huntington’s disease and breast cancer. inspired by this method, several cytoscape plug-ins were developed and applied to various omics data in order to find connected sub-components where most of the genes were differentially expressed or co-expressed. a recent review presents the integration of molecular profiles with networks in order to find “network modules”. projection of the high-throughput data into the basis of smooth functions defined on a biological network graph was suggested in. recently, biological networks were used to regularize the genome-wide mutational landscapes in cancer, applying network smoothing methods. however, none of the methods cited above had the purpose to visualize high-throughput data by computing a specific network layout based on the omics data themselves, which would combine both the network structure and the data associated to the network node attributes. some of the existing cytoscape layout algorithms allow exploiting the values of single node attributes, but this possibility is currently under-developed. we believe that using networks for visualizing and analyzing data requires methods that would be able to create more suitable biological network layouts adapted for a particular task. mathematically speaking, molecular entities exist in two metric spaces. the first one is the space of biological functions, where the distance between two molecules can be defined by the number of steps in a graph defining pairwise functional relations along the shortest path connecting them. the other metric space is the data space, where the distance between two molecules is defined by the proximity of the corresponding numerical descriptors. the network distances are usually visualized by designing a 2d or 3d layout, representing the network structure. visualization of distances in data space is achieved by data dimension reduction methods projecting multidimensional vectors in 2d or 3d space. dimension reduction techniques were already used for producing biological network layouts. for example, golorize cytoscape plugin computes the layout of a biological network using the results of go enrichment analysis. some existing methods apply multidimensional scaling to the distance matrix defined by the graph path distance. these methods have the purpose to construct more appealing network layouts. however, they usually do not use the multidimensional data attached to the network nodes. therefore, they can not be adapted for visualization of a particular dataset. on the other hand, there exist a number of convenient software allowing the construction and visualization of the structure of correlation graphs, computed from multidimensional data, e.g., biolayout express3d or arena3d. however, these representations do not use the knowledge of the structure of real biological networks since they are not inferred from the data by correlation analysis. we believe that in certain analyses, it could be insightful to construct the biological network layout based simultaneously on the network structure and the associated multidimensional data. one possible solution consists in applying data dimension reduction techniques. in order to allow cytoscape users to conveniently apply linear and non-linear dimension reduction methods accompanied by network-based data regularization, we have developed dedal, a cytoscape app for computing and mixing data-driven and structure-driven network layouts. unlike many other methods, the purpose of dedal is not to improve the visual appeal of the biological network layout, but to modify it in such a way that the trends in the associated data and exceptions from these trends would be detectable more easily. implementation dedal is a simplified cytoscape app implemented in java language. for computing linear and non-linear principal manifolds, dedal uses vdaoengine java library. for computing the eigenvectors of a symmetric laplacian matrix, the parallelized colt library has been used. internal graph implementation is re-used from binom cytoscape plugin. the source code of dedal is available at http://bioinfo-out.curie.fr/projects/dedal/. producing data-driven network layouts data-driven network layout is produced by dedal by positioning the nodes of the network according to their projection from the multidimensional data space of associated numerical vectors into a 2d space. dedal implements three algorithms for performing this dimension reduction: projection onto a plane of two selected principal components; projection onto a non-linear 2d surface approximating the multidimensional data distribution, i.e. principal manifold, computed by the method of elastic maps; and use of or preceded by network-based regularization of the data, based on computing the k first eigenvectors of the laplacian matrix of the network graph and projecting data into this subspace. dedal implements specific data pre-processing and resulting layout post-processing steps. pre-processing steps include selecting only nodes whose associated numerical vectors are sufficiently complete and optional double centering of the data matrix. post-processing of the resulting layout includes avoiding overlap between node positions by moving them in a random direction at a small distance; moving the outliers closer to the barycenter of the data distribution; and placing the nodes with missing data into the mean point of the position of their network neighbours. in future work, an effort will be made to project the data in the three dimensional space, or exploit the concept of multi-level d network representation. we would like to let the user rotate the network layout in order to better visualize the network substructures which are difficult to represent in 2d space, as it is done in biolayout 3d software. we also plan to implement in dedal more flexible dimension reduction algorithms such as multidimensional scaling which will extend the data representation possibilities, better answering to specific user’s needs. finally, more sophisticated strategies of network layout morphing will be developed, taking into account the data. we will also improve the function for avoiding extensive node overlapping. manipulating network layouts in dedal in order to allow the comparison of the resulting ddls with standard layouts produced by cytoscape and to transform one into another, dedal implements simple layout morphing and aligning methods. morphing of two network layouts is performed by a linear transformation, moving matched nodes along straight lines. dedal provides a convenient user dialog for morphing one layout into another so that the user can immediately appreciate the morphing result. the morphing operation provides poor results if one layout is systematically rotated or flipped with respect to the node positions in another one. dedal allows aligning two network layouts by rotating, mirroring, and minimizing the euclidean distance between two layouts. double-centering the data matrix the data matrix is optionally double-centered by subtracting from each matrix entry the mean value calculated over the corresponding matrix row and the mean value calculated over the matrix column, followed by adding the global mean value computed over all matrix entries. this procedure eliminates some global biases in the data such as the global differences in average fluorescence intensity of different probes in microarray data. network-based smoothing of data dedal perfoms network data smoothing, as suggested in. for a graph representing the biological network, its laplacian and all its eigenvectors are computed. these vectors define a new orthonormal basis in the multidimensional data space. to smooth the values of the data matrix, the initial multidimensional vector associated to a datapoint is projected into the subspace spanned by the first smallest k eigenvectors of the graph’s laplacian. dedal smoothing parameter is defined by pns=1−k−n−,pns∈, where nc is the number of connected components in the graph and n is the number of nodes on the graph. therefore, pns= corresponds to k=n, i.e. when no smoothing is performed and all eigenvectors are used, while pns= corresponds to k= and the first two non-degenerated eigenvectors are used to smooth the data. in the latter case, the data become effectively three-dimensional, with the first dimension corresponding to the average value of the data matrix computed over each connected component of the graph. exporting the pre-processed data the results of pre-processing the data for a given network can be exported to a file. actually, two files are created: one in a simple tab-delimited format suitable for further analyses in most of statistical software packages and another file in the “.dat” format, suitable for analyses in vidaexpert multidimensional data visualization tool. that way, network smoothing of an expression dataset can be done for further application in any machine learning algorithms. for this purpose, dedal can be also used in a command line mode. computing principal components and principal manifolds the principal components in dedal are computed using singular value decomposition by the method that allows the treatment of missing data values without pre-imputing them, as it is described in. data points, containing more than % of missing values are filtered out from the analysis. dedal computes the first principal components if there are more than data points, and k principal components if there are k+ data points, with k< after computing the principal components, dedal reports the amount of variance explained by each of the principal components. time-efficient method of elastic maps for computing principal manifolds also allows dealing with missing data without pre-imputing them. in this case, a 2d rectangular manifold is computed, and the amount of variance explained by it is reported. continuous layout morphing morphing two network layouts is performed by a simple linear transformation. a node having position in the initial layout and the position in the target layout is placed during the morphing procedure in the position x p×x22+x12), where p∈ is the morphing parameter representing the fraction of distance between the initial and target node positions along the straight line. aligning two network layouts by rotation and mirroring morphing between two network layouts might be meaningless if all nodes in one layout are systematically rotated or flipped with respect to the node positions in another layout. this situation is often the case when producing the pure data-driven layout and comparing it to the initial structure-driven layout. in this case, dedal allows minimizing the euclidean distance between two layouts defined as the sum of squared euclidean distances between all matched nodes with respect to all possible rotations and mirroring of one of the layouts. dedal provides an option to align networks before morphing them. also, a user can align several network layouts to one chosen reference network layout, using a separate “layout aligning” dialog. for example, it is usually useful to align the structure-driven layouts to the pca-based data-driven layout. using dedal in command line mode dedal can be used separately from the cytoscape environment, in the command line mode, as it is explained on the dedal website with several examples. this is especially recommended for computing data-driven layouts for large networks containing more than ten thousand nodes. command line mode allows applying all data pre-processing steps, including double-centering and network smoothing, saving the resulting network layout as a xgmml file and saving the eigenvector decomposition of the laplacian of the network graph for future use.  using tcga transcriptome data and hprd network we used the cancer genome atlas transcriptomic dataset for breast cancer and human protein reference database database as a source of protein-protein interaction network. firstly, as an example of a small subnetwork, we selected proteins involved in fanconi dna repair pathway as it is defined in atlas of cancer signaling network. for node coloring, we mapped the value of the t-test computed for the gene expression difference between the basal-like and non basal-like breast tumors. we have imported the tcga data in cytoscape and applied dedal for the transcription levels of the genes in the subnetwork. fig. using dedal for visualizing fanconi pathway in breast cancer. top row: standard organic layout, pca-based ddl, morphing two previous layouts at half-distance. bottom row from left to right: pca-based ddl computed only for basal-like tumors, pca applied to network-smoothed profile, ddl computed using elastic map algorithm for computing non-linear principal manifold. red color denotes larger positive values of the t-test computed for the difference between basal-like and non basal-like groups of samples, green color corresponds to negative values of the t-test one can see that the first principal component sorts the nodes according to the t-test, because in this case the first principal component is associated with the basal-like breast cancer subtype. the second principal component gives additional information such as the fact that the expression levels of brca and fance are differently modulated, though both are upregulated in the basal-like subtype. morphing the organic network layout with the pca-based layout moves the position of some of the genes, keeping the general pattern of pca preserved, while better reflecting the network structure. we have also applied pca-based ddl to the subset of basal-like breast tumors which showed the specific role of brca gene in this subtype confirming a known fact. also, the position of usp gene has significantly changed with respect to the pca-based ddl produced for the whole set of samples. this demonstrates the ability of dedal to produce network layouts specific for a particular cancer subtype. application of network smoothing is demonstrated in fig. bottom middle. the layout preserves the general pattern of the pca-based ddl, while better visualizing the network structure, and moving some proteins into a different position. for example, brca gene is moved to the left because it is connected to several genes overexpressed in basal-like breast cancer subtype. figure bottom right, shows the application of non-linear pca to data dimension reduction. this network layout better resolves the relations between some gene expression levels such as fancf and hes and the roles of brca and brca in fanconi dna repair pathway. visualizing rna-seq tissue expression data onto the network of tissue-specific genes in order to illustrate the added value of dedal for visualizing expression data on top of relatively large networks, we constructed a tissue-specific subnetwork from hprd global network of protein-protein interactions using the following approach. rna-seq data containing transcriptomes for healthy human tissues were obtained from. replicate measurements were averaged in order to obtain a single transcriptomic profile per tissue. in each profile, the genes were ranked according to their expression and the most significant largest connected component of the global ppi network directly connecting the top ranked genes was identified using binom plugin. after this step, the tissue-specific subnetworks that showed a significant score for the size of lcc were merged. this resulted in a network containing nodes, representing the top genes that are highly expressed in at least one tissue type, and edges representing direct ppis between them. dedal was applied to this network and the whole set of tissue transcriptomes. double-centering and network smoothing with retaining only % of smallest eigenvectors was applied at the pre-processing step, and the non-linear principal manifold was computed for dimension reduction. even without application of morphing to a structure-driven network layout, this procedure produced an insightful visualization of the network containing several clusters and connections between them. mapping transcriptomes of different tissues clearly highlights different network clusters with this layout. the configuration of the clusters reflects the proximity of them in the data space of healthy tissue transcriptomes. fig. using dedal for visualizing the network and rna-seq expression data of tissue-specific genes. rna-seq dataset for healthy human tissues was used to defined a subnetwork of hprd ppi database enriched in tissue-specific genes. network smoothing followed by computation of principal manifold was applied to produce the data-driven network layout. patterns of gene expression for two selected tissues are shown on top the constructed ddl, red color denotes higher expression, green color corresponds to lower expression. the sizes of the nodes are proportional to their connectivity degree in this network. on the left top panel application of the force directed layout is shown for comparison. on the left bottom panel results of quantitative comparison between multidimensional distance representation in dedal and force directed layout are shown. the most representative distances between the genes in the initial multidimensional space are ranked here from the largest to the smallest values in order to objectively evaluate the advantage of using dedal for data visualization, we quantified how well the distances between the genes in the multidimensional space were reproduced on the 2d plane. we computed the correlations between gene pair-wise euclidean distances in multidimensional space and in their configuration in a 2d network layout. we compared dedal with force directed layout frequently used to layout large networks. since the full distance matrix contains many dependent distance values, one has to select the most representative distances for computing these correlations. such approach was applied before to quantify the goodness of between-point distance representation after projecting them into a low-dimensional space. application of this approach in this case study showed improved pearson correlation between the distances from to, leading to increase of correlation coefficient statistical significance by orders of magnitude. the absolute value of the correlation remains moderate because projection of multidimensional data into 2d leads to significant loss of information. force directed layout produces significant correlation because in this case, the biological network was specifically constructed to match the variance in the dataset. the later underlines the importance of carefull biological network selection for data visualization purposes. visualizing genetic interactions genetic interaction between two genes reflects their synergistic or mutually alleviating functions the strength of genetic interactions is characterized by an epistatic score which quantifies deviation from a simple multiplicative model. in the global network of genetic interactions, each gene can be characterized by its epistatic profile, i.e., a vector of epistatic scores with all other genes. it is shown that the genes with similar epistatic profiles tend to have similar cellular functions. we applied dedal to create a ddl layout for a group of yeast genes involved in dna repair and replication. the genetic interactions between these genes and the epistatic profiles were used from. the definitions of dna repair pathways were taken from kegg database. figure shows the difference between application of the standard organic layout for this small network of genetic interactions and pca-based ddl. pca-based ddl, in this case, groups the genes with respect to their epistatic profiles. firstly, local hub genes rad and pol have distinct position in this layout. secondly, pca-based ddl roughly groups the genes accordingly to the dna repair pathway in which they are involved. for example, it shows that non-homologous end joining dna repair pathway is closer to homologous recombination pathway than to the mismatch repair pathway. it also underlines that some homologous recombination genes are characterized by a different pattern of genetic interactions than the “core” hr genes rad rad rad rad rad fig. using dedal for visualizing network of genetic interactions between yeast genes involved in dna repair. red and green edges denote positive and negative genetic interactions correspondingly. different node colors indicate three distinct dna repair pathways in yeast visualizing attractors of a boolean model in this example, we used the boolean model of cell fate decisions between survival, apoptosis and non-apoptotic cell death published in, to group the nodes of the influence diagram according to their co-activation patterns in the logical stable states. the table of stable states was taken from and used to compute the pca-based ddl. in this ddl, nodes in close positions have similar pattern of activation in stable states. we used morphing pca-based ddl and the initial layout of the model to visualize several stable states corresponding to different cell fates. in this layout co-activated nodes tend to form compact groups. therefore, dedal can be used to design layouts of mathematical models of biological networks, using the solutions of the model. applying dedal in this analysis highlighted the functional importance of different interactions in the model and identified dynamical modules composed of variables participating in the same fate decision. fig. using dedal for visualizing results of a boolean model simulation. table of computed stable states is used to group the nodes with similar states in similar conditions. in the influence diagram green edges signify inhibitory and red edges - activating relations. the model network layout is produced by applying morphing of a data-driven layout with the initial layout suggested by modeler fig. using dedal for visualizing results of a boolean model simulation. visualization of three stable states of the model, with green and red denoting inactive and active states of the node correspondingly scalability of dedal for large networks dedal scales very well with respect to computing data projections into 2d space. even for the networks containing ten thousand nodes and more, dedal computes linear and non-linear data projections for few hundreds of samples in less than few tens of seconds on an ordinary laptop. fig. scalability of dedal for large networks. the figure shows the number of seconds needed for dedal to compute network smoothing, first ten principal components and the principal manifold for a set of ovarian cancer transcriptomes and a series of networks with increasing number of nodes. network smoothing scaling is separately shown for the case of de-novo computation of the eigenvector decomposition of the network laplacian and for the case of using the pre-computed eigenvector decomposition. the benchmarking was done in the command line mode of dedal however, the network smoothing data pre-processing step implemented in dedal requires eigenvector decomposition of the laplacian matrix of the network graph which scales in time as the third power of the number of nodes. while this computation remains relatively fast for relatively large networks, it drastically slows down when the size of the network grows above several thousands of nodes. in our benchmark example, eigenvector decomposition of the laplacian of the whole hprd ppi database required hours on a regular laptop, which makes application of network smoothing data pre-processing not convenient for large networks. however, eigenvector decomposition of the laplacian for a large graph can be done once and saved on the disk for future reuse. for example, on the dedal website we provide the pre-computed eigenvector decomposition for the laplacian of the graph representing the whole hprd database, and other decompositions for large ppi networks will be provided in the future. using pre-computed eigenvector decomposition allows applying data network smoothing with large networks containing tens of thousands nodes in a reasonable time. use of dedal with large networks containing tens of thousands of nodes is recommended in command line mode. the computed network layout can be imported into cytoscape environment and used for mapping high-throughput data on top of them.  dedal cytoscape plugin combines the classical and advanced data dimension reduction methods with the algorithms of network layouting inside cytoscape environment. this ability can be used in a number of ways and for many applications, some of them are suggested in this paper. the application of dedal is not limited to producing data-driven network layouts. more generally, dedal allows the application of dimension reduction of the multivariate data associated with the nodes of any cytoscape network, optionally using the structure of the network, and exports the results for further analyses by any suitable algorithms. availability and requirements project name: dedal: data-driven network layoutingproject home page:http://bioinfo-out.curie.fr/projects/dedal/operating system: platform independentprogramming language: javaother requirements: java or higher, cytoscape or higherlicense: gnu lgplany restrictions to use by non-academics: free for any non-commercial use competing interests the authors declare that they have no competing interests. authors’ contributions az and uc developed the algorithm. uc and az wrote the application code. uc, lc and az provided the examples of using dedal. az and uc wrote the manuscript. az, lc, eb have read and revised the manuscript. all authors read and approved the final manuscript. 
a network layout based simultaneously on the network structure and the associated multidimensional data might be advantageous for data visualization and analysis in some cases. visualization and analysis of molecular profiling data together with biological networks are able to provide new mechanistic insights into biological functions. dedal is a convenient tool for applying data dimensionality reduction methods and for designing insightful data displays based on data-driven layouts of biological networks, built within cytoscape environment. dedal is a cytoscape app, which uses linear and non-linear algorithms of dimension reduction to produce data-driven network layouts based on multidimensional data. currently, it is possible to visualize high-throughput data on top of pre-defined network layouts, but they are not always adapted to a given data analysis task. we developed a cytoscape app, which allows constructing biological network layouts based on the data from molecular profiles imported as values of node attributes. dedal implements several data pre-processing and layout post-processing steps such as continuous morphing between two arbitrary network layouts and aligning one network layout with respect to another one by rotating and mirroring. the combination of all these functionalities facilitates the creation of insightful network layouts representing both structural network features and correlation patterns in multivariate data.
 visualization and analysis of molecular profiling data together with biological networks are able to provide new mechanistic insights into biological functions. currently, it is possible to visualize high-throughput data on top of pre-defined network layouts, but they are not always adapted to a given data analysis task. a network layout based simultaneously on the network structure and the associated multidimensional data might be advantageous for data visualization and analysis in some cases.  we developed a cytoscape app, which allows constructing biological network layouts based on the data from molecular profiles imported as values of node attributes. dedal is a cytoscape app, which uses linear and non-linear algorithms of dimension reduction to produce data-driven network layouts based on multidimensional data. dedal implements several data pre-processing and layout post-processing steps such as continuous morphing between two arbitrary network layouts and aligning one network layout with respect to another one by rotating and mirroring. the combination of all these functionalities facilitates the creation of insightful network layouts representing both structural network features and correlation patterns in multivariate data. we demonstrate the added value of applying dedal in several practical applications, including an example of a large protein-protein interaction network.  dedal is a convenient tool for applying data dimensionality reduction methods and for designing insightful data displays based on data-driven layouts of biological networks, built within cytoscape environment. dedal is freely available for downloading at http://bioinfo-out.curie.fr/projects/dedal/. issue-copyright-statement© the author 2015 