MOTIVATION: Extended tandem repeats (TRs) have been associated with 60 or more diseases over the past 30 years. Although most TRs have single repeat units (or motifs), complex TRs with different units have recently been correlated with some brain disorders. Of note, a population-scale analysis shows that complex TRs at one locus can be divergent, and different units are often expanded between individuals. To understand the evolution of high TR diversity, it is informative to visualize a phylogenetic tree. To do this, we need to measure the edit distance between pairs of complex TRs by considering duplication and contraction of units created by replication slippage. However, traditional rigorous algorithms for this purpose are computationally expensive. RESULTS: We here propose an efficient heuristic algorithm to estimate the edit distance with duplication and contraction of units (EDDC, for short). We select a set of frequent units that occur in given complex TRs, encode each unit as a single symbol, compress a TR into an optimal series of unit symbols that partially matches the original TR with the minimum Levenshtein distance, and estimate the EDDC between a pair of complex TRs from their compressed forms. Using substantial synthetic benchmark datasets, we demonstrate that the estimated EDDC is highly correlated with the accurate EDDC, with a Pearson correlation coefficient of >0.983, while the heuristic algorithm achieves orders of magnitude performance speedup. AVAILABILITY AND IMPLEMENTATION: The software program hEDDC that implements the proposed algorithm is available at https://github.com/Ricky-pon/hEDDC (DOI: 10.5281/zenodo.14732958).

MOTIVATION: Over the past 30 years, extended tandem repeats (TRs) have been correlated with ∼60 diseases with high odds ratios, and most known TRs consist of single repeat units. However, in the last few years, mosaic TRs composed of different units have been found to be associated with several brain disorders by long-read sequencing techniques. Mosaic TRs are difficult-to-characterize sequence configurations that are usually confirmed by manual inspection. Widely used tools are not designed to solve the mosaic TR problem and often fail to properly decompose mosaic TRs. RESULTS: We propose an efficient algorithm that can decompose mosaic TRs in the input string with high sensitivity. Using synthetic benchmark data, we demonstrate that our program named uTR outperforms TRF and RepeatMasker in terms of prediction accuracy, this is especially true when mosaic TRs are more complex, and uTR is faster than TRF and RepeatMasker in most cases. AVAILABILITY AND IMPLEMENTATION: The software program uTR that implements the proposed algorithm is available at https://github.com/morisUtokyo/uTR.

MOTIVATION: Diploid assembly, or determining sequences of homologous chromosomes separately, is essential to elucidate genetic differences between haplotypes. One approach is to call and phase single nucleotide variants (SNVs) on a reference sequence. However, this approach becomes unstable on large segmental duplications (SDs) or structural variations (SVs) because the alignments of reads deriving from these regions tend to be unreliable. Another approach is to use highly accurate PacBio HiFi reads to output diploid assembly directly. Nonetheless, HiFi reads cannot phase homozygous regions longer than their length and require oxford nanopore technology (ONT) reads or Hi-C to produce a fully phased assembly. Is a single long-read sequencing technology sufficient to create an accurate diploid assembly? RESULTS: Here, we present JTK, a megabase-scale diploid genome assembler. It first randomly samples kilobase-scale sequences (called 'chunks') from the long reads, phases variants found on them, and produces two haplotypes. The novel idea of JTK is to utilize chunks to capture SNVs and SVs simultaneously. From 60-fold ONT reads on the HG002 and a Japanese sample, it fully assembled two haplotypes with approximately 99.9% accuracy on the histocompatibility complex (MHC) and the leukocyte receptor complex (LRC) regions, which was impossible by the reference-based approach. In addition, in the LRC region on a Japanese sample, JTK output an assembly of better contiguity than those built from high-coverage HiFi+Hi-C. In the coming age of pan-genomics, JTK would complement the reference-based phasing method to assemble the difficult-to-assemble but medically important regions. AVAILABILITY AND IMPLEMENTATION: JTK is available at https://github.com/ban-m/jtk, and the datasets are available at https://doi.org/10.5281/zenodo.7790310 or JGAS000580 in DDBJ.

