26955555
Gene Network: Model, Dynamics and Simulation
A gene network is modeled as a dynamical random graph whose vertices and edges represent genes and gene-gene interactions, respectively. The network grows through three biological mechanisms: (1) gene duplication and loss; (2) gene-gene interaction adding and removing; and (3) genome duplication. The evolutionary dynamics of gene networks is discussed. It is shown that: (1) the vertex degree distribution (i.e., the distribution of the number of the gene-gene interactions per gene) always follows power laws and the power law exponents may be changed by genome duplications; and (2) the network degree distribution (i.e., the distribution of the total number of the gene-gene interactions in the network) has a complex behavior: If no genome duplication occurs, it follows a power law. If a genome duplication occurs, it may be away from the power law state. However, after a sufficient long evolutionary time, it approaches to a power law tail. The dynamics is confirmed by computer simulations. By allowing genome duplications, our model and dynamics (describing the dynamic behavior of gene networks) are more realistic than other previous ones (containing only static behavior).
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.
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.
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.
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.
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.
7031166
Performance evaluation of DCCP: A focus on smoothness and TCP-friendliness
Recent years have seen dramatic increases of the use of multimedia applications on the Internet, which typically either lack congestion control or use proprietary congestion control mechanisms. This can easily cause congestion collapse or compatibility problems. Datagram Congestion Control Protocol (Dccp) fills the gap betweenUdp andTcp, featuring congestion control rather than reliability for packet-switched rich content delivery with high degree of flexibility. We present aDccp model designed and implemented withOpnet Modeler, and the experiments and evaluation focused on largely the smoothness of the data rates, and the fairness between concurrentDccp flows andTcp flows. We foundDccp-ccid3 demonstrates stable data rates under different scenarios, and the fairness betweenDccp andTcp is only achieved under certain conditions. We also validated that the throughput ofDccp-Ccid3 is proportional to the average packet size, and relatively fixed packet size is critical for the optimal operation ofDccp. Problems in the slow start phase and insufficient receiver buffer size were identified and we hereby proposed solutions on this.RésuméLe nombre d’applications multimédias sur l’internet a considérablement augmenté ces dernières années. Ces applications généralement ne gèrent pas les congestions ou bien utilisent des mécanismes de contrôle propriétaires. Il peut en résulter facilement des congestions graves ou des problèmes d’incompatibilité. Le protocoleDccp (Datagram Congestion Control Protocol) se positionne entreUdp etTcp puisqu ’il fournit, pour des paquets multimédias, un contrôle de congestion hautement flexible mais sans la fiabilité de délivrance. Cet article présente un modèleDccp conçu et implémenté avec le simulateurOpnet. Les expérimentations et les analyses portent principalement sur le lissage des débits et l’équité entre des fluxDccp etTcp concurrents. On montre queDccp-Ccid3 affiche des débits stables sous divers scénarios et que l’équité entreDccp etTcp n’est atteinte que sous certaines conditions. On valide également que le débit deDccp-Ccid3 est proportionnel à la taille moyenne des paquets et que le fait d’avoir des paquets de taille relativement constante est un facteur essentiel pour un fonctionnement optimal deDccp. Les problèmes pendant la phase de démarrage lent et ceux dus à une mémoire tampon insuffisante côté récepteur sont également analysés et résolus.
13372241
An XML-based Quality of Service Enabling Language for the Web
In this paper, we introduce an XML-based hierarchical QoS markup language, called HQML, to enhance distributed multimedia applications on the World Wide Web (WWW) with quality of service (QoS) capability. The design ofHQML is based on two observations: (1) the absence of a systematic QoS specification language, that can be used by distributed multimedia applications on the WWW to utilize the state-of-the-art QoS management technology and (2) the power and popularity of XML to deliver richly structured contents over the Web. HQML allows distributed multimedia applications to specify all kinds of application-specific QoS policies and requirements. During runtime, the HQML Executor translates the HQML file into desired data structures and cooperates with the QoS proxies that assist applications in end-to-end QoS negotiation, setup and enforcement. In order to make QoS services tailored toward user preferences and meet the challenges of uncertainty in the distributed heterogeneous environments, the design of HQML is featured as interactive andflexible . In order to allow application developers to create HQML specifications correctly and easily, we have designed and developed a unified visual QoS programming environment, called QoSTalk. In QoSTalk, we adopt a grammatical approach to perform consistency check on the visual QoS specifications and generate HQML files automatically. Finally, we introduce the distributed QoS compiler, which performs the automatic mappings between application- and resource-level QoS parameters to relieve the application developer of the burden of dealing with low-level QoS specifications.
5425849
QoS-assured service composition in managed service overlay networks
Many value-added and content delivery services are being offered via service level agreements (SLAs). These services can be interconnected to form a service overlay network (SON) over the Internet. Service composition in SON has emerged as a cost-effective approach to quickly creating new services. Previous research has addressed the reliability, adaptability, and compatibility issues for composed services. However little has been done to manage generic quality-of-service (QoS) provisioning for composed services, based on the SLA contracts of individual services. In this paper we present QUEST a QoS assUred composEable Service infrasTructure, to address the problem. QUEST framework provides: (1) initial service composition, which can compose a qualified service path under multiple QoS constraints (e.g., response time, availability). If multiple qualified service paths exist, QUEST chooses the best one according to the load balancing metric; and (2) dynamic service composition, which can dynamically recompose the service path to quickly recover from service outages and QoS violations. Different from the previous work, QUEST can simultaneously achieve QoS assurances and good load balancing in SON.
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.
9442879
Dynamic QoS-aware multimedia service configuration in ubiquitous computing environments
Ubiquitous computing promotes the proliferation of various stationary, embedded and mobile devices interconnected by heterogeneous networks. It leads to a highly dynamic distributed system with many devices and services coming and going frequently. Many emerging distributed multimedia applications are being deployed in such a computing environment. In order to make the experience for a user truly seamless and to provide soft performance guarantees, we must meet the following challenges: (1) users should be able to perform tasks continuously, despite changes of resources, devices and locations; (2) users should be able to efficiently utilize all accessible resources within runtime environments to receive the best possible Quality-of-Service (QoS). In this paper, we propose an integrated QoS-aware service configuration model to address the above problems. The configuration model includes two tiers: (1) service composition tier, which is responsible for choosing and composing current available service components appropriately and coordinating arbitrary interactions between them to achieve the user's objectives; and (2) service distribution tier which is responsible for dividing an application into several partitions and distributing them to different available devices appropriately. Our initial experimental results based on both prototype and simulations show the soundness of our model and algorithms.