BACKGROUND: Reconstructing ancestral genomes is one of the central problems presented in genome rearrangement analysis since finding the most likely true ancestor is of significant importance in phylogenetic reconstruction. Large scale genome rearrangements can provide essential insights into evolutionary processes. However, when the genomes are large and distant, classical median solvers have failed to adequately address these challenges due to the exponential increase of the search space. Consequently, solving ancestral genome inference problems constitutes a task of paramount importance that continues to challenge the current methods used in this area, whose difficulty is further increased by the ongoing rapid accumulation of whole-genome data. RESULTS: In response to these challenges, we provide two contributions for ancestral genome inference. First, an improved discrete quantum-behaved particle swarm optimization algorithm (IDQPSO) by averaging two of the fitness values is proposed to address the discrete search space. Second, we incorporate DCJ sorting into the IDQPSO (IDQPSO-Median). In comparison with the other methods, when the genomes are large and distant, IDQPSO-Median has the lowest median score, the highest adjacency accuracy, and the closest distance to the true ancestor. In addition, we have integrated our IDQPSO-Median approach with the GRAPPA framework. Our experiments show that this new phylogenetic method is very accurate and effective by using IDQPSO-Median. CONCLUSIONS: Our experimental results demonstrate the advantages of IDQPSO-Median approach over the other methods when the genomes are large and distant. When our experimental results are evaluated in a comprehensive manner, it is clear that the IDQPSO-Median approach we propose achieves better scalability compared to existing algorithms. Moreover, our experimental results by using simulated and real datasets confirm that the IDQPSO-Median, when integrated with the GRAPPA framework, outperforms other heuristics in terms of accuracy, while also continuing to infer phylogenies that were equivalent or close to the true trees within 5 days of computation, which is far beyond the difficulty level that can be handled by GRAPPA.

Cancer is known for its heterogeneity and is regarded as an evolutionary process driven by somatic mutations and clonal expansions. This evolutionary process can be modeled by a phylogenetic tree and phylogenetic analysis of multiple subclones of cancer cells can facilitate the study of the tumor variants progression. Copy-number aberration occurs frequently in many types of tumors in terms of segmental amplifications and deletions. In this paper, we developed a distance-based method for reconstructing phylogenies from copy-number profiles of cancer cells. We demonstrate the importance of distance correction from the edit (minimum) distance to the estimated actual number of events. Experimental results show that our approaches provide accurate and scalable results in estimating the actual number of evolutionary events between copy number profiles and in reconstructing phylogenies.

Heterogeneity prevails not only among physical machines but also among workloads in real IaaS Cloud data centers (CDCs). The heterogeneity makes performance modeling of large and complex IaaS CDCs even more challenging. This paper considers the scenario where the number of virtual CPUs requested by each customer job may be different. We propose a hierarchical stochastic modeling approach applicable to IaaS CDC performance analysis under such a heterogeneous workload. Numerical results obtained from the proposed analytic model are verified through discrete-event simulations under various system parameter settings.

This paper presents a performability model for RAID storage systems using Markov regenerative process to compare different RAID architectures. While homogeneous Markov models are extensively used for reliability analysis of RAID storage systems, the memory-less property of the sojourn time assumed in such models is not satisfied in reality, especially in disk rebuild process whose progress is not interrupted even at an event of another disk failure. In this paper, we use Markov regenerative process which allows us to model the generally distributed rebuild times providing a needed extension of the traditional Markov models. The Markov regenerative process is then used to assess the performability of the storage system by assigning reward rates to each state based on the real storage benchmark results. Our numerical study characterizes the performability advantage of RAID6 architecture over RAID10 architecture in terms of sequential read access. Our findings include that the effect of exponential assumption for the rebuild times has practically negligible effect when we focus on data availability. However, the effect this approximation on performability prediction may not be negligible especially when the performance level drastically changes in degraded states. Our MRGP model provides more accurate prediction of performability in such cases.