MOTIVATION: Long tandem repeat expansions of more than 1000 nt have been suggested to be associated with diseases, but remain largely unexplored in individual human genomes because read lengths have been too short. However, new long-read sequencing technologies can produce single reads of 10 000 nt or more that can span such repeat expansions, although these long reads have high error rates, of 10-20%, which complicates the detection of repetitive elements. Moreover, most traditional algorithms for finding tandem repeats are designed to find short tandem repeats (<1000 nt) and cannot effectively handle the high error rate of long reads in a reasonable amount of time. RESULTS: Here, we report an efficient algorithm for solving this problem that takes advantage of the length of the repeat. Namely, a long tandem repeat has hundreds or thousands of approximate copies of the repeated unit, so despite the error rate, many short k-mers will be error-free in many copies of the unit. We exploited this characteristic to develop a method for first estimating regions that could contain a tandem repeat, by analyzing the k-mer frequency distributions of fixed-size windows across the target read, followed by an algorithm that assembles the k-mers of a putative region into the consensus repeat unit by greedily traversing a de Bruijn graph. Experimental results indicated that the proposed algorithm largely outperformed Tandem Repeats Finder, a widely used program for finding tandem repeats, in terms of sensitivity. AVAILABILITY AND IMPLEMENTATION: https://github.com/morisUtokyo/mTR.

Plant mitochondrial genomes have distinctive features compared to those of animals; namely, they are large and divergent, with sizes ranging from hundreds of thousands of to a few million bases. Recombination among repetitive regions is thought to produce similar structures that differ slightly, known as "multipartite structures," which contribute to different phenotypes. Although many reference plant mitochondrial genomes represent almost all the genes in mitochondria, the full spectrum of their structures remains largely unknown. The emergence of long-read sequencing technology is expected to yield this landscape; however, many studies aimed to assemble only one representative circular genome, because properly understanding multipartite structures using existing assemblers is not feasible. To elucidate multipartite structures, we leveraged the information in existing reference genomes and classified long reads according to their corresponding structures. We developed a method that exploits two classic algorithms, partial order alignment (POA) and the hidden Markov model (HMM) to construct a sensitive read classifier. This method enables us to represent a set of reads as a POA graph and analyze it using the HMM. We can then calculate the likelihood of a read occurring in a given cluster, resulting in an iterative clustering algorithm. For synthetic data, our proposed method reliably detected one variation site out of 9,000-bp synthetic long reads with a 15% sequencing-error rate and produced accurate clustering. It was also capable of clustering long reads from six very similar sequences containing only slight differences. For real data, we assembled putative multipartite structures of mitochondrial genomes of Arabidopsis thaliana from nine accessions sequenced using PacBio Sequel. The results indicated that there are recurrent and strain-specific structures in A. thaliana mitochondrial genomes.

MOTIVATION: De novo assembly of reference-quality genomes used to require enormously laborious tasks. In particular, it is extremely time-consuming to build genome markers for ordering assembled contigs along chromosomes; thus, they are only available for well-established model organisms. To resolve this issue, recent studies demonstrated that Hi-C could be a powerful and cost-effective means to output chromosome-length scaffolds for non-model species with no genome marker resources, because the Hi-C contact frequency between a pair of two loci can be a good estimator of their genomic distance, even if there is a large gap between them. Indeed, state-of-the-art methods such as 3D-DNA are now widely used for locating contigs in chromosomes. However, it remains challenging to reduce errors in contig orientation because shorter contigs have fewer contacts with their neighboring contigs. These orientation errors lower the accuracy of gene prediction, read alignment, and synteny block estimation in comparative genomics. RESULTS: To reduce these contig orientation errors, we propose a new algorithm, named HiC-Hiker, which has a firm grounding in probabilistic theory, rigorously models Hi-C contacts across contigs, and effectively infers the most probable orientations via the Viterbi algorithm. We compared HiC-Hiker and 3D-DNA using human and worm genome contigs generated from short reads, evaluated their performances, and observed a remarkable reduction in the contig orientation error rate from 4.3% (3D-DNA) to 1.7% (HiC-Hiker). Our algorithm can consider long-range information between distal contigs and precisely estimates Hi-C read contact probabilities among contigs, which may also be useful for determining the ordering of contigs. AVAILABILITY AND IMPLEMENTATION: HiC-Hiker is freely available at: https://github.com/ryought/hic_hiker.

