In past work (Onokpasa, Wild, Wong, DCC 2023), we showed that (a) for joint compression of RNA sequence and structure, stochastic context-free grammars are the best known compressors and (b) that grammars which have better compression ability also show better performance in ab initio structure prediction. Previous grammars were manually curated by human experts. In this work, we develop a framework for automatic and systematic search algorithms for stochastic grammars with better compression (and prediction) ability for RNA. We perform an exhaustive search of small grammars and identify grammars that surpass the performance of human-expert grammars.

In this paper, we use the biological domain knowledge incorporated into stochastic models for ab initio RNA secondary-structure prediction to improve the state of the art in joint compression of RNA sequence and structure data (Liu et al., BMC Bioinformatics, 2008). Moreover, we show that, conversely, compression ratio can serve as a cheap and robust proxy for comparing the prediction quality of different stochastic models, which may help guide the search for better RNA structure prediction models. Our results build on expert stochastic context-free grammar models of RNA secondary structures (Dowell & Eddy, BMC Bioinformatics, 2004; Nebel & Scheid, Theory in Biosciences, 2011) combined with different (static and adaptive) models for rule probabilities and arithmetic coding. We provide a prototype implementation and an extensive empirical evaluation, where we illustrate how grammar features and probability models affect compression ratios.

This paper presents a multi-target metric driven approach to sensor management for Bernoulli filtering, in which at most one target of interest is present. The metric used is the generalised optimal sub pattern assignment (GOSPA) metric. We consider the problem of having an agile sensor operating in a surveillance area, tracking objects as they appear from a target birth distribution. Only one target of interest can exist at any given time-step and its single-target density is Gaussian. In this scenario, we have a grid of sensors that we can select from, one at a time using myopic planning. We evaluate the proposed sensor management algorithm via simulations.

In this paper, we consider the pair-wise semiglobal sequence alignment problem with gaps, which is motivated by the re-sequencing problem that requires to assemble short reads sequences into a genome sequence by referring to a reference sequence. The problem has been studied before for single gap and bounded number of gaps. For single gap, there is a GPU-based algorithm proposed (Barton et al., 2015). In our work, we propose a GPU-based algorithm for the bounded number of gaps case, called GPUGapsMis. We implement the algorithm and compare the performance with the CPU-based algorithm, called CPUGapsMis. The algorithm has two distinct stages: the alignment phase, and the backtrack phase. We investigate several different approaches, in order to determine the most favorable for this problem, by means of a Hybrid model or a wholly-GPU based model, as well as the alignment of single text sequences or multiple text sequences on the GPU at a time. We show that the alignment phase of the algorithm is a good candidate for parallelization, with peak speedup of 11 times. We show that although the backtracking phase is sequential, it is more beneficial to perform it on the GPU, as opposed to returning to the CPU and performing there. When performing both phases on the GPU, GPUGapsMis achieves a peak speedup of 10.4 times against CPUGapsMis. Our data parallel GPU algorithm achieves results which are an improvement on those of an existing GPU data parallel implementation (Ojiaku, 2014).

Millimeter wave (mmWave) communication not only provides ultra-high speed radio access but is also ideally suited for efficient and flexible wireless backhauling. Specifically for dense deployments, a mmWave macro base station (MBS) that serves a large number of mmWave micro base stations (μBSs) is much more cost effective than legacy cellular architectures which connect μBSs to the core network through fibers. In addition, μBSs can cooperate with each other by acting as relay nodes. The directional nature of mmWave communication allows for spatial reuse, even in the presence of interference, which can be exploited to optimize mmWave wireless backhaul performance. The optimization opportunistically prioritizes the use of good connections at the MBS and further leverages compact and concurrent transmissions between μBS. Relays and directional antennas speed up communication, but increase the complexity of the scheduling problem. In this work, we study the mmWave backhaul scheduling problem and derive an MILP formulation for it as well as upper and lower bounds. We prove that the problem is NP-hard and can be approximated, but only if interference is negligible. By means of numerical simulations, we compare theoretical results with heuristics in small system sizes. Results validate the analysis and demonstrate the high performance of our heuristics in realistic cellular settings.

We study the problem of scheduling n similar jobs on m machines, with respect to the fact that jobs are dependent and some of them must be performed before others. Dependencies between jobs are modeled as a partial order relation. Machines are prone to crashes, induced by an Adaptive f-Bounded adversary who can fail up to f machines, where . Communication takes place via a Multiple-Access Channel (MAC), which restricts simultaneous transmissions. We show an optimal solution (with respect to total work of all machines) for partially ordered sets of jobs forming chains and an algorithm and lower bound for trees.

