Recent developments in quantitative graph theory: information inequalities for networks

In this article, we tackle a challenging problem in quantitative graph theory. We establish relations between graph entropy measures representing the structural information content of networks. In particular, we prove formal relations between quantitative network measures based on Shannon's entropy to study the relatedness of those measures. In order to establish such information inequalities for graphs, we focus on graph entropy measures based on information functionals. To prove such relations, we use known graph classes whose instances have been proven useful in various scientific areas. Our results extend the foregoing work on information inequalities for graphs.     

科技论文中线条图的优化编辑

线条图已在科技论文中得到广泛应用,良好的线条图可以将复杂的数据资料直观、简洁、明了地展现在读者面前,更有利于读者阅读和获取信息,更有助于作者思想的表达和科技信息的传播.以科技论文作者使用线条图中存在的问题为例,着重介绍了科技论文中线条图的几种优化方法.作者根据多年的编辑加工经验,通过对图类型选择、横纵坐标和图例的调整、...     

Colored de Bruijn graphs and the genome halving problem

Breakpoint graph analysis is a key algorithmic technique in studies of genome rearrangements. However, breakpoint graphs are defined only for genomes without duplicated genes, thus limiting their applications in rearrangement analysis. We discuss a connection between the breakpoint graphs and de Bruijn graphs that leads to a generalization of the notion of breakpoint graph for genomes with duplicated genes. We further use the generalized breakpoint graphs to study the genome halving problem (first introduced and solved by Nadia El-Mabrouk and David Sankoff). The El-Mabrouk-Sankoff algorithm is rather complex, and, in this paper, we present an alternative approach that is based on generalized breakpoint graphs. The generalized breakpoint graphs make the El-Mabrouk-Sankoff result more transparent and promise to be useful in future studies of genome rearrangements     

Protein evolution within a structural space

Understanding of the evolutionary origins of protein structures represents a key component of the understanding of molecular evolution as a whole. Here we seek to elucidate how the features of an underlying protein structural “space” might impact protein structural evolution. We approach this question using lattice polymers as a completely characterized model of this space. We develop a measure of structural comparison of lattice structures that is analogous to the one used to understand structural similarities between real proteins. We use this measure of structural relatedness to create a graph of lattice structures and compare this graph (in which nodes are lattice structures and edges are defined using structural similarity) to the graph obtained for real protein structures. We find that the graph obtained from all compact lattice structures exhibits a distribution of structural neighbors per node consistent with a random graph. We also find that subgraphs of 3500 nodes chosen either at random or according to physical constraints also represent random graphs. We develop a divergent evolution model based on the lattice space which produces graphs that, within certain parameter regimes, recapitulate the scale-free behavior observed in similar graphs of real protein structures.     

SING: Subgraph search In Non-homogeneous Graphs

Background  

Finding the subgraphs of a graph database that are isomorphic to a given query graph has practical applications in several fields, from cheminformatics to image understanding. Since subgraph isomorphism is a computationally hard problem, indexing techniques have been intensively exploited to speed up the process. Such systems filter out those graphs which cannot contain the query, and apply a subgraph isomorphism algorithm to each residual candidate graph. The applicability of such systems is limited to databases of small graphs, because their filtering power degrades on large graphs.     

Observations on graphing paleozoological data: Suggestions for better graphs

Paleozoologists have long used graphs of diverse styles to describe, analyze, and summarize their data. Some of these graphs provide excellent visual representations of complex data and are readily deciphered. Other graph styles require close study to be interpreted. Ease of visual decoding of information contained in a graph – graph perception – varies from graph style to graph style. Historical instances of graphing paleozoological data indicate some difficult to decipher graph styles have been used for at least a century. Graphs with three-dimensions, moiré effects, superimposed lines, or segmented bars, or which demand simultaneous decipherment of position and magnitude, are ill-advised. Temporal trends in data are best graphed following the principle of superposition such that data from old material is graphed at the bottom and data from younger material is graphed at the top of the diagram.     

Hamming-shifting graph of genomic short reads: Efficient construction and its application for compression