When combining several services into a composite service, it is non-trivial to determine, prior to service deployment, performance and reliability values of the composite service. Moreover, once the service is deployed, it is often the case that during operation it fails to meet its service-level agreement (SLA) and one needs to detect what has gone wrong (i.e., performance/reliability bottlenecks). To study these issues, we develop a Semi-Markov Process (SMP) formulation of composite services with failures and restarts. By explicitly including failure states into the SMP representation of a service, we can compute both its performance and reliability using a single SMP. We can also detect its performance and reliability bottlenecks by applying the formal sensitivity analysis technique. We demonstrate our approach by choosing a representative example that is validated using experiments on real Web services.

Explosive growth of data generation and increasing reliance of business analysis on massive data make data loss more damaging than ever before. Thus it has also become a critical issue for businesses to protect important data effectively. In a system with multiple data sets, complex system configurations and data protection requirements, backup planning plays an important role for maintaining the desired level of data protection while minimizing the impact on system operation. In this paper we investigate the use of Markov Decision Process (MDP) to guide the planning of data backup operations. To improve the applicability of the MDP framework to large systems, we present a novel approximation method to enhance its scalability. The benefit of the framework is demonstrated through numerical examples, where our MDP method reduces the storage system downtime by over 50% compared to the best heuristic approach.

The explosive growth of data generation and increasing reliance of business analysis on massive data make data loss more damaging than ever before. Nowadays many organizations start relying on cloud services for keeping their valuable data. It is a critical issue for cloud service provider to protect the data for individual users securely and effectively. To protect the data in a system with multiple data sources, backup schedule plays an important role for achieving the desired level of data protection while minimizing the impact on system operation. In this paper we investigate the use of Markov Decision Process (MDP) to guide the scheduling of data backup operation and propose a framework to automatically generate an MDP instance from system specifications and data protection requirements. We then demonstrate the benefits of the MDP approach.

In modern IT systems, data backup and restore operations are essential for providing protection against data loss from both natural and man-made incidents. On the other hand, data backup and restore operations can be resource-intensive and lead to performance degradation, or may require the system to be offline entirely. Therefore, it is important to properly choose backup and restore techniques and policies to ensure adequate data protection while minimizing the impact on system availability and performance. In this paper, we present an analytical modeling approach for such a purpose. We study a file service system that undergoes periodic data backups, and investigate metrics concerning system availability, data loss and rejection of user requests. To obtain the metrics, we combine a variety of model types, including Markov chains, queuing networks and Stochastic Reward Nets, to construct a set of analytical models that capture the operational details of the system. We then compute the metrics of interest under different backup/restore techniques, policies, and workload scenarios. The numerical results allow us to compare the effects of different backup/restore techniques and policies in terms of the tradeoff between protective power and impact on system performance and availability.

From an enterprise perspective, one key motivation to transform the traditional IT management into Cloud is the cost reduction of the hosted services. In an Infrastructure-as-a-Service (IaaS) Cloud, virtual machine (VM) instances share the physical machines (PMs) in the provider's data center. With large number of PMs, providers can maintain low cost of service downtime at the expense of higher infrastructure and other operational costs (e.g., power consumption and cooling costs). Hence, determining the optimal PM capacity requirements that minimize the overall cost is of interest. In this paper, we show how a cost analysis and optimization framework can be developed using stochastic availability and performance models of an IaaS Cloud. Specifically, we study two cost minimization problems to address the capacity planning in an IaaS Cloud: (1) what is the optimal number of PMs that minimizes the total cost of ownership for a given downtime requirement set by service level agreements? and, (2) is it more economical to use cheaper but less reliable PMs or to use costlier but more reliable PMs for insuring the same availability characteristics? We use simulated annealing, a well-known stochastic search algorithm, to solve these optimization problems. Results from our analysis show that the optimal solutions are found within reasonable time.