MOTIVATION: Detection of DNA at low abundance with respect to the entire sample is an important problem in areas such as epidemiology and field research, as these samples are highly contaminated with non-target DNA. To solve this problem, many methods have been developed to date, but all require additional time-consuming and costly procedures. Meanwhile, the MinION sequencer developed by Oxford Nanopore Technology (ONT) is considered a powerful tool for tackling this problem, as it allows selective sequencing of target DNA. The main technology employed involves rejection of an undesirable read from a specific pore by inverting the voltage of that pore, which is referred to as 'Read Until'. Despite its usefulness, several issues remain to be solved in real situations. First, limited computational resources are available in field research and epidemiological applications. In addition, a high-speed online classification algorithm is required to make a prompt decision. Lastly, the lack of a theoretical approach for modeling of selective sequencing makes it difficult to analyze and justify a given algorithm. RESULTS: In this paper, we introduced a statistical model of selective sequencing, proposed an efficient constant-time classifier for any background DNA profile, and validated its optimal precision. To confirm the feasibility of the proposed method in practice, for a pre-recorded mock sample, we demonstrate that the method can selectively sequence a 100 kb region, consisting of 0.1% of the entire read pool, and achieve approximately 500-fold amplification. Furthermore, the algorithm is shown to process 26 queries per second with a $500 palm-sized next unit of computing box using an Intel® CoreTMi7 CPU without extended computer resources such as a GPU or high-performance computing. Next, we prepared a mixed DNA pool composed of Saccharomyces cerevisiae and lambda phage, in which any 200 kb region of S.cerevisiae consists of 0.1% of the whole sample. From this sample, a 30-230 kb region of S.cerevisiae chromosome 1 was amplified approximately 30-fold. In addition, this method allowed on-the-fly changing of the amplified region according to the uncovered characteristics of a given DNA sample. AVAILABILITY AND IMPLEMENTATION: The source code is available at: https://bitbucket.org/ban-m/dyss.

Bioinformatics, https://doi.org/10.1093/bioinformatics/bty663 The publisher wishes to inform the reader that Table 1. In the above manuscript was published incorrectly. The corrected table appears below: Evaluation of each method using a pre-recorded dataset Note: The reference size was 100 kb, and the queries were 250 events long. Aside from the proposed method, a 15-nearest neighbor was used as a classifier. In the parameter descriptions, t refers to the re-chunking parameter (1). This parameter was tuned from 0 to 50. b denotes the bandwidth of the Sakoe–Chiba algorithm. This parameter ranged from 11 to 91. s and k denote the number of packs and number of candidates in the seeding step (see Section 3.4.3). The best score for each criterion is represented in bold. Evaluation of each method using a pre-recorded dataset Note: The reference size was 100 kb, and the queries were 250 events long. Aside from the proposed method, a 15-nearest neighbor was used as a classifier. In the parameter descriptions, t refers to the re-chunking parameter (1). This parameter was tuned from 0 to 50. b denotes the bandwidth of the Sakoe–Chiba algorithm. This parameter ranged from 11 to 91. s and k denote the number of packs and number of candidates in the seeding step (see Section 3.4.3). The best score for each criterion is represented in bold. The paper has been corrected online.