It is crucial to ensure reliability, security and stability of cloud services without sacrificing too much resources in the area of workload management in clouds. The paper evaluates and compares lightweight decentralized algorithms for scheduling a workload part of which could be unreliable, in the context of {\em heterogeneous} cloud data centers. This unreliability could be caused by various types of failures or attacks. The framework for robust workload scheduling efficiently combines classic fault tolerant and security tools, such as packet/job scanning, with workload scheduling, and it does not use any heavy resource consuming tools, e.g., cryptography or non-linear optimization. More specifically, the framework uses a novel objective function to allocate jobs to servers and constantly decides which job to scan based on a formula associated with the objective function. In previous work it was shown how to set up the objective function and the corresponding scanning procedure of the {\em central job scheduler} to make the system provably stable, provided a specific capacity condition is satisfied. As a result, it was shown that the framework assures cloud stability even though naive scanning-all and scanning-none strategies are not stable for both centralized and decentralized scheduling in {\em homogeneous} data centers. In this work we extend the work to {\em heterogeneous} data centers, for which we show that decentralized algorithms based on Join Shortest Queue and Join Shortest Work policies are {\em stable} for every workload within the system capacity, while the algorithms based on popular Power of Two Choices, Round Robin and Uniform Random policies are {\em not stable} for a substantial amount of workloads even within the system capacity.

Climate change is a major threat to species, unless their populations are able to invade and colonise new landscapes of more suitable environment. In this paper, we propose a new model of the invasion process using a tool of landscape network sparsification to efficiently estimate a duration of the process. More specifically, we aim to simplify the structure of large landscapes using the concept of sparsification in order to substantially decrease the time required to compute a good estimate of the invasion time in these landscapes. For this purpose, two different simulation methods have been compared: full and R-local simulations, which are based on the concept of dense and sparse networks, respectively. These two methods are applied to real heterogeneous landscapes in the United Kingdom to compute the total estimated time to invade landscapes. We examine how the duration of the invasion process is affected by different factors, such as dispersal coefficient, landscape quality and landscape size. Extensive evaluations have been carried out, showing that the R-local method approximates the duration of the invasion process to high accuracy using a substantially reduced computation time.

We study a scheduling problem arising in demand response management in smart grid. Consumers send in power requests with a flexible feasible time interval during which their requests can be served. The grid controller, upon receiving power requests, schedules each request within the specified interval. The electricity cost is measured by a convex function of the load in each timeslot. The objective is to schedule all requests with the minimum total electricity cost. Previous work has studied cases where jobs have unit power requirement and unit duration. We extend the study to arbitrary power requirement and duration, which has been shown to be NP-hard. We give the first online algorithm for the general problem, and prove that the worst case competitive ratio is asymptotically optimal. We also prove that the problem is fixed parameter tractable. Due to space limit, the missing proofs are presented in the full paper.

In this paper we consider the pair-wise sequence alignment problem with gaps, which is motivated by the re-sequencing problem that requires to assemble short reads sequences into a genome sequence by referring to a reference sequence. The problem has been studied before for single gap and bounded number of gaps. For single gap, there was a GPU-based algorithm proposed. In our work we propose a GPU-based algorithm for the bounded number of gaps case. We implemented the algorithm and compare the performance with the CPU-based algorithm in a multithreadded environment, the results are promising with the GPU version achieving a speedup of 30 times.

We consider the following fundamental scheduling problem in which the input consists of n jobs to be scheduled on a set of identical machines of bounded capacity g (which is the maximal number of jobs that can be processed simultaneously by a single machine). Each job is associated with a start time and a completion time, it is supposed to be processed from the start time to the completion time (and in one of our extensions it has to be scheduled also in a continuous number of days, this corresponds to a two-dimensional version of the problem). We consider two versions of the problem. In the scheduling minimization version the goal is to minimize the total busy time of machines used to schedule all jobs. In the resource allocation maximization version the goal is to maximize the number of jobs that are scheduled for processing under a budget constraint given in terms of busy time. This is the first study of the maximization version of the problem. The minimization problem is known to be NP-Hard, thus the maximization problem is also NP-Hard. We consider various special cases, identify cases where an optimal solution can be computed in polynomial time, and mainly provide constant factor approximation algorithms for both minimization and maximization problems. Some of our results improve upon the best known results for this job scheduling problem. Our study has applications in power consumption, cloud computing and optimizing switching cost of optical networks.

