Search

Background: Multiple sequence alignment is fundamental. Exponential growth in computation time appears to be inevitable when an optimal alignment is required for many sequences. Exact costs of optimum alignments are therefore rarely computed. Consequently much effort has been invested in algorithms for alignment that are heuristic, or explore a restricted class of solutions. These give an upper bound on the alignment cost, but it is equally important to determine the quality of the solution obtained. In the absence of an optimal alignment with which to compare, lower bounds may be calculated to assess the quality of the alignment. As more effort is invested in improving upper bounds (alignment algorithms), it is therefore important to improve lower bounds as well. Although numerous cost metrics can be used to determine the quality of an alignment, many are based on sum-of-pairs (SP) measures and their generalizations., Results: Two standard and two new methods are considered for using exact 2-way and 3-way alignments to compute lower bounds on total SP alignment cost; one new method fares well with respect to accuracy, while the other reduces the computation time. The first employs exhaustive computation of exact 3-way alignments, while the second employs an efficient heuristic to compute a much smaller number of exact 3-way alignments. Calculating all 3-way alignments exactly and computing their average improves lower bounds on sum of SP cost in v-way alignments. However judicious selection of a subset of all 3-way alignments can yield a further improvement with minimal additional effort. On the other hand, a simple heuristic to select a random subset of 3-way alignments (a random packing) yields accuracy comparable to averaging all 3-way alignments with substantially less computational effort., Conclusion: Calculation of lower bounds on SP cost (and thus the quality of an alignment) can be improved by employing a mixture of 3-way and 2-way alignments.

Motivation: Oligo arrays are important experimental tools for the high throughput measurement of gene expression levels. During production of oligo arrays, it is important to identify any faulty manufacturing step., Results: We describe a practical algorithm for the construction of optimal quality control designs that identify any faulty manufacturing step. The algorithm uses hillclimbing, a search technique from combinatorial optimization. We also present the results of using this algorithm on all practical quality control design sizes., Availability: On request from the authors.

Alternative design and analysis methods for screening experiments based on locating arrays are presented. The number of runs in a locating array grows logarithmically based on the number of factors, providing efficient methods for screening complex engineered systems, especially those with large numbers of categorical factors having different numbers of levels. Our analysis method focuses on levels of factors in the identification of important main effects and two-way interactions. We demonstrate the validity of our design and analysis methods on both well-studied and synthetic data sets and investigate both statistical and combinatorial properties of locating arrays that appear to be related to their screening capability. [ABSTRACT FROM AUTHOR]

Modern software systems often consist of many different components, each with a number of options. Although unit tests may reveal faulty options for individual components, functionally correct components may interact in unforeseen ways to cause a fault. Covering arrays are used to test for interactions among components systematically. A two‐stage framework, providing a number of concrete algorithms, is developed for the efficient construction of covering arrays. In the first stage, a time and memory efficient randomized algorithm covers most of the interactions. In the second stage, a more sophisticated search covers the remainder in relatively few tests. In this way, the storage limitations of the sophisticated search algorithms are avoided; hence, the range of the number of components for which the algorithm can be applied is extended, without increasing the number of tests. Many of the framework instantiations can be tuned to optimize a memory‐quality trade‐off, so that fewer tests can be achieved using more memory. [ABSTRACT FROM AUTHOR]

A new algebraic system, test algebra ($\mathsf{TA}$), is proposed for identifying faults in combinatorial testing for software-as-a-service (SaaS) applications. In the context of cloud computing, SaaS is a new software delivery model, in which mission-critical applications are composed, deployed, and executed on cloud platforms. Testing SaaS applications is challenging because new applications need to be tested once they are composed, and prior to their deployment. A composition of components providing services yields a configuration providing an SaaS application. While individual components in the configuration may have been thoroughly tested, faults still arise due to interactions among the components composed, making the configuration faulty. When there are $k$ components, combinatorial testing algorithms can be used to identify faulty interactions with $t$ or fewer components, for some threshold $2 \leq t \leq k$ on the size of interactions considered. In general, these methods do not identify specific faults, but rather indicate the presence or absence of some faults. To identify specific faults, an adaptive testing regime repeatedly constructs and tests configurations in order to determine, for each interaction of interest, whether it is faulty or not. In order to perform such testing in a loosely coupled distributed environment such as the cloud, it is imperative that testing results can be combined from many different servers. The $\mathsf{TA}$ defines rules to permit results to be combined, and to identify the faulty interactions. Using the $\mathsf{TA}$ , configurations can be tested concurrently on different servers and in any order. The $\mathsf{TA}$ always keeps the high reduction rate of potential faulty configurations in fault location analysis. [ABSTRACT FROM AUTHOR]