Welcome to the 2016 IEEE International Conference on Bioinformatics and Biomedicine (IEEE BIBM 2016) being held in the Shenzhen, China from December 15–18, 2016. On behalf of the IEEE BIBM 2016 Organizing Team, we would like to thank you for your participation and hope you enjoy the conference.

MOTIVATION: Determining the methylation state of regions with high copy numbers is challenging for second-generation sequencing, because the read length is insufficient to map reads uniquely, especially when repetitive regions are long and nearly identical to each other. Single-molecule real-time (SMRT) sequencing is a promising method for observing such regions, because it is not vulnerable to GC bias, it produces long read lengths, and its kinetic information is sensitive to DNA modifications. RESULTS: We propose a novel linear-time algorithm that combines the kinetic information for neighboring CpG sites and increases the confidence in identifying the methylation states of those sites. Using a practical read coverage of ∼30-fold from an inbred strain medaka (Oryzias latipes), we observed that both the sensitivity and precision of our method on individual CpG sites were ∼93.7%. We also observed a high correlation coefficient (R = 0.884) between our method and bisulfite sequencing, and for 92.0% of CpG sites, methylation levels ranging over [0,1] were in concordance within an acceptable difference 0.25. Using this method, we characterized the landscape of the methylation status of repetitive elements, such as LINEs, in the human genome, thereby revealing the strong correlation between CpG density and hypomethylation and detecting hypomethylation hot spots of LTRs and LINEs. We uncovered the methylation states for nearly identical active transposons, two novel LINE insertions of identity ∼99% and length 6050 base pairs (bp) in the human genome, and 16 Tol2 elements of identity >99.8% and length 4682 bp in the medaka genome. AVAILABILITY AND IMPLEMENTATION: AgIn (Aggregate on Intervals) is available at: https://github.com/hacone/AgIn CONTACT: [email protected] or [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: Long expansions of short tandem repeats (STRs), i.e. DNA repeats of 2-6 nt, are associated with some genetic diseases. Cost-efficient high-throughput sequencing can quickly produce billions of short reads that would be useful for uncovering disease-associated STRs. However, enumerating STRs in short reads remains largely unexplored because of the difficulty in elucidating STRs much longer than 100 bp, the typical length of short reads. RESULTS: We propose ab initio procedures for sensing and locating long STRs promptly by using the frequency distribution of all STRs and paired-end read information. We validated the reproducibility of this method using biological replicates and used it to locate an STR associated with a brain disease (SCA31). Subsequently, we sequenced this STR site in 11 SCA31 samples using SMRT(TM) sequencing (Pacific Biosciences), determined 2.3-3.1 kb sequences at nucleotide resolution and revealed that (TGGAA)- and (TAAAATAGAA)-repeat expansions determined the instability of the repeat expansions associated with SCA31. Our method could also identify common STRs, (AAAG)- and (AAAAG)-repeat expansions, which are remarkably expanded at four positions in an SCA31 sample. This is the first proposed method for rapidly finding disease-associated long STRs in personal genomes using hybrid sequencing of short and long reads. AVAILABILITY AND IMPLEMENTATION: Our TRhist software is available at http://trhist.gi.k.u-tokyo.ac.jp/. CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

K-means clustering has been widely used to gain insight into biological systems from large-scale life science data. To quantify the similarities among biological data sets, Pearson correlation distance and standardized Euclidean distance are used most frequently; however, optimization methods have been largely unexplored. These two distance measurements are equivalent in the sense that they yield the same k-means clustering result for identical sets of k initial centroids. Thus, an efficient algorithm used for one is applicable to the other. Several optimization methods are available for the Euclidean distance and can be used for processing the standardized Euclidean distance; however, they are not customized for this context. We instead approached the problem by studying the properties of the Pearson correlation distance, and we invented a simple but powerful heuristic method for markedly pruning unnecessary computation while retaining the final solution. Tests using real biological data sets with 50-60K vectors of dimensions 10-2001 (~400 MB in size) demonstrated marked reduction in computation time for k = 10-500 in comparison with other state-of-the-art pruning methods such as Elkan's and Hamerly's algorithms. The BoostKCP software is available at http://mlab.cb.k.u-tokyo.ac.jp/~ichikawa/boostKCP/.

