Fast and Simple Approximation of the Diameter and Radius of a Graph
The increasing amount of data to be processed by computers has led to the need for highly efficient algorithms for various computational problems. Moreover, the algorithms should be as simple as possible to be practically applicable. In this paper we propose a very simple approximation algorithm for finding the diameter and the radius of an undirected graph. The algorithm runs in $O(m\sqrt{n})$ time and gives an additive error of $O(\sqrt{n})$ for a graph with n vertices and m edges. Practical experiments show that the results of our algorithm are close to the optimum and compare favorably to the 2/3-approximation algorithm for the diameter problem by Aingworth et al [1].
Application of Graph Clustering and Visualisation Methods to Analysis of Biomolecular Data
In this paper we present an approach based on integrated use of graph clustering and visualisation methods for semi-supervised discovery of biologically significant features in biomolecular data sets. We describe several clustering algorithms that have been custom designed for analysis of biomolecular data and feature an iterated two step approach involving initial computation of thresholds and other parameters used in clustering algorithms, which is followed by identification of connected graph components, and, if needed, by adjustment of clustering parameters for processing of individual subgraphs.
Disconnected Graph Layout and the Polyomino Packing Approach
Conference name: GD: International Symposium on Graph Drawing 9th International Symposium Date of Conference: 23–26 September 2001 We review existing algorithms and present a new approach for layout of disconnected graphs. The new approach is based on polyomino representation of components as opposed to rectangles. The parameters of our algorithm and their influence on the drawings produced as well as a variation of the algorithm for multiple pages are discussed. We also analyze our algorithm both theoretically and experimentally and compare it with the existing ones. The new approach produces much more compact and uniform drawings than previous methods. © Springer-Verlag Berlin Heidelberg …
Graph-based network analysis of transcriptional regulation pattern divergence in duplicated yeast gene pairs
The genome and interactome of Saccharomyces cerevisiae have been characterized extensively over the course of the past few decades. However, despite many insights gained over the years, both functional studies and evolutionary analyses continue to reveal many complexities and confounding factors in the construction of reliable transcriptional regulatory network models. We present here a graph-based technique for comparing transcriptional regulatory networks based on network motif similarity for gene pairs. We construct interaction graphs for duplicated transcription factor pairs traceable to the ancestral whole-genome duplication as well as other paralogues in Saccharomyces cerevisiae. We c…
Matrix Shuffle- Exchange Networks for Hard 2D Tasks
Convolutional neural networks have become the main tools for processing two-dimensional data. They work well for images, yet convolutions have a limited receptive field that prevents its applications to more complex 2D tasks. We propose a new neural model, called Matrix Shuffle-Exchange network, that can efficiently exploit long-range dependencies in 2D data and has comparable speed to a convolutional neural network. It is derived from Neural Shuffle-Exchange network and has O(log N) layers and O(N ^ 2 log N) total time and O(N^2) space complexity for processing a NxN data matrix. We show that the Matrix Shuffle-Exchange network is well-suited for algorithmic and logical reasoning tasks on …
Curved Edge Routing
We consider the problem of drawing a graph where edges are represented by smooth curves between the associated nodes. Previously curved edges were drawn as splines defined by carefully calculated control points. We present a completely different approach where finding an edge is reduced to solving a differential equation. This approach allows to represent the graph drawing aesthetics directly, even the most complex ones denoting the dependencies among the paths.
Using Deep Learning to Extrapolate Protein Expression Measurements
Mass spectrometry (MS)-based quantitative proteomics experiments typically assay a subset of up to 60% of the ≈20 000 human protein coding genes. Computational methods for imputing the missing values using RNA expression data usually allow only for imputations of proteins measured in at least some of the samples. In silico methods for comprehensively estimating abundances across all proteins are still missing. Here, a novel method is proposed using deep learning to extrapolate the observed protein expression values in label-free MS experiments to all proteins, leveraging gene functional annotations and RNA measurements as key predictive attributes. This method is tested on four datasets, in…
A Potential Field Function for Overlapping Point Set and Graph Cluster Visualization
In this paper we address the problem of visualizing overlapping sets of points with a fixed positioning in a comprehensible way. A standard visualization technique is to enclose the point sets in isocontours generated by bounding a potential field function. The most commonly used functions are various approximations of the Gaussian distribution. Such an approach produces smooth and appealing shapes, however it may produce an incorrect point nesting in generated regions, e.g. some point is contained inside a foreign set region. We introduce a different potential field function that keeps the desired properties of Gaussian distribution, and in addition guarantees that every point belongs to a…
Implementing a Face Recognition System for Media Companies
During the past few years face recognition technologies have greatly benefited from the huge progress in machine learning and now have achieved precision rates that are even comparable with humans. This allows us to apply face recognition technologies more effectively for a number of practical problems in various businesses like media monitoring, security, advertising, entertainment that we previously were not able to do due to low precision rates of existing face recognition technologies. In this paper we discuss how to build a face recognition system for media companies and share our experience gained from implementing one for Latvian national news agency LETA. Our contribution is: which …
Topological structure analysis of chromatin interaction networks.
Abstract Background Current Hi-C technologies for chromosome conformation capture allow to understand a broad spectrum of functional interactions between genome elements. Although significant progress has been made into analysis of Hi-C data to identify biologically significant features, many questions still remain open, in particular regarding potential biological significance of various topological features that are characteristic for chromatin interaction networks. Results It has been previously observed that promoter capture Hi-C (PCHi-C) interaction networks tend to separate easily into well-defined connected components that can be related to certain biological functionality, however, …
Network motif-based analysis of regulatory patterns in paralogous gene pairs
Current high-throughput experimental techniques make it feasible to infer gene regulatory interactions at the whole-genome level with reasonably good accuracy. Such experimentally inferred regulatory networks have become available for a number of simpler model organisms such as S. cerevisiae, and others. The availability of such networks provides an opportunity to compare gene regulatory processes at the whole genome level, and in particular, to assess similarity of regulatory interactions for homologous gene pairs either from the same or from different species. We present here a new technique for analyzing the regulatory interaction neighborhoods of paralogous gene pairs. Our central focu…
A Nondifferentiable Optimization Approach to Ratio-Cut Partitioning
We propose a new method for finding the minimum ratio-cut of a graph. Ratio-cut is NP-hard problem for which the best previously known algorithm gives an O(log n)-factor approximation by solving its dually related maximum concurrent flow problem.We formulate the minimum ratio-cut as a certain nondifferentiable optimization problem, and show that the global minimum of the optimization problem is equal to the minimum ratio-cut. Moreover, we provide strong symbolic computation based evidence that any strict local minimum gives an approximation by a factor of 2. We also give an efficient heuristic algorithm for finding a local minimum of the proposed optimization problem based on standard nondi…
Logo detection in images using HOG and SIFT
In this paper we present a study of logo detection in images from a media agency. We compare two most widely used methods — HOG and SIFT on a challenging dataset of images arising from a printed press and news portals. Despite common opinion that SIFT method is superior, our results show that HOG method performs significantly better on our dataset. We augment the HOG method with image resizing and rotation to improve its performance even more. We found out that by using such approach it is possible to obtain good results with increased recall and reasonably decreased precision.