Covering perfect hash families represent certain covering arrays compactly. Applying two probabilistic methods to covering perfect hash families improves upon the asymptotic upper bound for the minimum number of rows in a covering array with v symbols, k columns, and strength t. One bound can be realized by a randomized polynomial time construction algorithm using column resampling, while the other can be met by a deterministic polynomial time conditional expectation algorithm. Computational results are developed for both techniques. Further, a random extension algorithm further improves on the best known sizes for covering arrays in practice. An extensive set of computations with column resampling and random extension yields explicit constructions when k≤75 for strength seven, k≤200 for strength six, k≤600 for strength five, and k≤2500 for strength four. When v>3, almost all known explicit constructions are improved upon. For strength t=3, restrictions on the covering perfect hash family ensure the presence of redundant rows in the covering array, which can be removed. Using restrictions and random extension, computations for t=3 and k≤10,000 again improve upon known explicit constructions in the majority of cases. Computations for strengths three and four demonstrate that a conditional expectation algorithm can produce further improvements at the expense of a larger time and storage investment. [ABSTRACT FROM AUTHOR]

• IPO strategy generates Covering Perfect Hash Families efficiently. • Fast covering array generation for large scale combinatorial testing. • Many improvements to upper bounds on CAN. • CPHFs with subspace restrictions lead to many different small CAs. Combinatorial testing makes it possible to test large systems effectively while maintaining certain coverage guarantees. At the same time, the construction of optimized covering arrays (CAs) with a large number of columns is a challenging task. Heuristic and Metaheuristic approaches often become inefficient when applied to large instances, as the computation of the quality for new moves or solutions during the search becomes too slow. Recently, the generation of covering perfect hash families (CPHFs) has led to vast improvements to the state of the art for many different instances of covering arrays. CPHFs can be considered a compact form of a specific family of covering arrays. Their compact representation makes it possible to apply heuristic methods for instances with a much larger number of columns. In this work, we adapt the ideas of the well-known In-Parameter-Order (IPO) strategy for covering array generation to efficiently construct CPHFs, and therefore implicitly covering arrays. We design a way to realize the concept of vertical extension steps in the context of CPHFs and discuss how a horizontal extension can be implemented in an efficient manner. Further, we develop a horizontal extension strategy for CPHFs with subspace restrictions that identifies candidate columns greedily based on conditional expectation. Then using a local optimization strategy, a candidate may be adjoined to the solution or may replace one of the existing columns. An extensive set of computational results yields many significant improvements on the sizes of the smallest known covering arrays. [ABSTRACT FROM AUTHOR]

Sequential processes can encounter faults as a result of improper ordering of subsets of the events. In order to reveal faults caused by the relative ordering of t or fewer of v events, for some fixed t, a test suite must provide tests so that every ordering of every set of t or fewer events is exercised. Such a test suite is equivalent to a sequence covering array, a set of permutations on v events for which every subsequence of t or fewer events arises in at least one of the permutations. Equivalently it is a (different) set of permutations, a completely t-scrambling set of permutations, in which the images of every set of t chosen events include each of the t! possible "patterns." In event sequence testing, minimizing the number of permutations used is the principal objective. By developing a connection with covering arrays, lower bounds on this minimum in terms of the minimum number of rows in covering arrays are obtained. An existing bound on the largest v for which the minimum can equal t! is improved. A conditional expectation algorithm is developed to generate sequence covering arrays whose number of permutations never exceeds a specified logarithmic function of v when t is fixed, and this method is shown to operate in polynomial time. A recursive product construction is established when t = 3 to construct sequence covering arrays on vw events from ones on v and w events. Finally computational results are given for t ∈{3, 4, 5} to demonstrate the utility of the conditional expectation algorithm and the product construction. [ABSTRACT FROM AUTHOR]

The primary function of the medium access control (MAC) protocol is managing access to the shared communication channel. From the viewpoint of the transmitters, the MAC protocol determines each transmitter's channel occupancy, the fraction of time that it spends transmitting over the channel. In this paper, we define a set of topological persistences that conform to both network topology and traffic load. We employ these persistences as target occupancies for the MAC layer protocol. A centralized algorithm is developed for calculating topological persistences and its correctness is established. A distributed algorithm and implementation are developed that can operate within scheduled and contention-based MAC protocols. In the distributed algorithm, network resources are allocated through auctions at each receiver in which transmitters participate as bidders to converge on the topological allocation. Very low overhead is achieved by piggybacking auction and bidder communication on existing data packets. The practicality of the distributed algorithm is demonstrated in a wireless network via simulation using the ns-2 network simulator. Simulation results show fast convergence to the topological solution and, once operating with topological persistences, improved performance compared to IEEE 802.11 in delay, throughput, and drop rate. [ABSTRACT FROM PUBLISHER]