UNLABELLED: The advent of high-throughput DNA sequencers has increased the pace of collecting enormous amounts of genomic information, yielding billions of nucleotides on a weekly basis. This advance represents an improvement of two orders of magnitude over traditional Sanger sequencers in terms of the number of nucleotides per unit time, allowing even small groups of researchers to obtain huge volumes of genomic data over fairly short period. Consequently, a pressing need exists for the development of personalized genome browsers for analyzing these immense amounts of locally stored data. The UTGB (University of Tokyo Genome Browser) Toolkit is designed to meet three major requirements for personalization of genome browsers: easy installation of the system with minimum efforts, browsing locally stored data and rapid interactive design of web interfaces tailored to individual needs. The UTGB Toolkit is licensed under an open source license. AVAILABILITY: The software is freely available at http://utgenome.org/.

BACKGROUND: RNA interference (RNAi), mediated by 21-nucleotide (nt)-length small interfering RNAs (siRNAs), is a powerful tool not only for studying gene function but also for therapeutic applications. RNAi, requiring perfect complementarity between the siRNA guide strand and the target mRNA, was believed to be extremely specific. However, a recent growing body of evidence has suggested that siRNA could down-regulate unintended genes whose transcripts possess complementarity to the 7-nt siRNA seed region. This off-target gene silencing may often provide incongruous results obtained from knockdown experiments, leading to misinterpretation. Thus, an efficient algorithm for designing functional siRNAs with minimal off-target effect based on the mechanistic features is considered of value. RESULTS: We present siDirect 2.0, an update of our web-based software siDirect, which provides functional and off-target minimized siRNA design for mammalian RNAi. The previous version of our software designed functional siRNAs by considering the relationship between siRNA sequence and RNAi activity, and provided them along with the enumeration of potential off-target gene candidates by using a fast and sensitive homology search algorithm. In the new version, the siRNA design algorithm is extensively updated to eliminate off-target effects by reflecting our recent finding that the capability of siRNA to induce off-target effect is highly correlated to the thermodynamic stability, or the melting temperature (Tm), of the seed-target duplex, which is formed between the nucleotides positioned at 2-8 from the 5' end of the siRNA guide strand and its target mRNA. Selection of siRNAs with lower seed-target duplex stabilities (benchmark Tm < 21.5 degrees C) followed by the elimination of unrelated transcripts with nearly perfect match should minimize the off-target effects. CONCLUSION: siDirect 2.0 provides functional, target-specific siRNA design with the updated algorithm which significantly reduces off-target silencing. When the candidate functional siRNAs could form seed-target duplexes with Tm values below 21.5 degrees C, and their 19-nt regions spanning positions 2-20 of both strands have at least two mismatches to any other non-targeted transcripts, siDirect 2.0 can design at least one qualified siRNA for >94% of human mRNA sequences in RefSeq. siDirect 2.0 is available at http://siDirect2.RNAi.jp/.

We study the problem of querying relational data embedded in XML. Relational data can be represented by various tree structures in XML. However, current XML query methods, such as XPath and XQuery, demand explicit path expressions, and thus it is quite difficult for users to produce correct XML queries in the presence of structural variations. To solve this problem, we introduce a novel query method that automatically discovers various XML structures derived from rela-tional data. A challenge in implementing our method is to reduce the cost of enumerating all possible tree structures that match the query. We show that the notion of functional dependencies has an important role in generating efficient query schedules that avoid ir-relevant tree structures. Our proposed method, the relational-style XML query, has sev-eral advantages over traditional XML data management. These in-clude removing the burden of designing strict tree-pattern schemas, enhancing the descriptions of relational data with XML’s rich se-mantics, and taking advantage of schema evolution capability of XML. In addition, the independence of query statements from the underlying XML structure is advantageous for integrating XML data from several sources. We present extensive experimental re-sults that confirm the scalability and tolerance of our query method for various sizes of XML data containing structural variations.

