37050852
Algorithms for Multiple Genome Rearrangement by Signed Reversals
We discuss a multiple genome rearrangement problem by signed reversals: Given a collection of genomes, we generate them in the minimum number of signed reversals. It is NP-hard and equivalent to finding an optimal Steiner tree to connect the genomes by reversal paths. We design two algorithms to find the optimal Steiner nodes of the problem: Neighbor-perturbing algorithm and branch-and-bound algorithm. The first one is a polynomial running time approximation algorithm. It searches for the optimal Steiner nodes by perturbing initial Steiner nodes nearby their neighborhoods and improving them better and better until convergence. The second one is an exact exponential running time algorithm for a median problem. It finds the optimal Steiner node by checking all candidates that satisfy the necessary conditions for optimal Steiner nodes. We implement the algorithms into two programs respectively and show by experimental examples that they are more efficient than other similar ones, such as GRAPPA, BPAnalysis, and MGR, etc.
6538618
A Greedy Algorithm for Optimal Recombination
Let Σ be an alphabet and Σn denote the collection of all sequences of length n over Σ. For any s1 = ajaj+1 . . . an+s2 = b1b2 . . . bj bj+1 . . . bn ∈ Σn, a recombination of s1 and s2 at position j is defined as an operation that crosses s1 and s2 at position j and generates t1 = a1a2 . . . ajbj+1 . . . bn and t2 = b1b2 . . . bjaj+1 . . . an. Denote A and S two collections of sequences. In this paper, we discuss generating A from S by a series of recombinations in minimum number of steps. We present a greedy algorithm for finding the optimal recombination evolutionary history from S to any tree A of sequences when |S| = 2.
42811809
Functional Divergence in TGF-b Signaling Pathway
2872276
Multiple Genome Rearrangement by Reversals
In this paper, we discuss a multiple genome rearrangement problem: Given a collection of genomes represented by permutations, we generate the collection from some fixed genome, e.g., the identity permutation, in a minimum number of signed reversals. It is NP-hard, so efficient heuristics is important for finding its optimal solution. We at first discuss how to generate two and three genomes from a fixed genome by polynomial algorithms for some special cases. Then based on the polynomial algorithms, we obtain some approximation algorithms for generating two and three genomes in general, respectively. Finally, we apply these approximation algorithms to design a new approximation algorithm for generating more genomes. We also show by some experimental examples that the algorithms are efficient.
13169629
Mathematical Modeling for Functional Divergence after Gene Duplication
In this paper, I present a statistical framework for modeling the functional divergence after gene duplication. A rate-component model to describe the rate covariation among homologous genes of a gene family is implemented when a phylogenetic tree is known. The Markov chain model is rigorous but may require a huge amount of computational time when the number of sequences is large. On the other hand, the Poisson-based model is mathematically analytical so that computation is very fast even for a large dataset. Moreover, under the posterior framework, we have developed a site-specific profile for predicting important amino acid residues responsible for these functional differences between member genes of a gene family. Our study may have great potential for functional genomics because it is cost-effective, and these predictions can be further tested by biological experimentation.
1939855
DIVERGE: phylogeny-based analysis for functional-structural divergence of a protein family
SUMMARY
DetectIng Variability in Evolutionary Rates among GEnes (DIVERGE) is a software system to study functional divergence of a protein family by detecting site-specific change in evolutionary rate using a multiple alignment of amino acid sequences for a given phylogenetic tree. The program first conducts a statistical test for site-specific rate shifts along the tree, and predicting candidate amino acid residues responsible for functional divergence based on posterior analysis. These results can then be mapped on the 3D protein structure if available.