Graphs such as de Bruijn graphs and OLC (overlap-layout-consensus) graphs have been widely adopted for the de novo assembly of genomic short reads. This work studies another important problem in the field: how graphs can be used for high-performance compression of the large-scale sequencing data. We present a novel graph definition named Hamming-Shifting graph to address this problem. The definition originates from the technological characteristics of next-generation sequencing machines, aiming to link all pairs of distinct reads that have a small Hamming distance or a small shifting offset or both. We compute multiple lexicographically minimal k-mers to index the reads for an efficient search of the weight-lightest edges, and we prove a very high probability of successfully detecting these edges. The resulted graph creates a full mutual reference of the reads to cascade a code-minimized transfer of every child-read for an optimal compression. We conducted compression experiments on the minimum spanning forest of this extremely sparse graph, and achieved a 10 − 30% more file size reduction compared to the best compression results using existing algorithms. As future work, the separation and connectivity degrees of these giant graphs can be used as economical measurements or protocols for quick quality assessment of wet-lab machines, for sufficiency control of genomic library preparation, and for accurate de novo genome assembly.     

Bipartite graphs as models of population structures in evolutionary multiplayer games

By combining evolutionary game theory and graph theory, "games on graphs" study the evolutionary dynamics of frequency-dependent selection in population structures modeled as geographical or social networks. Networks are usually represented by means of unipartite graphs, and social interactions by two-person games such as the famous prisoner's dilemma. Unipartite graphs have also been used for modeling interactions going beyond pairwise interactions. In this paper, we argue that bipartite graphs are a better alternative to unipartite graphs for describing population structures in evolutionary multiplayer games. To illustrate this point, we make use of bipartite graphs to investigate, by means of computer simulations, the evolution of cooperation under the conventional and the distributed N-person prisoner's dilemma. We show that several implicit assumptions arising from the standard approach based on unipartite graphs (such as the definition of replacement neighborhoods, the intertwining of individual and group diversity, and the large overlap of interaction neighborhoods) can have a large impact on the resulting evolutionary dynamics. Our work provides a clear example of the importance of construction procedures in games on graphs, of the suitability of bigraphs and hypergraphs for computational modeling, and of the importance of concepts from social network analysis such as centrality, centralization and bipartite clustering for the understanding of dynamical processes occurring on networked population structures.     

Evolutionary graph theory: breaking the symmetry between interaction and replacement

We study evolutionary dynamics in a population whose structure is given by two graphs: the interaction graph determines who plays with whom in an evolutionary game; the replacement graph specifies the geometry of evolutionary competition and updating. First, we calculate the fixation probabilities of frequency dependent selection between two strategies or phenotypes. We consider three different update mechanisms: birth-death, death-birth and imitation. Then, as a particular example, we explore the evolution of cooperation. Suppose the interaction graph is a regular graph of degree h, the replacement graph is a regular graph of degree g and the overlap between the two graphs is a regular graph of degree l. We show that cooperation is favored by natural selection if b/c>hg/l. Here, b and c denote the benefit and cost of the altruistic act. This result holds for death-birth updating, weak-selection and large population size. Note that the optimum population structure for cooperators is given by maximum overlap between the interaction and the replacement graph (g=h=l), which means that the two graphs are identical. We also prove that a modified replicator equation can describe how the expected values of the frequencies of an arbitrary number of strategies change on replacement and interaction graphs: the two graphs induce a transformation of the payoff matrix.     

Medusa: a simple tool for interaction graph analysis

SUMMARY: Medusa is a Java application for visualizing and manipulating graphs of interaction, such as data from the STRING database. It features an intuitive user interface developed with the help of biologists. Medusa is optimized for accessing protein interaction data from STRING, but can be used for any type of graph from any scientific field.     

Graphical integrity issues in open access publications: Detection and patterns of proportional ink violations