MOTIVATION: Designing highly effective short interfering RNA (siRNA) sequences with maximum target-specificity for mammalian RNA interference (RNAi) is one of the hottest topics in molecular biology. The relationship between siRNA sequences and RNAi activity has been studied extensively to establish rules for selecting highly effective sequences. However, there is a pressing need to compute siRNA sequences that minimize off-target silencing effects efficiently and to match any non-targeted sequences with mismatches. RESULTS: The enumeration of potential cross-hybridization candidates is non-trivial, because siRNA sequences are short, ca. 19 nt in length, and at least three mismatches with non-targets are required. With at least three mismatches, there are typically four or five contiguous matches, so that a BLAST search frequently overlooks off-target candidates. By contrast, existing accurate approaches are expensive to execute; thus we need to develop an accurate, efficient algorithm that uses seed hashing, the pigeonhole principle, and combinatorics to identify mismatch patterns. Tests show that our method can list potential cross-hybridization candidates for any siRNA sequence of selected human gene rapidly, outperforming traditional methods by orders of magnitude in terms of computational performance. AVAILABILITY: http://design.RNAi.jp CONTACT: [email protected].

MOTIVATION: Gene expression profiles should be useful in distinguishing variations in disease, since they reflect accurately the status of cells. The primary clustering of gene expression reveals the genotypes that are responsible for the proximity of members within each cluster, while further clustering elucidates the pathological features of the individual members of each cluster. However, since the first clustering process and the second classification step, in which the features are associated with clusters, are performed independently, the initial set of clusters may omit genes that are associated with pathologically meaningful features. Therefore, it is important to devise a way of identifying gene expression clusters that are associated with pathological features. RESULTS: We present the novel technique of 'itemset constrained clustering' (IC-Clustering), which computes the optimal cluster that maximizes the interclass variance of gene expression between groups, which are divided according to the restriction that only divisions that can be expressed using common features are allowed. This constraint automatically labels each cluster with a set of pathological features which characterize that cluster. When applied to liver cancer datasets, IC-Clustering revealed informative gene expression clusters, which could be annotated with various pathological features, such as 'tumor' and 'man', or 'except tumor' and 'normal liver function'. In contrast, the k-means method overlooked these clusters.

We discuss data mining based on association rules for two numeric attributes and one Boolean attribute. For example, in a database of bank customers, Age and Balance are two numeric attributes, and CardLoan is a Boolean attribute. Taking the pair (Age, Balance) as a point in two-dimensional space, we consider an association rule of the form ((Age,Balance) ∈P)⇒(CardLoan = Yes), which implies that bank customers whose ages and balances fall within a planar region P tend to take out credit card loans with a high probability.We consider two classes of regions, rectangles and admissible (i.e., connected and x-monotone) regions. For each class, we propose efficient algorithms for computing the regions that give optimal association rules for gain, support, and confidence, respectively. We have implemented the algorithms for admissible regions as well as several advanced functions based on them in our data mining system named SONAR (System for Optimized Numeric Association Rules), where the rules are visualized by using a graphic user interface to make it easy for users to gain an intuitive understanding of rules.

We study how to efficiently compute significant association rules according to common statistical measures such as a chi-squared value or correlation coefficient. For this purpose, one might consider to use of the Apriori algorithm, but the algorithm needs major conversion, because none of these statistical metrics are anti-monotone, and the use of higher support for reducing the search space cannot guarantee solutions in its the search space. We here present a method of estimating a tight upper bound on the statistical metric associated with any superset of an itemset, as well as the novel use of the resulting information of upper bounds to prune unproductive supersets while traversing itemset lattices. Experimental tests demonstrate the efficiency of this method.

