Search

Phylogenetic networks generalize phylogenetic trees by allowing the modelization of events of reticulate evolution. Among the different kinds of phylogenetic networks that have been proposed in the literature, the subclass of binary tree-child networks is one of the most studied ones. However, very little is known about the combinatorial structure of these networks. In this paper we address the problem of generating all possible binary tree-child (BTC) networks with a given number of leaves in an efficient way via reduction/augmentation operations that extend and generalize analogous operations for phylogenetic trees, and are biologically relevant. Since our solution is recursive, this also provides us with a recurrence relation giving an upper bound on the number of such networks. We also show how the operations introduced in this paper can be employed to extend the evolutive history of a set of sequences, represented by a BTC network, to include a new sequence. An implementation in python of the algorithms described in this paper, along with some computational experiments, can be downloaded from https://github.com/bielcardona/TCGenerators., Research of GC and JCP has been partially supported by the Spanish Ministry of Science, Innovation and Universities (http://www.ciencia.gob.es/) and European Regional Development Fund (https://ec.europa.eu/regional_policy/es/funding/erdf/) projects DPI2015-67082-P and PGC2018-096956-B-C43. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.

Computational modeling of engineered gene circuits is an important while challenged task in systems biology. In order to describe and predict the response behaviors of genetic circuits using reliable model parameters, this paper applies an optimal experimental design(OED) method to obtain input signals. In order to obtain informative observations, this study focuses on maximizing Fisher information matrix(FIM)-based optimal criteria and to provide optimal inputs. Furthermore, this paper designs a two-stage optimization with the modified E-optimal criteria and applies harmony search(HS)-based OED algorithm to minimize estimation errors. The proposed optimal identification methodology involves estimation errors and the sample size to pursue a trade-off between estimation accuracy and measurement cost in modeling gene networks. The designed cost function takes two major factors into account, in which experimental costs are proportional to the number of time points. Experiments select two types of synthetic genetic networks to validate the effectiveness of the proposed HS-OED approach. Identification outcomes and analysis indicate the proposed HS-OED method outperforms two candidate OED approaches, with reduced computational effort.

Phylogenetic networks are rooted, directed, acyclic graphs that model reticulate evolutionary histories. Recently, statistical methods were devised for inferring such networks from either gene tree estimates or the sequence alignments of multiple unlinked loci. Bi-allelic markers, most notably single nucleotide polymorphisms (SNPs) and amplified fragment length polymorphisms (AFLPs), provide a powerful source of genome-wide data. In a recent paper, a method called SNAPP was introduced for statistical inference of species trees from unlinked bi-allelic markers. The generative process assumed by the method combined both a model of evolution for the bi-allelic markers, as well as the multispecies coalescent. A novel component of the method was a polynomial-time algorithm for exact computation of the likelihood of a fixed species tree via integration over all possible gene trees for a given marker. Here we report on a method for Bayesian inference of phylogenetic networks from bi-allelic markers. Our method significantly extends the algorithm for exact computation of phylogenetic network likelihood via integration over all possible gene trees. Unlike the case of species trees, the algorithm is no longer polynomial-time on all instances of phylogenetic networks. Furthermore, the method utilizes a reversible-jump MCMC technique to sample the posterior of phylogenetic networks given bi-allelic marker data. Our method has a very good performance in terms of accuracy and robustness as we demonstrate on simulated data, as well as a data set of multiple New Zealand species of the plant genus Ourisia (Plantaginaceae). We implemented the method in the publicly available, open-source PhyloNet software package., Author summary The availability of genomic data has revolutionized the study of evolutionary histories and phylogeny inference. Inferring evolutionary histories from genomic data requires, in most cases, accounting for the fact that different genomic regions could have evolutionary histories that differ from each other as well as from that of the species from which the genomes were sampled. In this paper, we introduce a method for inferring evolutionary histories while accounting for two processes that could give rise to such differences across the genomes, namely incomplete lineage sorting and hybridization. We introduce a novel algorithm for computing the likelihood of phylogenetic networks from bi-allelic genetic markers and use it in a Bayesian inference method. Analyses of synthetic and empirical data sets show a very good performance of the method in terms of the estimates it obtains.