Academic graphs are essential for communicating complex scientific ideas and results. To ensure that these graphs truthfully reflect underlying data and relationships, visualization researchers have proposed several principles to guide the graph creation process. However, the extent of violations of these principles in academic publications is unknown. In this work, we develop a deep learning-based method to accurately measure violations of the proportional ink principle (AUC = 0.917), which states that the size of shaded areas in graphs should be consistent with their corresponding quantities. We apply our method to analyze a large sample of bar charts contained in 300K figures from open access publications. Our results estimate that 5% of bar charts contain proportional ink violations. Further analysis reveals that these graphical integrity issues are significantly more prevalent in some research fields, such as psychology and computer science, and some regions of the globe. Additionally, we find no temporal and seniority trends in violations. Finally, apart from openly releasing our large annotated dataset and method, we discuss how computational research integrity could be part of peer-review and the publication processes.     

Spatial graphs as templates for habitat networks in boreal landscapes

Network topology serves as a useful model for biological systems at various scales. Contrary to many biological systems, spatial reference is crucial for habitat networks. Boreal forest landscapes provide a wide gradient of spatial patterns and, thus, unique network structures. Assuming forest-dwelling organisms in general aim to minimize travel distances during foraging, dispersal, etc., linear links across the landscape matrix constitute expected movement routes among forested areas in boreal landscapes. We quantified the number and length of links in a set of 57 boreal forest landscapes for four hierarchically nested graphs in order to compare the incremental changes in characteristics of resulting graph measures. The forest cover graphs consisted of the same set of forest patches, and hierarchical link types extracted from real landscapes: nearest neighbour graph (NN), minimum spanning tree (MST), Gabriel graph (GG) and minimum planar graph (MPG). Most of the links in graphs were NN and GG links. Commonly links were 100–200?m in length, but link lengths particularly in the GG and MPG shorten when the proportion of forest in landscapes increased. Most nodes had 3–5 links each, but the number of links per node depended on node size and the proportion of forest cover. GG and MPG graphs retain the topology of the underlying node layout. Changes in node pattern alter the NN and MST graphs more than GG and MPG. Variation in regional network topologies is likely to affect connectivity patterns in a landscape and, thus, many ecological processes that occur at a local scale. An appropriate network analysis enables the discovery and comparison of distinctive network patterns. Understanding network topologies provide practical tools for land use planning and biodiversity management of broader areas that target functional habitat networks.     

Solving Hard Computational Problems Efficiently: Asymptotic Parametric Complexity 3-Coloring Algorithm

Many practical problems in almost all scientific and technological disciplines have been classified as computationally hard (NP-hard or even NP-complete). In life sciences, combinatorial optimization problems frequently arise in molecular biology, e.g., genome sequencing; global alignment of multiple genomes; identifying siblings or discovery of dysregulated pathways. In almost all of these problems, there is the need for proving a hypothesis about certain property of an object that can be present if and only if it adopts some particular admissible structure (an NP-certificate) or be absent (no admissible structure), however, none of the standard approaches can discard the hypothesis when no solution can be found, since none can provide a proof that there is no admissible structure. This article presents an algorithm that introduces a novel type of solution method to “efficiently” solve the graph 3-coloring problem; an NP-complete problem. The proposed method provides certificates (proofs) in both cases: present or absent, so it is possible to accept or reject the hypothesis on the basis of a rigorous proof. It provides exact solutions and is polynomial-time (i.e., efficient) however parametric. The only requirement is sufficient computational power, which is controlled by the parameter . Nevertheless, here it is proved that the probability of requiring a value of to obtain a solution for a random graph decreases exponentially: , making tractable almost all problem instances. Thorough experimental analyses were performed. The algorithm was tested on random graphs, planar graphs and 4-regular planar graphs. The obtained experimental results are in accordance with the theoretical expected results.     

Tellegen's theorem for bond graphs its relevance to chemical networks

Amongst the available graph theories the one making use of “bond graphs” has been considered the most suitable in network thermodynamics for representing a wide range of physico-chemical processes in the form of networks.In this article a complete representation of chemical reactions, both far from- and near-equilibrium, by bond graphs, is proposed. In addition, a new proof of the Tellegen theorem is given, derived directly from the properties of bond graphs. A new insight into the general meaning of Tellegen's theorem in variable networks and its relevance to biological networks is thus provided. The structure of the network being represented by new elements — i.e. the junctions — in bond graphs, time variations of these elements have the meaning of changes in the structure itself, to that the Tellegen theorem appears as an invariance relation in networks where the structure is allowed to change.     