This article extends the study of online algorithms for energy-efficient deadline scheduling to the overloaded setting. Specifically, we consider a processor that can vary its speed between 0 and a maximum speed T to minimize its energy usage (the rate is believed to be a cubic function of the speed). As the speed is upper bounded, the processor may be overloaded with jobs and no scheduling algorithms can guarantee to meet the deadlines of all jobs. An optimal schedule is expected to maximize the throughput, and furthermore, its energy usage should be the smallest among all schedules that achieve the maximum throughput. In designing a scheduling algorithm, one has to face the dilemma of selecting more jobs and being conservative in energy usage. If we ignore energy usage, the best possible online algorithm is 4-competitive on throughput [Koren and Shasha 1995]. On the other hand, existing work on energy-efficient scheduling focuses on a setting where the processor speed is unbounded and the concern is on minimizing the energy to complete all jobs; O (1)-competitive online algorithms with respect to energy usage have been known [Yao et al. 1995; Bansal et al. 2007a; Li et al. 2006]. This article presents the first online algorithm for the more realistic setting where processor speed is bounded and the system may be overloaded; the algorithm is O (1)-competitive on both throughput and energy usage. If the maximum speed of the online scheduler is relaxed slightly to (1+ϵ) T for some ϵ > 0, we can improve the competitive ratio on throughput to arbitrarily close to one, while maintaining O (1)-competitiveness on energy usage.

Energy usage has been an important concern in recent research on online scheduling. In this paper we extend the study of the tradeoff between flow time and energy from the single-processor setting [8, 6] to the multi-processor setting. Our main result is an analysis of a simple non-migratory online algorithm called CRR (classified round robin) on m ≥ 2 processors, showing that its flow time plus energy is within O(1) times of the optimal non-migratory offline algorithm, when the maximum allowable speed is slightly relaxed. This result still holds even if the comparison is made against the optimal migratory offline algorithm (the competitive ratio increases by a factor of 2.5). As a special case, our work also contributes to the traditional online flow-time scheduling. Specifically, for minimizing flow time only, CRR can yield a competitive ratio one or even arbitrarily smaller than one, when using sufficiently faster processors. Prior to our work, similar result is only known for online algorithms that needs migration [21, 23], while the best non-migratory result can achieve an O(1) competitive ratio [14].

Energy usage has been an important concern in recent research on online job scheduling, where processors are allowed to vary the speed dynamically so as to save energy whenever possible. Notice that providing good quality of service such as response time (flow time) and conserving energy are conflicting objectives. An interesting problem for scheduling is how to optimize an economic tradeoff of flow time and energy. To this end, the past two years have witnessed significant progress in the single-processor setting, and online algorithms with performance close to optimal have been obtained. In this paper we extend the study of optimizing the tradeoff between flow time and energy to the multi-processor setting. We derive and analyze a simple non-migratory online algorithm that makes use of the classified-round-robin (CRR) strategy to dispatch jobs. Even in the worst case, its performance is within O(log P) times of the optimal migratory offline algorithm, where P is the ratio of the maximum job size to the minimum job size. Technically speaking, this online result stems from a non-trivial solution to an offline problem of eliminating migration, which is also interesting by itself.

The DNA microarray technology, originally developed to measure the level of gene expression, had become one of the most widely used tools in genomic study. Microarrays have been proved to benefit areas including gene discovery, disease diagnosis, and multi-virus discovery. The crux of microarray design lies in how to select a unique probe that distinguishes a given genomic sequence from other sequences. However, in cases that the existence of a unique probe is unlikely, e.g., in the context of a large family of closely homologous genes, the use of a limited number of non-unique probes is still desirable.qyy Due to its significance, probe selection attracts a lot of attention. Various probe selection algorithms have been developed in recent years. Good probe selection algorithms should produce as small number of candidate probes as possible. Efficiency is also crucial because the data involved is usually huge. Most existing algorithms usually select probes by filtering, which is usually not selective enough and quite a large number of probes are returned. We propose a new direction to tackle the problem and give an efficient algorithm to select (randomly) a small set of probes and demonstrate that such a small set of probes is sufficient to distinguish each sequence from all the other sequences. Based on the algorithm, we have developed a probe selection software RANDPS, which runs efficiently and effectively in practice. A number of experiments have been carried out and the results will be discussed.