In this work, we proposed a hybrid pointer network (HPN), an end-to-end deep reinforcement learning architecture is provided to tackle the travelling salesman problem (TSP). HPN builds upon graph pointer networks, an extension of pointer networks with an additional graph embedding layer. HPN combines the graph embedding layer with the transformer’s encoder to produce multiple embeddings for the feature context. We conducted extensive experimental work to compare HPN and Graph pointer network (GPN). For the sack of fairness, we used the same setting as proposed in GPN paper. The experimental results show that our network significantly outperforms the original graph pointer network for small and large-scale problems. For example, it reduced the cost for travelling salesman problems with 50 cities/nodes (TSP50) from 5.959 to 5.706 without utilizing 2opt. Moreover, we solved benchmark instances of variable sizes using HPN and GPN. The cost of the solutions and the testing times are compared using Linear mixed effect models. We found that our model yields statistically significant better solutions in terms of the total trip cost. We make our data, models, and code publicly available https://github.com/AhmedStohy/Hybrid-Pointer-Networks.

Decision-making about pandemic mitigation often relies upon simulation modelling. Models of disease transmission through networks of contacts--between individuals or between population centres--are increasingly used for these purposes. Real-world contact networks are rich in structural features that influence infection transmission, such as tightly-knit local communities that are weakly connected to one another. In this paper, we propose a new flow-based edge-betweenness centrality method for detecting bottleneck edges that connect nodes in contact networks. In particular, we utilize convex optimization formulations based on the idea of diffusion with p-norm network flow. Using simulation models of COVID-19 transmission through real network data at both individual and county levels, we demonstrate that targeting bottleneck edges identified by the proposed method reduces the number of infected cases by up to 10% more than state-of-the-art edge-betweenness methods. Furthermore, the proposed method is orders of magnitude faster than existing methods., Comment: 38 pages, 21 figures

Entropy is an important index for describing the structure, function, and evolution of network. The existing research on entropy is primarily applied to undirected networks. Compared with an undirected network, a directed network involves a special asymmetric transfer. The research on the entropy of directed networks is very significant to effectively quantify the structural information of the whole network. Typical complex network models include nearest-neighbour coupling network, small-world network, scale-free network, and random network. These network models are abstracted as undirected graphs without considering the direction of node connection. For complex networks, modeling through the direction of network nodes is extremely challenging. In this paper, based on these typical models of complex network, a directed network model considering node connection in-direction is proposed, and the eigenvalue entropies of three matrices in the directed network is defined and studied, where the three matrices are adjacency matrix, in-degree Laplacian matrix and in-degree signless Laplacian matrix. The eigenvalue-based entropies of three matrices are calculated in directed nearest-neighbor coupling, directed small world, directed scale-free and directed random networks. Through the simulation experiment on the real directed network, the result shows that the eigenvalue entropy of the real directed network is between the eigenvalue entropy of directed scale-free network and directed small-world network.

Due to the lack of dependency for routing initiation and an inadequate allocated sextant on responding messages, the secure geographic routing protocols for Wireless Sensor Networks (WSNs) have attracted considerable attention. However, the existing protocols are more likely to drop packets when legitimate nodes fail to respond to the routing initiation messages while attackers in the allocated sextant manage to respond. Furthermore, these protocols are designed with inefficient collection window and inadequate verification criteria which may lead to a high number of attacker selections. To prevent the failure to find an appropriate relay node and undesirable packet retransmission, this paper presents Secure Region-Based Geographic Routing Protocol (SRBGR) to increase the probability of selecting the appropriate relay node. By extending the allocated sextant and applying different message contention priorities more legitimate nodes can be admitted in the routing process. Moreover, the paper also proposed the bound collection window for a sufficient collection time and verification cost for both attacker identification and isolation. Extensive simulation experiments have been performed to evaluate the performance of the proposed protocol in comparison with other existing protocols. The results demonstrate that SRBGR increases network performance in terms of the packet delivery ratio and isolates attacks such as Sybil and Black hole.

The traditional full-scan method is commonly used for identifying critical links in road networks. This method simulates each link to be closed iteratively and measures its impact on the efficiency of the whole network. It can accurately identify critical links. However, in this method, traffic assignments are conducted under all scenarios of link disruption, making this process prohibitively time-consuming for large-scale road networks. This paper proposes an approach considering the traffic flow betweenness index (TFBI) to identify critical links, which can significantly reduce the computational burden compared with the traditional full-scan method. The TFBI consists of two parts: traffic flow betweenness and endpoint origin-destination (OD) demand (rerouted travel demand). There is a weight coefficient between these two parts. Traffic flow betweenness is established by considering the shortest travel-time path betweenness, link traffic flow and total OD demand. The proposed approach consists of the following main steps. First, a sample road network is selected to calibrate the weight coefficient between traffic flow betweenness and endpoint OD demand in the TFBI using the network robustness index. This index calculates changes in the whole-system travel time due to each link's closure under the traditional full-scan method. Then, candidate critical links are pre-selected according to the TFBI value of each link. Finally, a given number of real critical links are identified from the candidate critical links using the traditional full-scan method. The applicability and computational efficiency of the TFBI-based approach are demonstrated for the road network in Changchun, China. Published version