AVAILABILITY
DIVERGE is available free of charge from http://xgu1.zool.iastate.edu/. Distribution packages for both Linux and Microsoft Windows operating systems are available, including manual and example files.
16522842
Computational methodologies for modelling, analysis and simulation of signalling networks
This article is a critical review of computational techniques used to model, analyse and simulate signalling networks. We propose a conceptual framework, and discuss the role of signalling networks in three major areas: signal transduction, cellular rhythms and cell-to-cell communication. In order to avoid an overly abstract and general discussion, we focus on three case studies in the areas of receptor signalling and kinase cascades, cell-cycle regulation and wound healing. We report on a variety of modelling techniques and associated tools, in addition to the traditional approach based on ordinary differential equations (ODEs), which provide a range of descriptive and analytical powers. As the field matures, we expect a wider uptake of these alternative approaches for several reasons, including the need to take into account low protein copy numbers and noise and the great complexity of cellular organisation. An advantage offered by many of these alternative techniques, which have their origins in computing science, is the ability to perform sophisticated model analysis which can better relate predicted behaviour and observations.
2093792
Visual QoS programming environment for ubiquitous multimedia services
The provision of distributed multimedia services is becoming mobile and ubiquitous. Different multimedia services require application-specific Quality of Service (QoS). In this paper, we present QoSTalk, a unified component-based programming environment that allows application developers to specify different application-specific QoS requirements easily. In QoSTalk, we adopt a hierarchical approach to model application configuration graphs for different distributed multimedia services. We design and implement the XML-based Hierarchical QoS Markup Language, called HQML, to describe the hierarchical configuration graph as well as other application-specific QoS requirements and policies. QoSTalk promotes the separation of concerns in developing QoS-aware ubiquitous multimedia applications and thus enables easy programming of QoS-aware applications, running on top of a unified QoS-aware middleware framework. We have prototyped the QoSTalk in Java and CORBA. Our case studies with several multimedia applications show that QoSTalk effectively fills the gap for application developers between the very general facilities provided by the QoS-aware middleware and different kinds of distributed multimedia applications.
6028890
On Composing Stream Applications in Peer-to-Peer Environments
Stream processing has become increasingly important as many emerging applications call for continuous real-time processing over data streams, such as voice-over-IP telephony, security surveillance, and sensor data analysis. In this paper, we propose a composable stream processing system for cooperative peer-to-peer environments. The system can dynamically select and compose stream processing elements located on different peers into user desired applications. We investigate multiple alternative approaches to composing stream applications: 1) global-state-based centralized versus local-state-based distributed algorithms for initially composing stream applications at setup phase. The centralized algorithm performs periodical global state maintenance while the distributed algorithm performs on-demand state collection. 2) Reactive versus proactive failure recovery schemes for maintaining composed stream applications during runtime. The reactive failure recovery algorithm dynamically recomposes a new stream application upon failures while the proactive approach maintains a number of backup compositions for failure recovery. We conduct both theoretical analysis and experimental evaluations to study the properties of different approaches. Our study illustrates the performance and overhead trade-offs among different design alternatives, which can provide important guidance for selecting proper algorithms to compose stream applications in cooperative peer-to-peer environments
805562
Synergy: Sharing-Aware Component Composition for Distributed Stream Processing Systems
Many emerging on-line data analysis applications require applying continuous query operations such as correlation, aggregation, and filtering to data streams in real-time. Distributed stream processing systems allow in-network stream processing to achieve better scalability and quality-of-service (QoS) provision. In this paper we present Synergy, a distributed stream processing middleware that provides sharing-aware component composition. Synergy enables efficient reuse of both data streams and processing components, while composing distributed stream processing applications with QoS demands. Synergy provides a set of fully distributed algorithms to discover and evaluate the reusability of available data streams and processing components when instantiating new stream applications. For QoS provision, Synergy performs QoS impact projection to examine whether the shared processing can cause QoS violations on currently running applications. We have implemented a prototype of the Synergy middleware and evaluated its performance on both PlanetLab and simulation testbeds. The experimental results show that Synergy can achieve much better resource utilization and QoS provision than previously proposed schemes, by judiciously sharing streams and processing components during application composition.
6987147
Optimal Component Composition for Scalable Stream Processing
Stream processing has become increasingly important with emergence of stream applications such as audio/video surveillance, stock price tracing, and sensor data analysis. A challenging problem is to provide optimal component composition in a distributed stream processing environment. The goal of optimal component composition is to achieve load balancing subject to multiple function, resource, and quality-of-service (QoS) constraints while composing stream applications. In this paper, we present an adaptive composition probing (ACP) approach to the problem. Different from previous work, ACP provides a new hybrid approach that combines distributed composition probing with coarse-grain global state management. Guided by the coarse-grain global state information, ACP selectively probes a subset of candidate components to discover an approximately optimal component composition. Further, ACP is self-tuning, which can adoptively adjust the number of probes to maintain a specified composition performance target (i.e., composition success rate) in a dynamic stream environment. While the optimal component composition problem is NP-hard, our ACP approach provides an adaptive polynomial approximation solution. We have conducted extensive simulation experiments to show the efficiency, scalability, and adaptability of the ACP approach by comparing with other alternative solutions