Visual exploration across biomedical databases

Though biomedical research often draws on knowledge from a wide variety of fields, few visualization methods for biomedical data incorporate meaningful cross-database exploration. A new approach is offered for visualizing and exploring a query-based subset of multiple heterogeneous biomedical databases. Databases are modeled as an entity-relation graph containing nodes (database records) and links (relationships between records). Users specify a keyword search string to retrieve an initial set of nodes, and then explore intra- and interdatabase links. Results are visualized with user-defined semantic substrates to take advantage of the rich set of attributes usually present in biomedical data. Comments from domain experts indicate that this visualization method is potentially advantageous for biomedical knowledge exploration.     

Using Random Walks to Generate Associations between Objects

Measuring similarities between objects based on their attributes has been an important problem in many disciplines. Object-attribute associations can be depicted as links on a bipartite graph. A similarity measure can be thought as a unipartite projection of this bipartite graph. The most widely used bipartite projection techniques make assumptions that are not often fulfilled in real life systems, or have the focus on the bipartite connections more than on the unipartite connections. Here, we define a new similarity measure that utilizes a practical procedure to extract unipartite graphs without making a priori assumptions about underlying distributions. Our similarity measure captures the relatedness between two objects via the likelihood of a random walker passing through these nodes sequentially on the bipartite graph. An important aspect of the method is that it is robust to heterogeneous bipartite structures and it controls for the transitivity similarity, avoiding the creation of unrealistic homogeneous degree distributions in the resulting unipartite graphs. We test this method using real world examples and compare the obtained results with alternative similarity measures, by validating the actual and orthogonal relations between the entities.     

土壤动物知识图谱构建理论、方法与技术——以浙江天目山土壤螨类为例

土壤动物学面临以全新知识体系为科学研究框架的变革时期,其核心内容是以数据驱动为主要特征的人工智能技术方法。目前广泛应用的基于数据库的数据处理分析方法,面临着数据多源异构、快速增长和处理能力不足之间的矛盾。基于快速发展的大数据科学和人工智能技术的数据挖掘方法在解决前述矛盾中有突出优势,但需要依赖一个强大的领域知识库,然而土壤动物领域知识图谱的研究十分匮乏。土壤动物知识图谱是一个具有有向图结构的知识库,其中图的节点代表与土壤动物相关的实体或概念,图的边代表实体或概念之间的各种语义关系。提出了土壤动物知识图谱的定义、内涵、理论模型和构建方法,以浙江天目山土壤螨类多样性为例,分析了构建山地土壤动物知识图谱的技术方法;以土壤动物多样性研究关注的物种分布、物种共存、环境条件对物种的影响作用为例,探讨了基于山地土壤动物知识图谱可以解决的相关科学问题。研究表明,土壤动物知识图谱在解决生物多样性重要科学问题方面具有独特的潜力和优势,有力推动了土壤动物学、信息科学和数据科学交叉的土壤动物信息学的发展。     

Clust&See: A Cytoscape plugin for the identification,visualization and manipulation of network clusters

Background and scope

Large networks, such as protein interaction networks, are extremely difficult to analyze as a whole. We developed Clust&See, a Cytoscape plugin dedicated to the identification, visualization and analysis of clusters extracted from such networks.

Implementation and performance

Clust&See provides the ability to apply three different, recently developed graph clustering algorithms to networks and to visualize: (i) the obtained partition as a quotient graph in which nodes correspond to clusters and (ii) the obtained clusters as their corresponding subnetworks. Importantly, tools for investigating the relationships between clusters and vertices as well as their organization within the whole graph are supplied.     

Structural distance and evolutionary relationship of networks

Exploring common features and universal qualities shared by a particular class of networks in biological and other domains is one of the important aspects of evolutionary study. In an evolving system, evolutionary mechanism can cause functional changes that forces the system to adapt to new configurations of interaction pattern between the components of that system (e.g. gene duplication and mutation play a vital role for changing the connectivity structure in many biological networks. The evolutionary relation between two systems can be retraced by their structural differences). The eigenvalues of the normalized graph Laplacian not only capture the global properties of a network, but also local structures that are produced by graph evolutions (like motif duplication or joining). The spectrum of this operator carries many qualitative aspects of a graph. Given two networks of different sizes, we propose a method to quantify the topological distance between them based on the contrasting spectrum of normalized graph Laplacian. We find that network architectures are more similar within the same class compared to between classes. We also show that the evolutionary relationships can be retraced by the structural differences using our method. We analyze 43 metabolic networks from different species and mark the prominent separation of three groups: Bacteria, Archaea and Eukarya. This phenomenon is well captured in our findings that support the other cladistic results based on gene content and ribosomal RNA sequences. Our measure to quantify the structural distance between two networks is useful to elucidate evolutionary relationships.     