Information diffusion has been widely discussed in various disciplines including sociology, economics, physics or computer science. In this paper, we generalize the linear threshold model in signed networks consisting of both positive and negative links. We analyze the dynamics of the spread of information based on balance theory, and find that a signed network can generate path dependence while structural balance can help remove the path dependence when seeded with balanced initialized active nodes. Simulation shows that the diffusion of information based on positive links contradicts that based on negative links. More positive links in signed networks are more likely to activate nodes and remove path dependence, but they can reduce predictability that is based on active states. We also find that a balanced structure can facilitate both the magnitude and speed of information diffusion, remove the path dependence, and cause polarization.

Orienteering problem (OP) is a routing problem, where the aim is to generate a path through set of nodes, which would maximize total score and would not exceed the budget. In this paper, we present an extension of classic OP-Orienteering Problem with Functional Profits (OPFP), where the score of a specific point depends on its characteristics, position in the route, and other points in the route. For solving OPFP, we developed an open-source framework for solving orienteering problems, which utilizes four core components of OP in its modular architecture. Fully-written in Go programming language our framework can be extended for solving different types of tasks with different algorithms; this was demonstrated by implementation of two popular algorithms for OP solving-Ant Colony Optimization and Recursive Greedy Algorithm. Computational efficiency of the framework was shown through solving four well-known OP types: classic Orienteering Problem (OP), Orienteering Problem with Compulsory Vertices (OPCV), Orienteering Problem with Time Windows (OPTW), and Time Dependent Orienteering Problem (TDOP) along with OPFP. Experiments were conducted on a large multi-source dataset for Saint Petersburg, Russia, containing data from Instagram, TripAdvisor, Foursquare and official touristic website. Our framework is able to construct touristic paths for different OP types within few seconds using dataset with thousands of points of interest.

The fundamental utility of the Large-Scale Visual Sensor Networks (LVSNs) is to monitor specified events and to transmit the detected information back to the sink for achieving the data aggregation purpose. However, the events of interest are usually not uniformly distributed but frequently detected in certain regions in real-world applications. It implies that when the events frequently picked up by the sensors in the same region, the transmission load of LVSNs is unbalanced and potentially cause the energy hole problem. To overcome this kind of problem for network lifetime, a Comprehensive Visual Data Gathering Network Architecture (CDNA), which is the first comparatively integrated architecture for LVSNs is designed in this paper. In CDNA, a novel α-hull based event location algorithm, which is oriented from the geometric model of α-hull, is designed for accurately and efficiently detect the location of the event. In addition, the Chi-Square distribution event-driven gradient deployment method is proposed to reduce the unbalanced energy consumption for alleviating energy hole problem. Moreover, an energy hole repairing method containing an efficient data gathering tree and a movement algorithm is proposed to ensure the efficiency of transmitting and solving the energy hole problem. Simulations are made for examining the performance of the proposed architecture. The simulation results indicate that the performance of CDNA is better than the previous algorithms in the realistic LVSN environment, such as the significant improvement of the network lifetime.

The prediction of protein complexes from protein-protein interactions (PPIs) is a well-studied problem in bioinformatics. However, the currently available PPI data is not enough to describe all known protein complexes. In this paper, we express the problem of determining the minimum number of (additional) required protein-protein interactions as a graph theoretic problem under the constraint that each complex constitutes a connected component in a PPI network. For this problem, we develop two computational methods: one is based on integer linear programming (ILPMinPPI) and the other one is based on an existing greedy-type approximation algorithm (GreedyMinPPI) originally developed in the context of communication and social networks. Since the former method is only applicable to datasets of small size, we apply the latter method to a combination of the CYC2008 protein complex dataset and each of eight PPI datasets (STRING, MINT, BioGRID, IntAct, DIP, BIND, WI-PHI, iRefIndex). The results show that the minimum number of additional required PPIs ranges from 51 (STRING) to 964 (BIND), and that even the four best PPI databases, STRING (51), BioGRID (67), WI-PHI (93) and iRefIndex (85), do not include enough PPIs to form all CYC2008 protein complexes. We also demonstrate that the proposed problem framework and our solutions can enhance the prediction accuracy of existing PPI prediction methods. ILPMinPPI can be freely downloaded from http://sunflower.kuicr.kyoto-u.ac.jp/~nakajima/.