Using Correlation Proximity Graphs to Study Phenotypic Integration

Characterizing and comparing the covariance or correlation structure of phenotypic traits lies at the heart of studies concerned with multivariate evolution. I describe an approach that represents the geometric structure of a correlation matrix as a type of proximity graph called a Correlation Proximity graph. Correlation Proximity graphs provide a compact representation of the geometric relationships inherent in correlation matrices, and these graphs have simple and intuitive properties. I demonstrate how this framework can be used to study patterns of phenotypic integration by employing this approach to compare phenotypic and additive genetic correlation matrices within and between species. I also outline a graph-based method for testing whether an inferred correlation proximity graph is one of a number of possible models that are consistent with a “soft” biological hypothesis.     

广东森林群落排序分析

本文应用极点排序和位置向量排序的方法对广东13个森林群落进行排序分析,并分别用极点排序图和位置向量排序的二维图和三维图表示排序的结果。同时对排序图的生态学意义及排序方法的优缺点进行讨论。结果表明,三维位置向量排序图能较好地把性质相近的群落类型聚在一起,可作为植被分类的辅助方法;积点排序图从一定程度上反映了植被的连续变化;极点排序与位置向量排序虽然取得一定结果,但由于同属线性排序,损失的信息量较多,寻求非线性排序方法是研究的方向。     

A random graph model of density thresholds in swarming cells

Swarming behaviour is a type of bacterial motility that has been found to be dependent on reaching a local density threshold of cells. With this in mind, the process through which cell‐to‐cell interactions develop and how an assembly of cells reaches collective motility becomes increasingly important to understand. Additionally, populations of cells and organisms have been modelled through graphs to draw insightful conclusions about population dynamics on a spatial level. In the present study, we make use of analogous random graph structures to model the formation of large chain subgraphs, representing interactions between multiple cells, as a random graph Markov process. Using numerical simulations and analytical results on how quickly paths of certain lengths are reached in a random graph process, metrics for intercellular interaction dynamics at the swarm layer that may be experimentally evaluated are proposed.     

Graph theoretical methods for comparing phytosociological structures

This paper describes some methods that can be used to compare the phytosociological structure of plant communities using some graph theoretic properties of the directed graphs that represent them. In such a graph, the species are represented by points and the association of species A with species B is represented by a directed line segment going from B to A. Two communities can be compared using simple indices to measure the similarity of their species-lists (point similarity) and of the species associations in them (line similarity). A more sophisticated and informative measure of line similarity is the probability that, given the number of points shared by two graphs, they have at least as many lines in common as they are observed to have. A formula for calculating that probability is given here. The graphs of community structure can also be compared with respect to the homogeneity of the distribution of the lines among the points, a property related to the number of species that are important in determining the composition of the community. These techniques are illustrated using the graphs of the phytosociological structure of intertidal seaweed communities on the southeast coast of Nova Scotia.Nomenclature follows: South and Cardinal (1970)     

Algorithmic computation of knot polynomials of secondary structure elements of proteins.

The classification of protein structures is an important and still outstanding problem. The purpose of this paper is threefold. First, we utilize a relation between the Tutte and homfly polynomial to show that the Alexander-Conway polynomial can be algorithmically computed for a given planar graph. Second, as special cases of planar graphs, we use polymer graphs of protein structures. More precisely, we use three building blocks of the three-dimensional protein structure--alpha-helix, antiparallel beta-sheet, and parallel beta-sheet--and calculate, for their corresponding polymer graphs, the Tutte polynomials analytically by providing recurrence equations for all three secondary structure elements. Third, we present numerical results comparing the results from our analytical calculations with the numerical results of our algorithm-not only to test consistency, but also to demonstrate that all assigned polynomials are unique labels of the secondary structure elements. This paves the way for an automatic classification of protein structures.