Search

Motivation: Precision medicine is an emerging field with hopes to improve patient treatment and reduce morbidity and mortality. To these ends, computational approaches have predicted associations among genes, chemicals and diseases. Such efforts, however, were often limited to using just some available association types. This lowers prediction coverage and, since prior evidence shows that integrating heterogeneous data is likely beneficial, it may limit accuracy. Therefore, we systematically tested whether using more association types improves prediction., Results: We study multimodal networks linking diseases, genes and chemicals (drugs) by applying three diffusion algorithms and varying information content. Ten-fold cross-validation shows that these networks are internally consistent, both within and across association types. Also, diffusion methods recovered missing edges, even if all the edges from an entire mode of association were removed. This suggests that information is transferable between these association types. As a realistic validation, time-stamped experiments simulated the predictions of future associations based solely on information known prior to a given date. The results show that many future published results are predictable from current associations. Moreover, in most cases, using more association types increases prediction coverage without significantly decreasing sensitivity and specificity. In case studies, literature-supported validation shows that these predictions mimic human-formulated hypotheses. Overall, this study suggests that diffusion over a more comprehensive multimodal network will generate more useful hypotheses of associations among diseases, genes and chemicals, which may guide the development of precision therapies., Availability and Implementation: Code and data are available at https://github.com/LichtargeLab/multimodal-network-diffusion., Supplementary Information: Supplementary data are available at Bioinformatics online., (© The Author(s) 2018. Published by Oxford University Press. All rights reserved. For permissions, please e-mail: journals.permissions@oup.com.)

Network alignment has extensive applications in comparative interactomics. Traditional approaches aim to simultaneously maximize the number of conserved edges and the underlying similarity of aligned entities. We propose a novel formulation of the network alignment problem that extends topological similarity to higher-order structures and provides a new objective function that maximizes the number of aligned substructures. This objective function corresponds to an integer programming problem, which is NP-hard. Consequently, we identify a closely related surrogate function whose maximization results in a tensor eigenvector problem. Based on this formulation, we present an algorithm called Triangular AlignMEnt (TAME), which attempts to maximize the number of aligned triangles across networks. Using a case study on the NAPAbench dataset, we show that triangular alignment is capable of producing mappings with high node correctness. We further evaluate our method by aligning yeast and human interactomes. Our results indicate that TAME outperforms the state-of-art alignment methods in terms of conserved triangles. In addition, we show that the number of conserved triangles is more significantly correlated, compared to the conserved edge, with node correctness and co-expression of edges. Our formulation and resulting algorithms can be easily extended to arbitrary motifs.

Clustering points in a vector space or nodes in a graph is a ubiquitous primitive in statistical data analysis, and it is commonly used for exploratory data analysis. In practice, it is often of interest to "refine"" or "improve"" a given cluster that has been obtained by some other method. In this survey, we focus on principled algorithms for this cluster improvement problem. Many such cluster improvement algorithms are flow-based methods, by which we mean that operationally they require the solution of a sequence of maximum flow problems on a (typically implicitly) modified data graph. These cluster improvement algorithms are powerful, both in theory and in practice, but they have not been widely adopted for problems such as community detection, local graph clustering, semisupervised learning, etc. Possible reasons for this are the steep learning curve for these algorithms, the lack of efficient and easy-to-use software, and the lack of detailed numerical experiments on real-world data that demonstrate their usefulness. Our objective here is to address these issues. To do so, we guide the reader through the whole process of understanding how to implement and apply these powerful algorithms. We present a unifying fractional programming optimization framework that permits us to distill, in a simple way, the crucial components of all these algorithms. This also makes apparent similarities and differences among related methods. Viewing these cluster improvement algorithms via a fractional programming framework suggests directions for future algorithm development. Finally, we develop efficient implementations of these algorithms in our LocalGraphClustering Python package, and we perform extensive numerical experiments to demonstrate the performance of these methods on social networks and image-based data graphs. [ABSTRACT FROM AUTHOR]

Context: Maximum clique analysis (MCA) can approximate landscape carrying capacity (Nk) for populations of territorial wildlife. However, MCA has not been widely adopted for wildlife applications, mainly due to computational constraints and software wildlife biologists may find difficult to use. Moreover, MCA does not incorporate uncertainty into estimates of Nk. Objectives: We extended MCA by applying a vertex cover algorithm to compute Nk over a large (92,789 km2), continuous spatial scale for female bobcats (Lynx rufus) in Indiana, USA. We incorporated uncertainty by calculating confidence intervals for Nk across five thresholds of habitat suitability using 10 replicate suitability maps from bootstrapped datasets. For portions of the landscape too large to be solved with the vertex cover algorithm, we compared predictions from a linear model and a "greedy" algorithm. Results: Mean estimates of Nk for female bobcats in Indiana across habitat suitability thresholds ranged from 539 (0.75 threshold) to 1200 territories (0.25 threshold). On average, each 12.5 percentile reduction in the suitability threshold increased estimates for Nk by 1.2-fold. Both the predictive and greedy algorithm produced reasonable estimates of maximum cliques for areas that were too large to compute with the vertex cover algorithm. The greedy algorithm produced smaller confidence intervals compared to the predictive approach but underestimated maximum cliques by 1.2%. Conclusions: Our research demonstrates effective application of MCA to species occupying large landscapes while accounting for uncertainty. We believe our methods, coupled with availability of annotated scripts developed in R, will make MCA more broadly accessible to wildlife biologists. [ABSTRACT FROM AUTHOR]