A popular objective criterion for partitioning a set of actors into core and periphery subsets is the maximization of the correlation between an ideal and observed structure associated with intra-core and intra-periphery ties. The resulting optimization problem has commonly been tackled using heuristic procedures such as relocation algorithms, genetic algorithms, and simulated annealing. In this paper, we present a computationally efficient simulated annealing algorithm for maximum correlation core/periphery partitioning of binary networks. The algorithm is evaluated using simulated networks consisting of up to 2000 actors and spanning a variety of densities for the intra-core, intra-periphery, and inter-core-periphery components of the network. Core/periphery analyses of problem solving, trust, and information sharing networks for the frontline employees and managers of a consumer packaged goods manufacturer are provided to illustrate the use of the model.

Graphlet analysis is an approach to network analysis that is particularly popular in bioinformatics. We show how to set up a system of linear equations that relate the orbit counts and can be used in an algorithm that is significantly faster than the existing approaches based on direct enumeration of graphlets. The approach presented in this paper presents a generalization of the currently fastest method for counting 5-node graphlets in bioinformatics. The algorithm requires existence of a vertex with certain properties; we show that such vertex exists for graphlets of arbitrary size, except for complete graphs and a cycle with four nodes, which are treated separately. Empirical analysis of running time agrees with the theoretical results.

Traffic state estimation from the floating car system is a challenging problem. The low penetration rate and random distribution make available floating car samples usually cover part space and time points of the road networks. To obtain a wide range of traffic state from the floating car system, many methods have been proposed to estimate the traffic state for the uncovered links. However, these methods cannot provide traffic state of the entire road networks. In this paper, the traffic state estimation is transformed to solve a missing data imputation problem, and the tensor completion framework is proposed to estimate missing traffic state. A tensor is constructed to model traffic state in which observed entries are directly derived from floating car system and unobserved traffic states are modeled as missing entries of constructed tensor. The constructed traffic state tensor can represent spatial and temporal correlations of traffic data and encode the multi-way properties of traffic state. The advantage of the proposed approach is that it can fully mine and utilize the multi-dimensional inherent correlations of traffic state. We tested the proposed approach on a well calibrated simulation network. Experimental results demonstrated that the proposed approach yield reliable traffic state estimation from very sparse floating car data, particularly when dealing with the floating car penetration rate is below 1%.

In this paper, the synchronization problem for a class of discrete-time complex-valued neural networks with time-varying delays is investigated. Compared with the previous work, the time delay and parameters are assumed to be time-varying. By separating the real part and imaginary part, the discrete-time model of complex-valued neural networks is derived. Moreover, by using the complex-valued Lyapunov-Krasovskii functional method and linear matrix inequality as tools, sufficient conditions of the synchronization stability are obtained. In numerical simulation, examples are presented to show the effectiveness of our method.

The concept of robustness of regulatory networks has received much attention in the last decade. One measure of robustness has been associated with the volume of the feasible region, namely, the region in the parameter space in which the system is functional. In this paper, we show that, in addition to volume, the geometry of this region has important consequences for the robustness and the fragility of a network. We develop an approximation within which we could algebraically specify the feasible region. We analyze the segment polarity gene network to illustrate our approach. The study of random walks in the parameter space and how they exit the feasible region provide us with a rich perspective on the different modes of failure of this network model. In particular, we found that, between two alternative ways of activating Wingless, one is more robust than the other. Our method provides a more complete measure of robustness to parameter variation. As a general modeling strategy, our approach is an interesting alternative to Boolean representation of biochemical networks., Author Summary Developing models with a large number of parameters for describing the dynamics of a biochemical network is a common exercise today. The dependence of predictions of such a network model on the choice of parameters is important to understand for two reasons. For the purpose of fitting biological data and making predictions, we need to know which combinations of parameters are strongly constrained by observations and also which combinations seriously affect a particular prediction. In addition, we expect naturally evolved networks to be somewhat robust to parameter changes. If the functioning of the network requires fine-tuning in many parameters, then mutations causing changes in regulatory interactions could quickly make the network dysfunctional. For predictions involving gene products being ON or OFF, we found a method that facilitates the study parameter dependence. As an example, we analyzed several competing models of the segment polarity network in Drosophila. We explicitly describe the region in the parameter space where the wild-type expression pattern of key genes becomes feasible for each model. We also study how random walks in the parameter space exit from the feasible region of a network model, allowing us to compare the relative robustness of the alternative models.