Frequency Response and Gap Tuning for Nonlinear Electrical Oscillator Networks

We study nonlinear electrical oscillator networks, the smallest example of which consists of a voltage-dependent capacitor, an inductor, and a resistor driven by a pure tone source. By allowing the network topology to be that of any connected graph, such circuits generalize spatially discrete nonlinear transmission lines/lattices that have proven useful in high-frequency analog devices. For such networks, we develop two algorithms to compute the steady-state response when a subset of nodes are driven at the same fixed frequency. The algorithms we devise are orders of magnitude more accurate and efficient than stepping towards the steady-state using a standard numerical integrator. We seek to enhance a given network''s nonlinear behavior by altering the eigenvalues of the graph Laplacian, i.e., the resonances of the linearized system. We develop a Newton-type method that solves for the network inductances such that the graph Laplacian achieves a desired set of eigenvalues; this method enables one to move the eigenvalues while keeping the network topology fixed. Running numerical experiments using three different random graph models, we show that shrinking the gap between the graph Laplacian''s first two eigenvalues dramatically improves a network''s ability to (i) transfer energy to higher harmonics, and (ii) generate large-amplitude signals. Our results shed light on the relationship between a network''s structure, encoded by the graph Laplacian, and its function, defined in this case by the presence of strongly nonlinear effects in the frequency response.     

Mathematical modeling of the malignancy of cancer using graph evolution

We report a novel computational method based on graph evolution process to model the malignancy of brain cancer called glioma. In this work, we analyze the phases that a graph passes through during its evolution and demonstrate strong relation between the malignancy of cancer and the phase of its graph. From the photomicrographs of tissues, which are diagnosed as normal, low-grade cancerous and high-grade cancerous, we construct cell-graphs based on the locations of cells; we probabilistically generate an edge between every pair of cells depending on the Euclidean distance between them. For a cell-graph, we extract connectivity information including the properties of its connected components in order to analyze the phase of the cell-graph. Working with brain tissue samples surgically removed from 12 patients, we demonstrate that cell-graphs generated for different tissue types evolve differently and that they exhibit different phase properties, which distinguish a tissue type from another.     

A replicas placement approach of component services for service-based cloud application

Placement of component service replicas for service-based application (SBA) in cloud environments has become increasingly important. A SBA is usually communication topology-aware, and component service replicas possess stronger data dependency than data replicas; therefore, there are huge amounts of communication between the computer nodes that are used to place component service replicas. Because the conventional methods do not consider the communication topology of component services and the relations between computer nodes, they are not appropriate for placing component service replicas. In this paper, we propose a topological matching-based component service replicas placement method that takes into account not only the topology of SBAs but also the communication performance between different computing nodes. This method first discovers the communication topology of a SBA via multi-scale graph clustering then acquires the topology of computer nodes through spectral clustering. It then places the component service replicas by matching the above two topological structures. Comprehensive experiments are conducted by comparing the performance of our method with those of other methods based on CloudSim simulation software. The results show the effectiveness of our method for improving the performance of SBAs.     

Graph-Theoretical Analysis of Cleavage Pattern: Graph Developmental System and Its Application to Cleavage Pattern of Ascidian Egg

The skeletal structure of the embryo is represented by the graph. In the graph, the cells and the connectivities between the cells are reduced to the nodes and edges, respectively. Along cleavage history, the series of graphs is obtained. In this paper I propose a new graph developmental system(GDS) which develops the series of graphs. And I represent and analyze the cleavage pattern of the ascidian egg by GDS. In order to represent it by GDS, at first, the connectivities between the cells are labeled according to the developments of the connectivities at the next time step, and next the cells are labeled. But there are two ways of labeling the cells, then two types of GDS are defined: (1) to label according to the pattern of the connectivities of their descendant cells after two time steps (G-GDS), (2) to label according to the cell fates (C-GDS). The C-GDS of the ascidian egg produces 16 cleavage patterns at 64-cell stage non-deterministically. If some labels are distinguished at 16-cell stage, the C-GDS becomes deterministic at 64-cell stage.
GDS will be useful to simulate morphogenesis by the computer graphics.     