Multiple network alignment is the problem of identifying similar and related regions in a given set of networks. While there are a large number of effective techniques for pairwise problems with two networks that scale in terms of edges, these cannot be readily extended to align multiple networks as the computational complexity will tend to grow exponentially with the number of networks. In this manuscript we introduce a new multiple network alignment algorithm and framework that is effective at aligning thousands of networks with thousands of nodes. The key enabling technique of our algorithm is identifying an exact and easy to compute low-rank tensor structure inside of a principled heuristic procedure for pairwise network alignment called IsoRank. This can be combined with a new algorithm for k-dimensional matching problems on low-rank tensors to produce the alignment. We demonstrate results on synthetic and real-world problems that show our technique (i) is as good as or better than, in terms of quality, existing methods, when they work on small problems, while running considerably faster, and (ii) is able to scale to aligning a number of networks unreachable by current methods. [ABSTRACT FROM AUTHOR]

We study a novel variation on the Ulam{von Neumann Monte Carlo method for solving a linear system. This is an old randomized procedure that results from using a random walk to stochastically evaluate terms in the Neumann series. In order to apply this procedure, the variance of the stochastic estimator needs to be bounded. The best known suficient condition for bounding the variance is that the infinity norm of the matrix in the Neumann series is smaller than one, which greatly limits the usability of this method. We improve this condition by proposing a new stochastic estimator based on a different type of random walk. Our multiway walk and estimator is based on a time-inhomogeneous Markov process that iterates through a sequence of transition matrices built from the original linear system. For our new method, we prove that a necessary and suficient condition for convergence is that the spectral radius of the elementwise absolute value of the matrix underlying the Neumann series is smaller than one. This is a strictly weaker condition than currently exists. In addition, our new method is often faster than the standard algorithm. Through experiments, we demonstrate the potential for our method to reduce the time needed to solve linear equations by incorporating it into an outer iterative method. [ABSTRACT FROM AUTHOR]

We present a parallel algorithm for the undirected s – t min-cut problem with floating-point valued edge weights. Our overarching algorithm uses an iteratively reweighted least squares framework. Specifically, this algorithm generates a sequence of Laplacian linear systems, which are solved in parallel. The iterative nature of our algorithm enables us to trade off solution quality for execution time, which is distinguished from those purely combinatorial algorithms that only produce solutions at optimum. We also propose a novel two-level rounding procedure that helps to enhance the quality of the approximate min-cut solution output by our algorithm. Our overall implementation, including the rounding procedure, demonstrates significant speed improvement over a state-of-the-art serial solver, where it could be up to 200 times faster on commodity platforms. [ABSTRACT FROM AUTHOR]

Community detection is an important task in network analysis. A community (also referred to as a cluster) is a set of cohesive vertices that have more connections inside the set than outside. In many social and information networks, these communities naturally overlap. For instance, in a social network, each vertex in a graph corresponds to an individual who usually participates in multiple communities. In this paper, we propose an efficient overlapping community detection algorithm using a seed expansion approach. The key idea of our algorithm is to find good seeds, and then greedily expand these seeds based on a community metric. Within this seed expansion method, we investigate the problem of how to determine good seed nodes in a graph. In particular, we develop new seeding strategies for a personalized PageRank clustering scheme that optimizes the conductance community score. An important step in our method is the neighborhood inflation step where seeds are modified to represent their entire vertex neighborhood. Experimental results show that our seed expansion algorithm outperforms other state-of-the-art overlapping community detection methods in terms of producing cohesive clusters and identifying ground-truth communities. We also show that our new seeding strategies are better than existing strategies, and are thus effective in finding good overlapping communities in real-world networks. [ABSTRACT FROM PUBLISHER]

SUMMARY Circulant matrices play a central role in a recently proposed formulation of three-way data computations. In this setting, a three-way table corresponds to a matrix where each 'scalar' is a vector of parameters defining a circulant. This interpretation provides many generalizations of results from matrix or vector-space algebra. These results and algorithms are closely related to standard decoupling techniques on block-circulant matrices using the fast Fourier transform. We derive the power and Arnoldi methods in this algebra. In the course of our derivation, we define inner products, norms, and other notions. These extensions are straightforward in an algebraic sense, but the implications are dramatically different from the standard matrix case. For example, the number of eigenpairs may exceed the dimension of the matrix, although it is still polynomial in it. It is thus necessary to take an extra step and carefully select a smaller, canonical set of size equal to the dimension of the matrix from which all possible eigenpairs can be formed. Copyright © 2012 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Network alignment generalizes and unifies several approaches for forming a matching or alignment between the vertices of two graphs. We study a mathematical programming framework for network alignment problem and a sparse variation of it where only a small number of matches between the vertices of the two graphs are possible. We propose a new message passing algorithm that allows us to compute, very efficiently, approximate solutions to the sparse network alignment problems with graph sizes as large as hundreds of thousands of vertices. We also provide extensive simulations comparing our algorithms with two of the best solvers for network alignment problems on two synthetic matching problems, two bioinformatics problems, and three large ontology alignment problems including a multilingual problem with a known labeled alignment. [ABSTRACT FROM AUTHOR]

We present a new iterative scheme for PageRank computation. The algorithm is applied to the linear system formulation of the problem, using inner-outer stationary iterations. It is simple, can be easily implemented and parallelized, and requires minimal storage overhead. Our convergence analysis shows that the algorithm is effective for a crude inner tolerance and is not sensitive to the choice of the parameters involved. The same idea can be used as a preconditioning technique for nonstationary schemes. Numerical examples featuring matrices of dimensions exceeding 100,000,000 in sequential and parallel environments demonstrate the merits of our technique. Our code is available online for viewing and testing, along with several large scale examples. [ABSTRACT FROM AUTHOR]