Algorithmic construction of software interaction test suites has focussed on pairwise coverage; less is known about the efficient construction of test suites for t-way interactions with t≥3. This study extends an efficient density-based algorithm for pairwise coverage to generate t-way interaction test suites and shows that it guarantees a logarithmic upper bound on the size of the test suites as a function of the number of factors. To complement this theoretical guarantee, an implementation is outlined and some practical improvements are made. Computational comparisons with other published methods are reported. Many of the results improve upon those in the literature. However, limitations on the ability of one-test-at-a-time algorithms are also identified. Copyright © 2008 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Abstract: A graph is fully gated when every convex set of vertices is gated. Doignon posed the problem of characterizing fully gated graphs and in particular of deciding whether there is an efficient algorithm for their recognition. While the number of convex sets can be exponential, we establish that it suffices to examine only the convex hulls of pairs of vertices. This yields an elementary polynomial time algorithm for the recognition of fully gated graphs; however, it does not appear to lead to a simple structural characterization. In this direction, we establish that fully gated graphs are closed under a set of ‘convex’ operations, including a new operation which duplicates the vertices of a convex set (under some well-defined restrictions). This in turn establishes that every bipartite graph is an isometric subgraph of a fully gated graph, thereby severely limiting the potential for a characterization based on subgraphs. Finally, a large class of fully gated graphs is obtained using the presence of bipartite dominators, which suggests that simple convex operations cannot suffice to produce all fully gated graphs. [Copyright &y& Elsevier]

There are many published algorithms for generating interaction test suites for software testing, exemplified by AETG, IPO, TCG, TConfig, simulated annealing and other heuristic search, and combinatorial design techniques. Among these, greedy one-test-at-a-time methods (such as AETG and TCG) have proven to be a reasonable compromise between the needs for small test suites, fast test-suite generation, and flexibility to accommodate a variety of testing scenarios. However, such methods suffer from the lack of a worst-case logarithmic guarantee on test suite size, while methods that provide such a guarantee at present are less efficient or flexible, or do not produce test suites that are competitive in size for practical testing scenarios. In this paper, a new algorithm establishes that efficient, greedy, one-test-at-a-time methods can indeed produce a logarithmic worst-case guarantee on the test suite size. In addition, this can be done while still producing test suites that are of competitive size, and in a time that is comparable to the published methods. It is deterministic, guaranteeing reproducibility. It generates only one candidate test at a time, permits users to ‘seed’ the test suite with specified tests, and allows users to specify constraints of combinations that should be avoided. Further, statistical analysis examines the impact of five variables used to tune this density algorithm for execution time and test suite size: weighting of density for factors, scaling of density, tie-breaking, use of multiple candidates, and multiple repetitions using randomization. Copyright © 2007 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Abstract: Reliability is a major concern in the design of large disk arrays. In this paper, we examine the effect of encountering more failures than that for which the RAID array was initially designed. Erasure codes are incorporated to enable system recovery from a specified number of disk erasures, and strive beyond that threshold to recover the system as frequently, and as thoroughly, as is possible. Erasure codes for tolerating two disk failures are examined. For these double erasure codes, we establish a correspondence between system operation and acyclicity of its graph model. For the most compact double erasure code, the full 2-code, this underlies an efficient algorithm for the computation of system operation probability (all disks operating or recoverable). When the system has failed, some disks are nonetheless recoverable. We extend the graph model to determine the probability that d disks have failed, a of which are recoverable by solving one linear equation, b of which are further recoverable by solving systems of linear equations, and of which cannot be recovered. These statistics are efficiently calculated for the full 2-code by developing a three variable ordinary generating function whose coefficients give the specified values. Finally, examples are given to illustrate the probability that an individual disk can be recovered, even when the system is in a failed state. [Copyright &y& Elsevier]

Studies the combinatorial and computational constructions for difference triangle sets having small scopes. Combinatorial asymptotics for difference triangle sets; Algorithms for constructing difference triangle sets; Conclusions.

An efficient generalization of Shanthikumar's upper bound on two-terminal reliability is developed, that leads to efficient methods for the probabilistic assessment of damage from fire spread and other invasive hazards in segmented structures. The methods exploit a basic relationship between the fire spread problem and the probability of reachability in communications networks. The upper bound employs noncrossing cuts of the network. [ABSTRACT FROM AUTHOR]

This is a short tutorial introduction to combinatorial aspects of network reliability, focusing on recent results in the area. Topics include the complexity of reliability computations, exact algorithms, bounding methods and Monte Carlo strategies. [ABSTRACT FROM AUTHOR]