The computation of the global minimum energy conformation (GMEC) is an important and challenging topic in structure-based computational protein design. In this paper, we propose a new protein design algorithm based on the AND OR branch-and-bound (AOBB) search, which is a variant of the traditional branch-and-bound search algorithm, to solve this combinatorial optimization problem. By integrating with a powerful heuristic function, AOBB is able to fully exploit the graph structure of the underlying residue interaction network of a backbone template to significantly accelerate the design process. Tests on real protein data show that our new protein design algorithm is able to solve many prob- lems that were previously unsolvable by the traditional exact search algorithms, and for the problems that can be solved with traditional provable algorithms, our new method can provide a large speedup by several orders of magnitude while still guaranteeing to find the global minimum energy conformation (GMEC) solution.
The traditional BnB search algorithm @cite_0 usually ignores the underlying topological information of the residue interaction network constructed based on the backbone template, while AOBB is designed to exploit this property.
@cite_0
2134002980
Elastic network models have been successful in elucidating the largest scale collective motions of proteins. These models are based on a set of highly coupled springs, where only the close neighboring amino acids interact, without any residue specificity. Our objective here is to determine whether the equivalent cooperative motions can be obtained upon further coarse-graining of the protein structure along the backbone. The influenza virus hemagglutinin A (HA), composed of N = 1509 residues, is utilized for this analysis. Elastic network model calculations are performed for coarse-grained HA structures containing only N 2, N 10, N 20, and N 40 residues along the backbone. High correlations (>0.95) between residue fluctuations are obtained for the first dominant (slowest) mode of motion between the original model and the coarse-grained models. In the case of coarse-graining by a factor of 1 40, the slowest mode shape for HA is reconstructed for all residues by successively selecting different subsets of residues, shifting one residue at a time. The correlation for this reconstructed first mode shape with the original all-residue case is 0.73, while the computational time is reduced by about three orders of magnitude. The reduction in computational time will be much more significant for larger targeted structures. Thus, the dominant motions of protein structures are robust enough to be captured at extremely high levels of coarse-graining. And more importantly, the dynamics of extremely large complexes are now accessible with this new methodology. ADOPT and BnB-ADOPT are two optimal DCOP search algorithms that are similar except for their search strategies: the former uses best-first search and the latter uses depth-first branch-and-bound search. In this paper, we present a new algorithm, called ADOPT(k), that generalizes them. Its behavior depends on the k parameter. It behaves like ADOPT when k = 1, like BnB-ADOPT when k = ∞ and like a hybrid of ADOPT and BnB-ADOPT when 1 < k < ∞. We prove that ADOPT(k) is a correct and complete algorithm and experimentally show that ADOPT(k) outperforms ADOPT and BnB-ADOPT on several benchmarks across several metrics. Recently there has been a surge of interest to use branch-and-bound (bnb) optimisation for 3D point cloud registration. While bnb guarantees globally optimal solutions, it is usually too slow to be practical. A fundamental source of difficulty is the search for the rotation parameters in the 3D rigid transform. In this work, assuming that the translation parameters are known, we focus on constructing a fast rotation search algorithm. With respect to an inherently robust geometric matching criterion, we propose a novel bounding function for bnb that allows rapid evaluation. Underpinning our bounding function is the usage of stereographic projections to precompute and spatially index all possible point matches. This yields a robust and global algorithm that is significantly faster than previous methods. To conduct full 3D registration, the translation can be supplied by 3D feature matching, or by another optimisation framework that provides the translation. On various challenging point clouds, including those taken out of lab settings, our approach demonstrates superior efficiency. In a large and complex distributed sensor network, the individual sensor directly communicates only with its neighboring sensors. Despite being restricted to such local communications, the network itself should be self-organizing to maintain certain desirable properties, such as network connectivity and lifetime maximization. Topology control is a technique to determine the optimal transmit parameters for each sensor, such that the network topology has the best possible network performance. In this paper, we investigate a dynamic topology control scheme to improve the network lifetime for wireless sensor networks in the presence of selfish sensors. A non-cooperative game aided topology control approach is developed for designing energy-efficient and energy balanced network topologies dynamically. Each sensor in the topology control game tries to minimize its unwillingness for constructing a connected network according to its residual energy and transmit power. We prove the existence of Nash equilibrium (NE) and demonstrate that the NE is Pareto optimal as well. Specifically, a fully distributed algorithm-topology control with lifetime extension (TCLE)-is proposed to construct dynamic network topologies. The topologies derived by TCLE algorithm can improve the network lifetime significantly as compared with existing algorithms. Simulations demonstrate the efficiency of our TCLE algorithm. Hexagonal wireless sensor network refers to a network topology where a subset of nodes have six peer neighbors. These nodes form a backbone for multi-hop communications. In a previous work, we proposed the use of hexagonal topology in wireless sensor networks and discussed its properties in relation to real-time (bounded latency) multi-hop communications in large-scale deployments. In that work, we did not consider the problem of hexagonal topology formation in practice — which is the subject of this research. In this paper, we present a decentralized algorithm that forms the hexagonal topology backbone in an arbitrary but sufficiently dense network deployment. We implemented a prototype of our algorithm in NesC for TinyOS based platforms. We present data from field tests of our implementation, collected using a deployment of fifty wireless sensor nodes. Virtualization has been proposed as a vehicle for overcoming the growing problem of internet ossification [1]. This paper studies the problem of mapping diverse virtual networks onto a common physical substrate. In particular, we develop a method for mapping a virtual network onto a substrate network in a cost-efficient way, while allocating sufficient capacity to virtual network links to ensure that the virtual network can handle any traffic pattern allowed by a general set of traffic constraints. Our approach attempts to find the best topology in a family of backbone-star topologies, in which a subset of nodes constitute the backbone, and the remaining nodes each connect to the nearest backbone node. We investigate the relative cost-effectiveness of different backbone topologies on different substrate networks, under a wide range of traffic conditions. Specifically, we study how the most cost-effective topology changes as the tightness of pairwise traffic constraints and the constraints on traffic locality are varied. In general, we find that as pairwise traffic constraints are relaxed, the least-cost backbone topology becomes increasingly “tree-like”. We also find that the cost of the constructed virtual networks is usually no more than 1.5 times a computed lower bound on the network cost and that the quality of solutions improves as the traffic locality gets weaker. We propose an application level multicast approach, Topology Aware Grouping (TAG), which exploits underlying network topology information to build efficient overlay networks among multicast group members. TAG uses information about path overlap among members to construct a tree that reduces the overlay relative delay penalty, and reduces the number of duplicate copies of a packet on the same link. We study the properties of TAG, and model and experiment with its economies of scale factor to quantify its benefits compared to unicast and IP multicast. We also compare the TAG approach with the ESM approach in a variety of simulation configurations including a number of real Internet topologies and generated topologies. Our results indicate the effectiveness of the algorithm in reducing delays and duplicate packets, with reasonable algorithm time and space complexities. With the advent of multi-cores and many-cores, traditional techniques that seek only to improve FLOPS of performance or the degree of parallelism have hit a roadblock with regards to providing even greater performance. In order to surmount this roadblock, techniques should more directly address the underlying design objectives of an application. Specific implementations and algorithmic choices in applications are intended to achieve the underlying realism objectives in the programmer's mind. We identify two specific aspects of this realism that traditional programming and parallelization approaches do not capture and exploit to utilize the growing number of cores. The first aspect is that the goal of minimizing program execution time can be satisfactorily met if the program execution time is low with sufficiently high probability. We exploit the fact that randomized algorithms are available for many commonly used kernels, and that the use of parallelism can achieve very low expected execution times with high probability for these algorithms. This can provide speedups to parts of the application that were hitherto deemed sequential and ignored for extracting performance via multi-cores. The second aspect of realism that we exploit is that important classes of emerging applications, like gaming and interactive visualization, have user-interactivity and responsiveness requirements that are as important as raw performance. Their design goal is to maximize the functionality expressed, while maintaining a high and smooth frame-rate. Therefore, the primary objective for these applications is not to run a fixed computation as fast as possible, but rather to scale the application semantics up or down depending on the resources available. Our framework intends to capture the responsiveness requirements of these applications as they pertain to expressed realism and automatically scale the application semantics expressed on every architecture, including very resource-rich many-cores. Several multiagent tasks can be formulated and solved as DCOPs. BnB-ADOPT+-AC is one of the most efficient algorithms for optimal DCOP solving. It is based on BnB-ADOPT, removing redundant messages and maintaining soft arc consistency during search. In this paper, we present several improvements for this algorithm, namely (i) a better implementation, (ii) processing exactly simultaneous deletions, and (iii) searching on arc consistent cost functions. We present empirical results showing the benefits of these improvements on several benchmarks. Abstract Most traditional algorithms for compressive sensing image reconstruction suffer from the intensive computation. Recently, deep learning-based reconstruction algorithms have been reported, which dramatically reduce the time complexity than iterative reconstruction algorithms. In this paper, we propose a novel Deep Residual Reconstruction Network (DR2-Net) to reconstruct the image from its Compressively Sensed (CS) measurement. The DR2-Net is proposed based on two observations: (1) linear mapping could reconstruct a high-quality preliminary image, and (2) residual learning could further improve the reconstruction quality. Accordingly, DR2-Net consists of two components, i.e., linear mapping network and residual network, respectively. Specifically, the fully-connected layer in neural network implements the linear mapping network. We then expand the linear mapping network to DR2-Net by adding several residual learning blocks to enhance the preliminary image. Extensive experiments demonstrate that the DR2-Net outperforms traditional iterative methods and recent deep learning-based methods by large margins at measurement rates 0.01, 0.04, 0.1, and 0.25, respectively. The code of DR2-Net has been released on: https: github.com coldrainyht caffe_dr2 . Many real-world domains can be represented as large node-link graphs: backbone Internet routers connect with 70,000 other hosts, mid-sized Web servers handle between 20,000 and 200,000 hyperlinked documents, and dictionaries contain millions of words defined in terms of each other. Computational manipulation of such large graphs is common, but previous tools for graph visualization have been limited to datasets of a few thousand nodes. Visual depictions of graphs and networks are external representations that exploit human visual processing to reduce the cognitive load of many tasks that require understanding of global or local structure. We assert that the two key advantages of computer-based systems for information visualization over traditional paper-based visual exposition are interactivity and scalability. We also argue that designing visualization software by taking the characteristics of a target user's task domain into account leads to systems that are more effective and scale to larger datasets than previous work. This thesis contains a detailed analysis of three specialized systems for the interactive exploration of large graphs, relating the intended tasks to the spatial layout and visual encoding choices. We present two novel algorithms for specialized layout and drawing that use quite different visual metaphors. The H3 system for visualizing the hyperlink structures of web sites scales to datasets of over 100,000 nodes by using a carefully chosen spanning tree as the layout backbone, 3D hyperbolic geometry for a Focus+Context view, and provides a fluid interactive experience through guaranteed frame rate drawing. The Constellation system features a highly specialized 2D layout intended to spatially encode domain-specific information for computational linguists checking the plausibility of a large semantic network created from dictionaries. The Planet Multicast system for displaying the tunnel topology of the Internet's multicast backbone provides a literal 3D geographic layout of arcs on a globe to help MBone maintainers find misconfigured long-distance tunnels. Each of these three systems provides a very different view of the graph structure, and we evaluate their efficacy for the intended task. We generalize these findings in our analysis of the importance of interactivity and specialization for graph visualization systems that are effective and scalable. In this paper, we present a means to fold amino acid interaction networks. This is a graph whose vertices are the proteins amino acids and whose edges are the interactions between them. Our approach consists in exploiting the parallel between topological and structural properties. Thus, we establish a relation between the sequence and the structure relying on topological criteria. To fold this type of graph, we limit the topological space and we exploit an ant colony approach. We consider those graphs as dynamic graphs so that we can observe gradually the graph properties during the folding process. Motivation: Proteins usually fulfill their biological functions by interacting with other proteins. Although some methods have been developed to predict the binding sites of a monomer protein, these are not sufficient for prediction of the interaction between two monomer proteins. The correct prediction of interface residue pairs from two monomer proteins is still an open question and has great significance for practical experimental applications in the life sciences. We hope to build a method for the prediction of interface residue pairs that is suitable for those applications. Results: Here, we developed a novel deep network architecture called the multi-layered Long-Short Term Memory networks (LSTMs) approach for the prediction of protein interface residue pairs. Firstly, we created three new descriptions and used other six worked characterizations to describe an amino acid, then we employed these features to discriminate between interface residue pairs and non-interface residue pairs. Secondly, we used two thresholds to select residue pairs that are more likely to be interface residue pairs. Furthermore, this step increases the proportion of interface residue pairs and reduces the influence of imbalanced data. Thirdly, we built deep network architectures based on Long-Short Term Memory networks algorithm to organize and refine the prediction of interface residue pairs by employing features mentioned above. We trained the deep networks on dimers in the unbound state in the international Protein-protein Docking Benchmark version 3.0. The updated data sets in the versions 4.0 and 5.0 were used as the validation set and test set respectively. For our best model, the accuracy rate was over 62 when we chose the top 0.2 pairs of every dimer in the test set as predictions, which will be very helpful for the understanding of protein-protein interaction mechanisms and for guidance in biological experiments. We derive a general formula for the lifetime-of wireless sensor networks which holds independently of the underlying network model including network architecture and protocol, data collection initiation, lifetime definition, channel fading characteristics, and energy consumption model. This formula identifies two key parameters at the physical layer that affect the network lifetime: the channel state and the residual energy of sensors. As a result, it provides not only a gauge for performance evaluation of sensor networks but also a guideline for the design of network protocols. Based on this formula, we propose a medium access control protocol that exploits both the channel state information and the residual energy information of individual sensors. Referred to as the max-min approach, this protocol maximizes the minimum residual energy across the network in each data collection. In recent years, there is a growing need for communicating complex data in an accessible graphical form. Existing visualization creation tools support automatic visual encoding, but lack flexibility for creating custom design; on the other hand, freeform illustration tools require manual visual encoding, making the design process time-consuming and error-prone. In this paper, we present Data-Driven Guides (DDG), a technique for designing expressive information graphics in a graphic design environment. Instead of being confined by predefined templates or marks, designers can generate guides from data and use the guides to draw, place and measure custom shapes. We provide guides to encode data using three fundamental visual encoding channels: length, area, and position. Users can combine more than one guide to construct complex visual structures and map these structures to data. When underlying data is changed, we use a deformation technique to transform custom shapes using the guides as the backbone of the shapes. Our evaluation shows that data-driven guides allow users to create expressive and more accurate custom data-driven graphics. In online social networks (OSNs), spam originating from friends and acquaintances not only reduces the joy of Internet surfing but also causes damage to less security-savvy users. Prior countermeasures combat OSN spam from different angles. Due to the diversity of spam, there is hardly any existing method that can independently detect the majority or most of OSN spam. In this paper, we empirically analyze the textual pattern of a large collection of OSN spam. An inspiring finding is that the majority (63.0 ) of the collected spam is generated with underlying templates. We therefore propose extracting templates of spam detected by existing methods and then matching messages against the templates toward accurate and fast spam detection. We implement this insight through Tangram, an OSN spam filtering system that performs online inspection on the stream of user-generated messages. Tangram automatically divides OSN spam into segments and uses the segments to construct templates to filter future spam. Experimental results show that Tangram is highly accurate and can rapidly generate templates to throttle newly emerged campaigns. Specifically, Tangram detects the most prevalent template-based spam with 95.7 true positive rate, whereas the existing template generation approach detects only 32.3 . The integration of Tangram and its auxiliary spam filter achieves an overall accuracy of 85.4 true positive rate and 0.33 false positive rate. We propose a new geometric spanner for static wireless ad hoc networks, which can be constructed efficiently in a localized manner. It integrates the connected dominating set and the local Delaunay graph to form a backbone of the wireless network. Priori arts showed that both structures can be constructed locally with bounded communication costs. This new spanner has these following attractive properties: 1) the backbone is a planar graph, 2) the node degree of the backbone is bounded from above by a positive constant, 3) it is a spanner for both hops and length, 4) it can be constructed locally and is easy to maintain when the nodes move around, and 5) moreover, the communication cost of each node is bounded by a constant. Simulation results are also presented for studying its practical performance. Similarity search is a fundamental problem in social and knowledge networks like GitHub, DBLP, Wikipedia, etc. Existing network similarity measures are limited because they only consider similarity from the perspective of the query node. However, due to the complicated topology of real-world networks, ignoring the preferences of target nodes often results in odd or unintuitive performance. In this work, we propose a dual perspective similarity metric called Forward Backward Similarity (FBS) that efficiently computes topological similarity from the perspective of both the query node and the perspective of candidate nodes. The effectiveness of our method is evaluated by traditional quantitative ranking metrics and large-scale human judgement on four large real world networks. The proposed method matches human preference and outperforms other similarity search algorithms on community overlap and link prediction. Finally, we demonstrate top-5 rankings for five famous researchers on an academic collaboration network to illustrate how our approach captures semantics more intuitively than other approaches. We consider the problem of diffusing information in networks that contain malicious nodes. We assume that each normal node in the network has no knowledge of the network topology other than an upper bound on the number of malicious nodes in its neighborhood. We introduce a topological property known as r-robustness of a graph, and show that this property provides improved bounds on tolerating malicious behavior, in comparison to traditional concepts such as connectivity and minimum degree. We use this topological property to analyze the canonical problems of distributed consensus and broadcasting, and provide sufficient conditions for these operations to succeed. Finally, we provide a construction for r-robust graphs and show that the common preferential-attachment model for scale-free networks produces a robust graph. Distributed constraint optimization (DCOP) problems are a popular way of formulating and solving agent-coordination problems. A DCOP problem is a problem where several agents coordinate their values such that the sum of the resulting constraint costs is minimal. It is often desirable to solve DCOP problems with memory-bounded and asynchronous algorithms. We introduce Branch-and-Bound ADOPT (BnB-ADOPT), a memory-bounded asynchronous DCOP search algorithm that uses the message-passing and communication framework of ADOPT (Modi, Shen, Tambe, & Yokoo, 2005), a well known memory-bounded asynchronous DCOP search algorithm, but changes the search strategy of ADOPT from best-first search to depth-first branch-and-bound search. Our experimental results show that BnB-ADOPT finds cost-minimal solutions up to one order of magnitude faster than ADOPT for a variety of large DCOP problems and is as fast as NCBB, a memory-bounded synchronous DCOP search algorithm, for most of these DCOP problems. Additionally, it is often desirable to find bounded-error solutions for DCOP problems within a reasonable amount of time since finding cost-minimal solutions is NP-hard. The existing bounded-error approximation mechanism allows users only to specify an absolute error bound on the solution cost but a relative error bound is often more intuitive. Thus, we present two new bounded-error approximation mechanisms that allow for relative error bounds and implement them on top of BnB-ADOPT.