The large graph limit of a stochastic epidemic model on a dynamic multilayer network

We consider a Markovian SIR-type (Susceptible → Infected → Recovered) stochastic epidemic process with multiple modes of transmission on a contact network. The network is given by a random graph following a multilayer configuration model where edges in different layers correspond to potentially infectious contacts of different types. We assume that the graph structure evolves in response to the epidemic via activation or deactivation of edges of infectious nodes. We derive a large graph limit theorem that gives a system of ordinary differential equations (ODEs) describing the evolution of quantities of interest, such as the proportions of infected and susceptible vertices, as the number of nodes tends to infinity. Analysis of the limiting system elucidates how the coupling of edge activation and deactivation to infection status affects disease dynamics, as illustrated by a two-layer network example with edge types corresponding to community and healthcare contacts. Our theorem extends some earlier results describing the deterministic limit of stochastic SIR processes on static, single-layer configuration model graphs. We also describe precisely the conditions for equivalence between our limiting ODEs and the systems obtained via pair approximation, which are widely used in the epidemiological and ecological literature to approximate disease dynamics on networks. The flexible modeling framework and asymptotic results have potential application to many disease settings including Ebola dynamics in West Africa, which was the original motivation for this study.     

On some metric properties of the systems of compartments

Rules for the enumeration of the strong components of a graph and for the calculation of its variable adjacency matrix are presented. A new method is given to calculate the transfer function of a graphy by analyzing the strong components of the graph, the elementary paths between two nodes, and the linear subgraphs.     

基于政策工具视角的中国生物产业政策差异性分析

产业发展离不开产业政策的制定与发布,产业政策对于产业具有导向性与支持性,其制定主体主要包括中央政府和地方政府。以生物产业为例,采用计量分析的方法,搜集并整理了中央政府以及湖北、深圳、重庆、上海、北京五个地方政府颁布的生物产业政策,对其外部属性特征进行差异性分析,同时对多份国家层面的生物产业结构性政策运用内容分析的方法,进行政策工具分类分析,并构建了“政策工具-生物产业发展阶段”二维政策工具分析框架,探讨不同产业发展阶段之间政策工具使用的差异性。研究发现,中央政府与地方政府生物产业政策密集发布年份存在差异,且与生物产业发展关键节点有关联;国家层面生物产业政策不同类型政策工具使用频率差距较大,以环境型政策工具为主,较少使用需求型政策工具。针对研究结果,从我国生物产业发展情况及区域间差异的角度提出了相关政策建议。     

Planning and Sequencing Heuristics for Feature-Based Control of Holonic Machining Equipment

The intelligent manufacturing system program was proposed by Japan in 1989. Five participating regions—Australia, Canada, the European Community, Japan, and the United States—currently are involved in developing 21st century manufacturing technology through an investment of US $1.2 billion over 10 years. Korea joined the program and will start work on one of the six ongoing projects, holonic manufacturing systems (HMSs). The objective of the paper is to develop the control architecture of the holonic machining unit (HMU) for construction of the HMSs and to present some planning and sequencing heuristics for feature-based control of the HMU. Further, the paper provides the HMU's functionality using the IDEF0 function modeling method. The basic operation of the decision maker among the HMU's functions is to determine an efficient feature sequence in real time from the nonlinear feature graph used to represent a process plan. To this end, two methodologies are applied sequentially to managing a nonlinear process plan: removal of the OR nodes and then grouping and sequencing the features in the feature graph. Markov chain theory is used to compute the path preference indicator for removing the OR nodes, that is, for selecting the best path among those surrounded by OR nodes. The resulting graph is the AND graph, from which the feature type nodes are formed into sequenced groups. The CNC codes associated with the features in each group are combined and downloaded to the CNC machine. The development of the methodologies can help manufacturers efficiently cope with unexpected failures encountered during computer-automated machining.     

Influence of prior knowledge in constraint-based learning of gene regulatory networks