Computing the natural join of a set of relations is an important operation in relational database systems. The ordering of joins determines to a large extent the computation time of the join. Since the number of possible orderings could be very large, query optimizers first reduce the search space by using various heuristics and then try to select an optimal ordering of joins. Avoiding Cartesian products is a common heuristic for reducing the search space, but it cannot guarantee optimal ordering in its search space, because the cheapest Cartesian-product-free (CPF for short) ordering could be significantly worse than an optimal non-CPF ordering by a factor of an arbitrarily large number. In this paper, we use programs consisting of joins, semijoins, and projections for computing the join of some relations, and we introduce a novel algorithm that derives programs from CPF orderings of joins. We show that there exists a CPF ordering from which our algorithm derives a program whose cost is within a constant factor of the cost of an optimal ordering. Thus, our result demonstrates the effectiveness of avoiding Cartesian products as a heuristic for restricting the search space of orderings of joins.

Given a huge database, we address the problem of finding association rules for numeric attributes, such as Permission to make digital/hard copies of all or pati of this material for personal or claasroom usc is granted without fee provided that the copies are not made or distributed for pro~t or cornmesvial advantage, the copyright notice, the title of the publication and Its date appear, and notice is given that cop yright is by permission of the ACM, Inc.To copy otherwise, to repubtish, to post on servers or to redistribute to lists, requires specific permission and/or fee.PODS '96, Montreal Quebec Canada

We discuss data mining based on association rules for two numeric attributes and one Boolean attribute. For example, in a database of bank customers, "Age" and "Balance" are two numeric attributes, and "CardLoan" is a Boolean attribute. Taking the pair (Age, Balance) as a point in two-dimensional space, we consider an association rule of the form((Age, Balance) ∈ P) ⇒ (CardLoan = Yes),which implies that bank customers whose ages and balances fall in a planar region P tend to use card loan with a high probability. We consider two classes of regions, rectangles and admissible (i.e. connected and x-monotone) regions. For each class, we propose efficient algorithms for computing the regions that give optimal association rules for gain, support, and confidence, respectively. We have implemented the algorithms for admissible regions, and constructed a system for visualizing the rules.

No abstract available.

We study applying the magic-sets transformation technique to Datalog programs with negation that may not have 2-valued well-founded models. In this general setting we encounter the problem that the well-founded model of the original program does not always agree with the well-founded model of the magic program derived by commonly used left-to-right sips on the query. In order to fix this disagreement we present a novel method that is obtained by slightly and naturally tailoring Van Gelder's alternating fixpoint technique [16] to a magic program.

We describe the design and implementation of the Glue-Nail database system. The Nail language is a purely declarative query language; Glue is a procedural language used for non-query activities. The two languages combined are sufficient to write a complete application. Nail and Glue code both compile into the target language IGlue. The Nail compiler uses variants of the magic sets algorithm, and supports well-founded models. Static optimization is performed by the Glue compiler using techniques that include peephole methods and data flow analysis. The IGlue code is executed by the IGlue interpreter, which features a run-time adaptive optimizer. The three optimizers each deal with separate optimization domains, and experiments indicate that an effective synergism is achieved. The Glue-Nail system is largely complete and has been tested using a suite of representative applications.

Avoiding Cartesian products is a common heuristic to reduce the search space of join expressions (orderings) over some set of relations. However, this heuristic cannot guarantee optimal join expressions in its search space because the cheapest Cartesian-product-free (CPF, for short) join expression could be significantly worse than an optimal non-CPF join expression. In a recent PODS, Tay [9] gave some conditions on actual relations that ensure the existence of an optimal CPF join expression; however, the conditions turn out to be applicable only in special cases. In this paper, we do not put any restrictions on actual relations, and we introduce a novel technique that derives programs consisting of joins, semijoins, and projections from CPF join expressions. Our main result is that for every join expression, there exists an equivalent CPF join expression from which we can derive a program whose cost is within a constant factor of the cost of an optimal join expression.