13757062
Faster solution to the maximum quartet consistency problem with constraint programming
Evolution is an important sub-area of study in biological science, whereby the evolutionary history, or phylogeny, would shed light on the genetic linkage and the functional correlation for the species under consideration. Many kinds of species data can be deployed for the task and many phylogeny reconstruction methods have been examined in the literature. A quartet approach is to build a local phylogeny for every 4 species, which is called a quartet for these 4 species, and then to assemble a phylogeny for the whole set of species satisfying the topological constraints imposed by these quartets built. In practice, those predicted quartets might not agree each other and the optimization problem, the well-known Maximum Quartet Consistency (MQC) problem, is to construct a phylogeny to satisfy a maximum number of the predicted quartets. An equivalent representation for the MQC problem through searching for a certain ultrametric matrix via Answer Set Programming has recently been proposed. This paper follows the approach and presents a number of optimization techniques to speed up the searching process. The experimental results on both the simulated and real datasets suggest that the new representation combined with Constraint Programming presents a unique perspective to the MQC problem.
9960122
Dynamic Zone-Balancing of Topology-Aware Peer-to-Peer Networks
Building a topology-aware peer-to-peer overlay network can bring many advantages, such as providing locality-aware connectivity and reducing routing path length. While its benefits on performance have been recognized, an uneven overlay zone distribution has emerged. Recent work has shown that topology-aware neighbor selection during construction can aggravate the unbalance of zone distribution while it reduces routing path length. The imbalance in zone sizes may lead to performance decrease and an unfair load distribution. 
 