Constraint-based structure learning algorithms generally perform well on sparse graphs. Although sparsity is not uncommon, there are some domains where the underlying graph can have some dense regions; one of these domains is gene regulatory networks, which is the main motivation to undertake the study described in this paper. We propose a new constraint-based algorithm that can both increase the quality of output and decrease the computational requirements for learning the structure of gene regulatory networks. The algorithm is based on and extends the PC algorithm. Two different types of information are derived from the prior knowledge; one is the probability of existence of edges, and the other is the nodes that seem to be dependent on a large number of nodes compared to other nodes in the graph. Also a new method based on Gene Ontology for gene regulatory network validation is proposed. We demonstrate the applicability and effectiveness of the proposed algorithms on both synthetic and real data sets.     

Compartmental systems and generating functions

Compartmental systems can be represented by direct graphs in which each node corresponds to a generating function and each arm to a transfer generating function. A homomorphism is established between a compartmental system and this representation, in analogy with that obtained through the use of the Laplace transformation. From the values obtained experimentally in a given compartment, through the solution of a difference equation, the generating function for the corresponding node can be calculated and the graph of the system can be built up within the degrees of freedom of the model. From the graph it is possible to calculate the transfer generating function between any two connected nodes, the mean permanence time in a given node, the mean transit time between two nodes, and their precursor-successor order.     

On some metric properties of the systems of compartments

Rules for the enumeration of the strong components of a graph and for the calculation of its variable adjacency matrix are presented. A new method is given to calculate the transfer function of a graphy by analyzing the strong components of the graph, the elementary paths between two nodes, and the linear subgraphs. This work was supported in part by the United States Atomic Energy Commission and the National Aeronautics and Space Administration.     

Using iterative ridge regression to explore associations between conditioned variables

We address a specific case of joint probability mapping, where the information presented is the probabilistic associations of random variables under a certain condition variable (conditioned associations). Bayesian and dependency networks graphically map the joint probabilities of random variables, though both networks may identify associations that are independent of the condition (background associations). Since the background associations have the same topological features as conditioned associations, it is difficult to discriminate between conditioned and non-conditioned associations, which results in a major increase in the search space. We introduce a modification of the dependency network method, which produces a directed graph, containing only condition-related associations. The graph nodes represent the random variables and the graph edges represent the associations that arise under the condition variable. This method is based on ridge-regression, where one can utilize a numerically robust and computationally efficient algorithm implementation. We illustrate the method's efficiency in the context of a medically relevant process, the emergence of drug-resistant variants of human immunodeficiency virus (HIV) in drug-treated, HIV-infected people. Our mapping was used to discover associations between variants that are conditioned by the initiation of a particular drug treatment regimen. We have demonstrated that our method can recover known associations of such treatment with selected resistance mutations as well as documented associations between different mutations. Moreover, our method revealed novel associations that are statistically significant and biologically plausible.     

Subvoxel Accurate Graph Search Using Non-Euclidean Graph Space

Graph search is attractive for the quantitative analysis of volumetric medical images, and especially for layered tissues, because it allows globally optimal solutions in low-order polynomial time. However, because nodes of graphs typically encode evenly distributed voxels of the volume with arcs connecting orthogonally sampled voxels in Euclidean space, segmentation cannot achieve greater precision than a single unit, i.e. the distance between two adjoining nodes, and partial volume effects are ignored. We generalize the graph to non-Euclidean space by allowing non-equidistant spacing between nodes, so that subvoxel accurate segmentation is achievable. Because the number of nodes and edges in the graph remains the same, running time and memory use are similar, while all the advantages of graph search, including global optimality and computational efficiency, are retained. A deformation field calculated from the volume data adaptively changes regional node density so that node density varies with the inverse of the expected cost. We validated our approach using optical coherence tomography (OCT) images of the retina and 3-D MR of the arterial wall, and achieved statistically significant increased accuracy. Our approach allows improved accuracy in volume data acquired with the same hardware, and also, preserved accuracy with lower resolution, more cost-effective, image acquisition equipment. The method is not limited to any specific imaging modality and readily extensible to higher dimensions.     

人代谢网络巨强连通体的复杂网络分析

采用复杂网络理论分析了人代谢网络的巨强连通体。通过对高质量人代谢网络数据的整理,获取了该网络巨强连通体中的所有代谢反应。用代谢物图表示这些反应形成了一个网络,它包含了256个节点和648条连线。选用模拟退火算法对该网络进行社团结构分析,发现得到的模块具备重要的生物学功能。通过多种不同的中心化方法,分析了该网络的关键节点,并讨论了它们的生物学和理疗意义。