MOTIVATION: For the purpose of locating conserved genes in a whole genome scale, this paper proposes a new structural optimization problem called the Mutated Subsequence Problem, which gives consideration to possible mutations between two species (in the form of reversals and transpositions) when comparing the genomes. RESULTS: A practical algorithm called mutated subsequence algorithm (MSS) is devised to solve this optimization problem, and it has been evaluated using different pairs of human and mouse chromosomes, and different pairs of virus genomes of Baculoviridae. MSS is found to be effective and efficient; in particular, MSS can reveal >90% of the conserved genes of human and mouse that have been reported in the literature. When compared with existing softwares MUMmer and MaxMinCluster, MSS uncovers 14 and 7% more genes on average, respectively. Furthermore, this paper shows a hybrid approach to integrate MUMmer or MaxMinCluster with MSS, which has better performance and reliability.

MOTIVATION: Short interfering RNAs (siRNAs) can be used to suppress gene expression and possess many potential applications in therapy, but how to design an effective siRNA is still not clear. Based on the MPI (Max-Planck-Institute) basic principles, a number of siRNA design tools have been developed recently. The set of candidates reported by these tools is usually large and often contains ineffective siRNAs. In view of this, we initiate the study of filtering ineffective siRNAs. RESULTS: The contribution of this paper is 2-fold. First, we propose a fair scheme to compare existing design tools based on real data in the literature. Second, we attempt to improve the MPI principles and existing tools by an algorithm that can filter ineffective siRNAs. The algorithm is based on some new observations on the secondary structure, which we have verified by AI techniques (decision trees and support vector machines). We have tested our algorithm together with the MPI principles and the existing tools. The results show that our filtering algorithm is effective. AVAILABILITY: The siRNA design software tool can be found in the website http://www.cs.hku.hk/~sirna/ CONTACT: [email protected]

This paper proposes a new approach for solving the whole genome alignment problem. Our approach is based on a new structural optimization problem (called the MUM selection problem) related to mutations via reversals and transpositions. We have devised a practical algorithm for this optimization problem and have evaluated the algorithm using 15 pairs of human and mouse chromosomes. The results show that our algorithm is both effective and efficient. More specifically, our algorithm can reveal 91% of the conserved gene pairs that have been reported in the literature. When compared to existing software MUMmer and MaxMinCluster , our algorithm uncovers 15% and 7% more genes on average, respectively. The sensitivity of our algorithm is also slightly higher. The paper concludes with a remark on the computational hardness of the MUM selection problem.

MOTIVATION: This paper is concerned with algorithms for aligning two whole genomes so as to identify regions that possibly contain conserved genes. Motivated by existing heuristic-based software tools, we initiate the study of an optimization problem that attempts to uncover conserved genes with a global concern. Another interesting feature in our formulation is the tolerance of noise, which also complicates the optimization problem. A brute-force approach takes time exponential in the noise level. RESULTS: We show how an insight into the optimization structure can lead to a drastic improvement in the time and space requirement [precisely, to O(k2n2) and O(k2n), respectively, where n is the size of the input and k is the noise level]. The reduced space requirement allows us to implement the new algorithm, called MaxMinCluster, on a PC. It is exciting to see that when tested with different real data sets, MaxMinCluster consistently uncovers a high percentage of conserved genes that have been published by GenBank. Its performance is indeed favorably compared to MUMmer (perhaps the most popular software tool for uncovering conserved genes in a whole-genome scale). AVAILABILITY: The source code is available from the website http://www.csis.hku.hk/~colly/maxmincluster/ detailed proof of the propositions can also be found there.

In this paper we consider the notion of relative competitive analysis, which is a simple generalization of the conventional competitive analysis and extra-resource analysis for on-line algorithms. We apply this analysis to study on-line schedulers for stream merging in two different video-on-demand (VOD) systems, which are based on two common approaches, namely, piggybacking and skimming. Our new analysis, in its simplest form, reveals a 3-competitive algorithm for stream merging based on skimming as well as piggybacking. This improves all previous results [4, 8]. We also show how to obtain guarantee on the performance improvement based on adding extra resources, and more interestingly, we provide a unified methodology to compare piggybacking and skimming. We believe that our result gives a clue to system designers for choosing desirable configurations.

This paper is concerned with an on-line scheduling problem arising from video-on-demand (VOD) systems that support stream merging. Most previous work on this problem focuses on empirical results; Bar-Noy and Ladner [3] are the first to consider worst-case performance and give an on-line algorithm with competitive ratio bounded by ,w here , is the number of requests, and is the guaranteed startup delay measured as a fraction of the time for a full stream. In this paper we give a new on-line algorithm that improves the competitive ratio to a constant (precisely, 5). Our result implies that the performance does not deteriorate in dealing with a large number of requests and a small startup delay.