In this paper, we present an even topology-aware peer-to-peer network based on De Bruijn Graph by developing a dynamic zone-balancing approach.
2439726
Concept boundary detection for speeding up SVMs
Support Vector Machines (SVMs) suffer from an O(n2) training cost, where n denotes the number of training instances. In this paper, we propose an algorithm to select boundary instances as training data to substantially reduce n. Our proposed algorithm is motivated by the result of (Burges, 1999) that, removing non-support vectors from the training set does not change SVM training results. Our algorithm eliminates instances that are likely to be non-support vectors. In the concept-independent preprocessing step of our algorithm, we prepare nearest-neighbor lists for training instances. In the concept-specific sampling step, we can then effectively select useful training data for each target concept. Empirical studies show our algorithm to be effective in reducing n, outperforming other competing downsampling algorithms without significantly compromising testing accuracy.
2388375
Congestion control via online sampling
We consider the congestion control problem in a communication network with multiple traffic sources, each modeled as a fully-controllable stream of fluid traffic. The controlled traffic shares a common bottleneck node with high-priority cross traffic described by a Markov-modulated fluid (MMF). Each controlled source is assumed to have a unique round-trip delay. We wish to maximize a linear combination of the throughput, delay, traffic loss rate, and a fairness metric at the bottleneck node. We introduce an online sampling-based burst-level congestion control scheme capable of performing effectively under rapidly-varying cross traffic by making explicit use of the provided MMF model of that variation. The control problem is posed as a finite-horizon Markov decision process and is solved heuristically using a technique called hindsight optimization. We provide a detailed derivation of our congestion control algorithm based on this technique. The distinguishing feature of our scheme relative to conventional congestion control schemes is that we exploit a stochastic model of the cross traffic. Our empirical study shows that our control scheme significantly outperforms the conventional proportional-derivative (PD) controller, achieving higher utilization, lower delay, and lower loss under reasonable fairness. The performance advantage of our scheme over the PD scheme grows as the rate variance of cross traffic increases, underscoring the effectiveness of our control scheme under variable cross traffic.
18105952
Adapting Prime Number Labeling Scheme for Directed Acyclic Graphs
Directed Acyclic Graph(DAG) could be used for modeling subsumption hierarchies. Several labeling schemes have been proposed or tailored for indexing DAG in order to efficiently explore relationships in such hierarchy. However few of them can satisfy all the requirements in response time, space, and effect of updates simultaneously. In this paper, the prime number labeling scheme is extended for DAG. The scheme invests intrinsic mapping between integer divisibility and subsumption hierarchy, which simplifies the transitive closure computations and diminishes storage redundancy, as well as inherits the dynamic labeling ability from original scheme. Performance is further improved by introducing some optimization techniques. Our extensive experimental results show that prime number labeling scheme for DAG outperforms interval-based and prefix-based labeling schemes in most cases.
4178545
Data placement and query processing based on RPE parallelisms
The basic idea behind parallel database systems is to perform operations in parallel to reduce the response time and improve the system throughput. Data placement is a key factor on the performance of parallel database systems. This paper proposes two data partition strategies to decluster XML documents with very large size, path schema based path instance balancing (PSPIB) strategy, in which all path instances with the same path schema in a data tree are declustered evenly over all sites, and node schema based node round-robin (NSNRR) strategy, in which all node objects with the same node schema in a data tree are declustered over all sites in a round-robin way. Accordingly, two query processing algorithms are proposed based on the two partition methods, parallel path merge (PPM) algorithm and parallel pipelining path join (PPPJ) algorithm. The performance analysis and evaluation on the two data placement strategies and corresponding query processing algorithms are given in this paper.
17315153
Randomness and universal machines
The present work investigates several questions from a recent survey of Miller and Nies related to Chaitin's @W numbers and their dependence on the underlying universal machine. Furthermore, the notion @W"U[X][email protected]?"p":"U"("p")"@7"@?"X2^-^|^p^| is studied for various sets X and universal machines U. A universal machine U is constructed such that for all x, @W"U[{x}]=2^1^-^H^(^x^). For such a universal machine there exists a co-r.e. set X such that @W"U[X] is neither left-r.e. nor Martin-Lof random. Furthermore, one of the open problems of Miller and Nies is answered completely by showing that there is a sequence U"n of universal machines such that the truth-table degrees of the @W"U"""n form an antichain. Finally, it is shown that the members of hyperimmune-free Turing degree of a given @P"1^0-class are not low for @W unless this class contains a recursive set.
6594297
Generic Universal Switch Blocks
A switch block M with W terminals on each side is said to be universal if every set of nets satisfying the dimension constraint (i.e., the number of nets on each side of M is at most W) is simultaneously routable through M. In this paper, we present an algorithm to construct N-sided universal switch blocks with W terminals on each side. Each of our universal switch blocks has (/sub 2//sup N/) W switches and switch-block flexibility N-1 (i.e., F/sub S/=N-1). We prove that no switch block with less than (/sub 2//sup N/)W switches can be universal. We also compare our universal switch blocks with others of the topology associated with Xilinx XC4000-type FPGAs. To explore the area performance of the universal switch blocks, we develop a detailed router for hierarchical FPGAs (HFPGAs) with 5-sided switch blocks. Experimental results demonstrate that our universal switch blocks improve routability at the chip level. Based on extensive experiments, we also provide key insights into the interactions between switch-block architectures and routing.
1432738
SGDB: a database of synthetic genes re-designed for optimizing protein over-expression
Here we present the Synthetic Gene Database (SGDB): a relational database that houses sequences and associated experimental information on synthetic (artificially engineered) genes from all peer-reviewed studies published to date. At present, the database comprises information from more than 200 published experiments. This resource not only provides reference material to guide experimentalists in designing new genes that improve protein expression, but also offers a dataset for analysis by bioinformaticians who seek to test ideas regarding the underlying factors that influence gene expression. The SGDB was built under MySQL database management system. We also offer an XML schema for standardized data description of synthetic genes. Users can access the database at , or batch downloads all information through XML files. Moreover, users may visually compare the coding sequences of a synthetic gene and its natural counterpart with an integrated web tool at , and discuss questions, findings and related information on an associated e-forum at .
35293254
Quasi-complements of the cappable degrees
Say that a nonzero c. e. degree b is a quasi-complement of a c. e. degree a if a ∩ b = 0 and a ∪ b is high. It is well-known (due to Shore) that each cappable degree has a high quasi-complement. However, by the existence of the almost deep degrees, there are nonzero cappable degrees having no low quasi-complements. In this paper, we prove that any nonzero cappable degree has a low2 quasi-complement. (© 2004 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)
35154734
Isolation and the Jump Operator