BACKGROUND: Because of the short read length of high throughput sequencing data, assembly errors are introduced in genome assembly, which may have adverse impact to the downstream data analysis. Several tools have been developed to eliminate these errors by either 1) comparing the assembled sequences with some similar reference genome, or 2) analyzing paired-end reads aligned to the assembled sequences and determining inconsistent features alone mis-assembled sequences. However, the former approach cannot distinguish real structural variations between the target genome and the reference genome while the latter approach could have many false positive detections (correctly assembled sequence being considered as mis-assembled sequence). RESULTS: We present misFinder, a tool that aims to identify the assembly errors with high accuracy in an unbiased way and correct these errors at their mis-assembled positions to improve the assembly accuracy for downstream analysis. It combines the information of reference (or close related reference) genome and aligned paired-end reads to the assembled sequence. Assembly errors and correct assemblies corresponding to structural variations can be detected by comparing the genome reference and assembled sequence. Different types of assembly errors can then be distinguished from the mis-assembled sequence by analyzing the aligned paired-end reads using multiple features derived from coverage and consistence of insert distance to obtain high confident error calls. CONCLUSIONS: We tested the performance of misFinder on both simulated and real paired-end reads data, and misFinder gave accurate error calls with only very few miscalls. And, we further compared misFinder with QUAST and REAPR. misFinder outperformed QUAST and REAPR by 1) identified more true positive mis-assemblies with very few false positives and false negatives, and 2) distinguished the correct assemblies corresponding to structural variations from mis-assembled sequence. misFinder can be freely downloaded from https://github.com/hitbio/misFinder.

Predicting drug-target interaction using computational approaches is an important step in drug discovery and repositioning. To predict whether there will be an interaction between a drug and a target, most existing methods identify similar drugs and targets in the database. The prediction is then made based on the known interactions of these drugs and targets. This idea is promising. However, there are two shortcomings that have not yet been addressed appropriately. Firstly, most of the methods only use 2D chemical structures and protein sequences to measure the similarity of drugs and targets respectively. However, this information may not fully capture the characteristics determining whether a drug will interact with a target. Secondly, there are very few known interactions, i.e. many interactions are “missing” in the database. Existing approaches are biased towards known interactions and have no good solutions to handle possibly missing interactions which affect the accuracy of the prediction. In this paper, we enhance the similarity measures to include non-structural (and non-sequence-based) information and introduce the concept of a “super-target” to handle the problem of possibly missing interactions. Based on evaluations on real data, we show that our similarity measure is better than the existing measures and our approach is able to achieve higher accuracy than the two best existing algorithms, WNN-GIP and KBMF2K.

Bayesian networks (BNs) are popular for modeling conditional distributions of variables and causal relationships, especially in biological settings such as protein interactions, gene regulatory networks and microbial interactions. Previous BN structure learning algorithms treat variables with similar tendency separately. In this paper, we propose a grouped sparse Gaussian BN (GSGBN) structure learning algorithm which creates BN based on three assumptions: (i) variables follow a multivariate Gaussian distribution, (ii) the network only contains a few edges (sparse), (iii) similar variables have less-divergent sets of parents, while not-so-similar ones should have divergent sets of parents (variable grouping). We use L1regularization to make the learned network sparse, and another term to incorporate shared information among variables. For similar variables, GSGBN tends to penalize the differences of similar variables' parent sets more, compared to those not-so-similar variables' parent sets. The similarity of variables is learned from the data by alternating optimization, without prior domain knowledge. Based on this new definition of the optimal BN, a coordinate descent algorithm and a projected gradient descent algorithm are developed to obtain edges of the network and also similarity of variables. Experimental results on both simulated and real datasets show that GSGBN has substantially superior prediction performance for structure learning when compared to several existing algorithms.

MOTIVATION: Inferring gene-regulatory networks is very crucial in decoding various complex mechanisms in biological systems. Synthesis of a fully functional transcriptional factor/protein from DNA involves series of reactions, leading to a delay in gene regulation. The complexity increases with the dynamic delay induced by other small molecules involved in gene regulation, and noisy cellular environment. The dynamic delay in gene regulation is quite evident in high-temporal live cell lineage-imaging data. Although a number of gene-network-inference methods are proposed, most of them ignore the associated dynamic time delay. RESULTS: Here, we propose DDGni (dynamic delay gene-network inference), a novel gene-network-inference algorithm based on the gapped local alignment of gene-expression profiles. The local alignment can detect short-term gene regulations, that are usually overlooked by traditional correlation and mutual Information based methods. DDGni uses 'gaps' to handle the dynamic delay and non-uniform sampling frequency in high-temporal data, like live cell imaging data. Our algorithm is evaluated on synthetic and yeast cell cycle data, and Caenorhabditis elegans live cell imaging data against other prominent methods. The area under the curve of our method is significantly higher when compared to other methods on all three datasets. AVAILABILITY: The program, datasets and supplementary files are available at http://www.jjwanglab.org/DDGni/.

Feature selection is important for many biological studies, especially when the number of available samples is limited (in order of hundreds) while the number of input features is large (in order of millions), such as eQTL (expression quantitative trait loci) mapping, GWAS (genome wide association study) and environmental microbial community study. We study the problem of multiple output regression which leverages the underlying common relationship shared by multiple output features and propose an efficient and accurate approach for feature selection. Our approach considers both intra- and inter-group sparsities. The intergroup sparsity assumes that only small set of input features are related to the output features. The intragroup sparsity assumes that each input features may relate to multiple output features which should have different kinds of sparsity. Most existing methods do not model the intragroup sparsity well by either assuming uniform regularization on each group, i.e. each input feature relates to similar number of output features, or requiring prior knowledge of the relationship of input and output features. By modelling the regression coefficients as a mixture distributions of Laplacian and Gaussian, we can shrink group regression coefficients to be small adaptively and learn the intergroup, intragroup sparsity and shrinkage estimation patterns. Empirical studies on the synthetic and real environmental microbial community datasets show that our model has better predictions on test dataset than existing methods such as Lasso, Elastic Net, dirty model and rMTFL (robust multi-task feature learning). Moreover, by using least angle regression or coordinate descent and projected gradient descent techniques for optimization, we can obtain the optimal regression efficiently.

MOTIVATION: RNA sequencing based on next-generation sequencing technology is effective for analyzing transcriptomes. Like de novo genome assembly, de novo transcriptome assembly does not rely on any reference genome or additional annotation information, but is more difficult. In particular, isoforms can have very uneven expression levels (e.g. 1:100), which make it very difficult to identify low-expressed isoforms. One challenge is to remove erroneous vertices/edges with high multiplicity (produced by high-expressed isoforms) in the de Bruijn graph without removing correct ones with not-so-high multiplicity from low-expressed isoforms. Failing to do so will result in the loss of low-expressed isoforms or having complicated subgraphs with transcripts of different genes mixed together due to erroneous vertices/edges. Contributions: Unlike existing tools, which remove erroneous vertices/edges with multiplicities lower than a global threshold, we use a probabilistic progressive approach to iteratively remove them with local thresholds. This enables us to decompose the graph into disconnected components, each containing a few genes, if not a single gene, while retaining many correct vertices/edges of low-expressed isoforms. Combined with existing techniques, IDBA-Tran is able to assemble both high-expressed and low-expressed transcripts and outperform existing assemblers in terms of sensitivity and specificity for both simulated and real data. AVAILABILITY: http://www.cs.hku.hk/~alse/idba_tran. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: Next-generation sequencing allows us to sequence reads from a microbial environment using single-cell sequencing or metagenomic sequencing technologies. However, both technologies suffer from the problem that sequencing depth of different regions of a genome or genomes from different species are highly uneven. Most existing genome assemblers usually have an assumption that sequencing depths are even. These assemblers fail to construct correct long contigs. RESULTS: We introduce the IDBA-UD algorithm that is based on the de Bruijn graph approach for assembling reads from single-cell sequencing or metagenomic sequencing technologies with uneven sequencing depths. Several non-trivial techniques have been employed to tackle the problems. Instead of using a simple threshold, we use multiple depthrelative thresholds to remove erroneous k-mers in both low-depth and high-depth regions. The technique of local assembly with paired-end information is used to solve the branch problem of low-depth short repeat regions. To speed up the process, an error correction step is conducted to correct reads of high-depth regions that can be aligned to highconfident contigs. Comparison of the performances of IDBA-UD and existing assemblers (Velvet, Velvet-SC, SOAPdenovo and Meta-IDBA) for different datasets, shows that IDBA-UD can reconstruct longer contigs with higher accuracy. AVAILABILITY: The IDBA-UD toolkit is available at our website http://www.cs.hku.hk/~alse/idba_ud

MOTIVATION: Metagenomic binning remains an important topic in metagenomic analysis. Existing unsupervised binning methods for next-generation sequencing (NGS) reads do not perform well on (i) samples with low-abundance species or (ii) samples (even with high abundance) when there are many extremely low-abundance species. These two problems are common for real metagenomic datasets. Binning methods that can solve these problems are desirable. RESULTS: We proposed a two-round binning method (MetaCluster 5.0) that aims at identifying both low-abundance and high-abundance species in the presence of a large amount of noise due to many extremely low-abundance species. In summary, MetaCluster 5.0 uses a filtering strategy to remove noise from the extremely low-abundance species. It separate reads of high-abundance species from those of low-abundance species in two different rounds. To overcome the issue of low coverage for low-abundance species, multiple w values are used to group reads with overlapping w-mers, whereas reads from high-abundance species are grouped with high confidence based on a large w and then binning expands to low-abundance species using a relaxed (shorter) w. Compared to the recent tools, TOSS and MetaCluster 4.0, MetaCluster 5.0 can find more species (especially those with low abundance of say 6× to 10×) and can achieve better sensitivity and specificity using less memory and running time. AVAILABILITY: http://i.cs.hku.hk/~alse/MetaCluster/ CONTACT: [email protected].

MOTIVATION: With the rapid development of next-generation sequencing techniques, metagenomics, also known as environmental genomics, has emerged as an exciting research area that enables us to analyze the microbial environment in which we live. An important step for metagenomic data analysis is the identification and taxonomic characterization of DNA fragments (reads or contigs) resulting from sequencing a sample of mixed species. This step is referred to as 'binning'. Binning algorithms that are based on sequence similarity and sequence composition markers rely heavily on the reference genomes of known microorganisms or phylogenetic markers. Due to the limited availability of reference genomes and the bias and low availability of markers, these algorithms may not be applicable in all cases. Unsupervised binning algorithms which can handle fragments from unknown species provide an alternative approach. However, existing unsupervised binning algorithms only work on datasets either with balanced species abundance ratios or rather different abundance ratios, but not both. RESULTS: In this article, we present MetaCluster 3.0, an integrated binning method based on the unsupervised top--down separation and bottom--up merging strategy, which can bin metagenomic fragments of species with very balanced abundance ratios (say 1:1) to very different abundance ratios (e.g. 1:24) with consistently higher accuracy than existing methods. AVAILABILITY: MetaCluster 3.0 can be downloaded at http://i.cs.hku.hk/~alse/MetaCluster/.

MOTIVATION: Next-generation sequencing techniques allow us to generate reads from a microbial environment in order to analyze the microbial community. However, assembling of a set of mixed reads from different species to form contigs is a bottleneck of metagenomic research. Although there are many assemblers for assembling reads from a single genome, there are no assemblers for assembling reads in metagenomic data without reference genome sequences. Moreover, the performances of these assemblers on metagenomic data are far from satisfactory, because of the existence of common regions in the genomes of subspecies and species, which make the assembly problem much more complicated. RESULTS: We introduce the Meta-IDBA algorithm for assembling reads in metagenomic data, which contain multiple genomes from different species. There are two core steps in Meta-IDBA. It first tries to partition the de Bruijn graph into isolated components of different species based on an important observation. Then, for each component, it captures the slight variants of the genomes of subspecies from the same species by multiple alignments and represents the genome of one species, using a consensus sequence. Comparison of the performances of Meta-IDBA and existing assemblers, such as Velvet and Abyss for different metagenomic datasets shows that Meta-IDBA can reconstruct longer contigs with similar accuracy. AVAILABILITY: Meta-IDBA toolkit is available at our website http://www.cs.hku.hk/~alse/metaidba. CONTACT: [email protected].

Given a set T of n points in ℝ2, a Manhattan network on T is a graph G with the property that for each pair of points in T, G contains a rectilinear path between them of length equal to their distance in the L 1-metric. The minimum Manhattan network problem is to find a Manhattan network of minimum length, i.e., minimizing the total length of the line segments in the network. In this paper, we prove that the decision version of the MMN problem is strongly NP-complete, using a reduction from the well-known 3-SAT problem, which requires a number of gadgets. The gadgets have similar structures, but play different roles in simulating a 3-CNF formula.

The 2D Online Bin Packing is a fundamental problem in Computer Science and the determination of its asymptotic competitive ratio has research attention. In a long series of papers, the lower bound of this ratio has been improved from 1.808, 1.856 to 1.907 and its upper bound reduced from 3.25, 3.0625, 2.8596, 2.7834 to 2.66013. In this article, we rewrite the upper bound record to 2.5545. Our idea for the improvement is as follows. In 2002, Seiden and van Stee [Seiden and van Stee 2003] proposed an elegant algorithm called H ⊗ C , comprised of the Harmonic algorithm H and the Improved Harmonic algorithm C , for the two-dimensional online bin packing problem and proved that the algorithm has an asymptotic competitive ratio of at most 2.66013. Since the best known online algorithm for one-dimensional bin packing is the Super Harmonic algorithm [Seiden 2002], a natural question to ask is: could a better upper bound be achieved by using the Super Harmonic algorithm instead of the Improved Harmonic algorithm? However, as mentioned in Seiden and van Stee [2003], the previous analysis framework does not work. In this article, we give a positive answer for this question. A new upper bound of 2.5545 is obtained for 2-dimensional online bin packing. The main idea is to develop new weighting functions for the Super Harmonic algorithm and propose new techniques to bound the total weight in a rectangular bin.

BACKGROUND: With the rapid development of genome sequencing techniques, traditional research methods based on the isolation and cultivation of microorganisms are being gradually replaced by metagenomics, which is also known as environmental genomics. The first step, which is still a major bottleneck, of metagenomics is the taxonomic characterization of DNA fragments (reads) resulting from sequencing a sample of mixed species. This step is usually referred as "binning". Existing binning methods are based on supervised or semi-supervised approaches which rely heavily on reference genomes of known microorganisms and phylogenetic marker genes. Due to the limited availability of reference genomes and the bias and instability of marker genes, existing binning methods may not be applicable in many cases. RESULTS: In this paper, we present an unsupervised binning method based on the distribution of a carefully selected set of l-mers (substrings of length l in DNA fragments). From our experiments, we show that our method can accurately bin DNA fragments with various lengths and relative species abundance ratios without using any reference and training datasets. Another feature of our method is its error robustness. The binning accuracy decreases by less than 1% when the sequencing error rate increases from 0% to 5%. Note that the typical sequencing error rate of existing commercial sequencing platforms is less than 2%. CONCLUSIONS: We provide a new and effective tool to solve the metagenome binning problem without using any reference datasets or markers information of any known reference genomes (species). The source code of our software tool, the reference genomes of the species for generating the test datasets and the corresponding test datasets are available at http://i.cs.hku.hk/~alse/MetaCluster/.

A rectilinear path between two points p,q∈ R2 is a path connecting p and q with all its line segments horizontal or vertical segments. Furthermore, a Manhattan path between p and q is a rectilinear path with its length exactly dist(p,q):=|p.x-q.x|+|p.y-q.y|.

BACKGROUND: DNA assembling is the problem of determining the nucleotide sequence of a genome from its substrings, called reads. In the experiments, there may be some errors on the reads which affect the performance of the DNA assembly algorithms. Existing algorithms, e.g. ECINDEL and SRCorr, correct the error reads by considering the number of times each length-k substring of the reads appear in the input. They treat those length-k substrings appear at least M times as correct substring and correct the error reads based on these substrings. However, since the threshold M is chosen without any solid theoretical analysis, these algorithms cannot guarantee their performances on error correction. RESULTS: In this paper, we propose a method to calculate the probabilities of false positive and false negative when determining whether a length-k substring is correct using threshold M. Based on this optimal threshold M that minimizes the total errors (false positives and false negatives). Experimental results on both real data and simulated data showed that our calculation is correct and we can reduce the total error substrings by 77.6% and 65.1% when compared to ECINDEL and SRCorr respectively. CONCLUSION: We introduced a method to calculate the probability of false positives and false negatives of the length-k substring using different thresholds. Based on this calculation, we found the optimal threshold to minimize the total error of false positive plus false negative.

In this paper, an optimal linear-time algorithm is presented to solve the haplotype inference problem for pedigree data when there are no recombinations and the pedigree has no mating loops. The approach is based on the use of graphs to capture SNP, Mendelian, and parity constraints of the given pedigree. This representation allows us to capture the constraints as the edges in a graph, rather than as a system of linear equations as in previous approaches. Graph traversals are then used to resolve the parity of these edges, resulting in an optimal running time.

The problem of discovering novel motifs of binding sites is important to the understanding of gene regulatory networks. Motifs are generally represented by matrices (position weight matrix (PWM) or position specific scoring matrix (PSSM) or strings. However, these representations cannot model biological binding sites well because they fail to capture nucleotide interdependence. It has been pointed out by many researchers that the nucleotides of the DNA binding site cannot be treated independently, e.g. the binding sites of zinc finger in proteins. In this paper, a new representation called Scored Position Specific Pattern (SPSP), which is a generalization of the matrix and string representations, is introduced which takes into consideration the dependent occurrences of neighboring nucleotides. Even though the problem of discovering the optimal motif in SPSP representation is proved to be NP-hard, we introduce a heuristic algorithm called SPSP-Finder, which can effectively find optimal motifs in most simulated cases and some real cases for which existing popular motif finding software, such as Weeder, MEME and AlignACE, fail.

Given a mobile telephone network, whose geographical coverage area is divided into cells, phone calls are serviced by assigning frequencies to them, so that no two calls emanating from the same or neighboring cells are assigned the same frequency. Assuming an online arrival of calls and the calls will not terminate, the problem is to minimize the span of frequencies used.

Transparent data replication is a promising technique for improving the system performance of a large distributed network. Transcoding is an important technology which adapts the same multimedia object to diverse mobile appliances; thus, users' requests for a specified version of a multimedia object could be served by a more detailed version cached according to transcoding. Therefore, it is particularly of theoretical and practical necessity to determine the proper version to be cached at each node such that the specified objective is achieved. In this paper, we address the problem of multimedia object placement for transparent data replication. The performance objective is to minimize the total access cost by considering both transmission cost and transcoding cost. We present optimal solutions for different cases for this problem. The performance of the proposed solutions is evaluated with a set of carefully designed simulation experiments for various performance metrics over a wide range of system parameters. The simulation results show that our solution consistently and significantly outperforms comparison solutions in terms of all the performance metrics considered

The problem of finding motifs of binding sites is very important to the understanding of gene regulatory networks. Motifs are generally represented by matrices (PWM or PSSM) or strings. However, these representations cannot model biological binding sites well because they fail to capture nucleotide interdependence. It has been pointed out by many researchers that the nucleotides of the DNA binding site cannot be treated independently, e.g. the binding of zinc finger in proteins. In this paper, a new representation called Scored Position Specific Pattern (SPSP), which is a generalization of the matrix and string representations, is introduced which takes into consideration the dependent occurrences of neighboring nucleotides. Even though the problem of finding the optimal motif in SPSP representation is proved to be NP-hard, we introduce a heuristic algorithm called SPSP-Finder, which can effectively find optimal motifs in most simulated cases and some real cases for which existing popular motif-finding software, such as MEME and AlignACE fail

MOTIVATION: Finding common patterns, motifs, from a set of promoter regions of coregulated genes is an important problem in molecular biology. Most existing motif-finding algorithms consider a set of sequences bound by the transcription factor as the only input. However, we can get better results by considering sequences that are not bound by the transcription factor as an additional input. RESULTS: First, instead of using the simple hyper-geometric analysis, we propose to calculate the likelihood based on a more precise probabilistic analysis which considers motif length, sequence length and number of binding sites as input parameters for testing whether motif is found. Second, we adopt an heuristic algorithm bases on our analysis to find motifs. For the simulated and real datasets, our algorithm ALSE compares favorably against common motif-finding programs such as SeedSearch and MEME in all cases and performs very well, especially when each input sequence contains more than one binding site. AVAILABILITY: ALSE is available for download at the homepage http://alse.cs.hku.hk CONTACT: [email protected].

Finding common patterns, or motifs, from a set of DNA sequences is an important problem in molecular biology. Most motif-discovering algorithms/software require the length of the motif as input. Motivated by the fact that the motifs length is usually unknown in practice, Styczynski et al. introduced the extended (l,d)-motif problem (EMP), where the motifs length is not an input parameter. Unfortunately, the algorithm given by Styczynski et al. to solve EMP can take an unacceptably long time to run, e.g. over 3 months to discover a length-14 motif. This paper makes two main contributions. First, we eliminate another input parameter from EMP: the minimum number of binding sites in the DNA sequences. Fewer input parameters not only reduces the burden of the user, but also may give more realistic/robust results since restrictions on length or on the number of binding sites make little sense when the best motif may not be the longest nor have the largest number of binding sites. Second, we develop an efficient algorithm to solve our redefined problem. The algorithm is also a fast solution for EMP (without any sacrifice to accuracy) making EMP practical.

In this paper, we address present an optimal solution for the problem of multimedia object placement for hybrid transparent data replication. The performance objective is to minimize the total access cost by considering both transmission cost and transcoding cost. The performance of the proposed solution is evaluated with a set of carefully designed simulation experiments for various performance metrics over a wide range of system parameters. The simulation results show that our solution consistently and significantly outperforms comparison solutions in terms of all the performance metrics considered.

This paper addresses the problem of vehicle tracking under a single static, uncalibrated camera without any constraints on the scene or on the motion direction of vehicles. We introduce an explicit contour model, which not only provides a good approximation to the contours of all classes of vehicles but also embeds the contour dynamics in its parameterized template. We integrate the model into a Bayesian framework with multiple cues for vehicle tracking, and evaluate the correctness of a target hypothesis, with the information implied by the shape, by monitoring any conflicts within the hypothesis of every single target as well as between the hypotheses of all targets. We evaluated the proposed method using some real sequences, and demonstrated its effectiveness in tracking vehicles, which have their shape changed significantly while moving on curly, uphills roads.

Transcoding is an important technology which adapts the same multimedia object to diverse mobile appliances; thus, users' requests for a specified version of a multimedia object could be served by a more detailed version cached according to transcoding. Therefore, it is of particularly theoretical and practical necessity to determine the proper versions to be cached at a node such that the specified objective is achieved. In this paper, we address the problem of multimedia object placement. The performance objective is to minimize the total access cost by considering both transmission cost and transcoding cost. We present an optimal dynamic programming-based solution for this problem. The performance of the proposed solutions is evaluated with a set of carefully designed simulation experiments for various performance metrics over a wide range of system parameters. The simulation results show that our solution consistently and significantly outperforms comparison solutions in terms of all the performance metrics considered.

Web caching is an important technology for improving the scalability of Web services. One of the key problems in coordinated enroute Web caching is to compute the locations for storing copies of an object among the enroute caches so that some specified objectives are achieved. In this article, we address this problem for tree networks, and formulate it as a maximization problem. We consider this problem for both unconstrained and constrained cases. The constrained case includes constraints on the cost gain per node and on the number of object copies to be placed. We present dynamic programming-based solutions to this problem for different cases and theoretically show that the solutions are either optimal or convergent to optimal solutions. We derive efficient algorithms that produce these solutions. Based on our mathematical model, we also present a solution to coordinated enroute Web caching for autonomous systems as a natural extension of the solution for tree networks. We implement our algorithms and evaluate our model on different performance metrics through extensive simulation experiments. The implementation results show that our methods outperform the existing algorithms of either coordinated enroute Web caching for linear topology or object placement (replacement) at individual nodes only.

Finding motifs is an important problem in computational biology. Our paper makes two major contributions to this problem. Firstly, we better characterize the types of problem instances that cannot be solved by most existing methods of finding motifs. Secondly, we introduce a different method, which is shown to succeed for various problem instances for which popular existing methods fail.Most existing computational methods to finding motifs are based on the strong-signal model wherein only strong-signal sequences (i.e. those that are known to contain binding sites very similar to the motif) are considered as input and weak-signal sequences (i.e. those do not contain any sub-string similar to the motif) are disregarded.Buhler and Tompa have studied the limitations of methods based on the strong-signal model. They characterized the problem instances for which the motif is unlikely to be found in terms of the number of input (strong-signal) sequences needed under the assumption that each input sequence contains exactly one binding site. They further gave a method to calculate the minimum number of input sequences required.We re-characterize the limitations of the strong-signal model in terms of the minimum total number of binding sites, rather than the minimum number of strong-signal sequences, required to be in the input data set. We use a probability matrix to represent a motif instead of a string pattern to calculate the minimum total number of binding sites required. This new characterization is shown to be more general and realistic.Next, we introduce a more general and realistic energy-based model, which considers all available sequences (including weak-signal sequences) with varying degrees of binding strength to the transcription factors (as measured experimentally by observed color intensity). Given varying degrees of binding strength, our model can consider sequences ranging from those that contain more than one binding site to those that are weak sequences. By treating sequences with different degrees of binding strength differently, we develop a heuristic algorithm called EBMF (Energy-Based Motif Finding algorithm) using an EM-like approach to find motifs under our model. This EBMF algorithm can find motifs for data sets that do not even have the required minimum number of binding sites as previously derived for the strong-signal model. Our algorithm compares favorably with common motif-finding programs AlignACE and MEME, which are based on the strong-signal model. In particular, for some simulated and real data sets, our algorithm finds the motif when both AlignACE and MEME fail to do so.

An open problem is to find all rules that satisfy a minimum confidence but not necessarily a minimum support. Without the support requirement, the classic support-based pruning strategy is inapplicable. The problem demands a confidence-based pruning strategy. In particular, the following monotonicity of confidence, called the universal-existential upward closure, holds: if a rule of size k is confident (for the given minimum confidence), for every other attribute not in the rule, some specialization of size k+1 using the attribute must be confident. Like the support-based pruning, the bottleneck is at the memory that often is too small to store the candidates required for search. We implement this strategy on disk and study its performance.

This paper addresses the problem of efficient routing in unreliable multihop optical networks supported by Wavelength Division Multiplexing (WDM). We first define a new cost model for routing in (optical) WDM networks that is more general than the existing models. Our model takes into consideration not only the cost of wavelength access and conversion but also the delay for queuing signals arriving at different input channels that share the same output channel at the same node. We then propose a set of efficient algorithms in a reliable WDM network on the new cost model for each of the three most important communication patterns-multiple point-to-point routing, multicast, and multiple multicast. Finally, we show how to obtain a set of efficient algorithms in an unreliable WDM network with up to f faulty optical channels and wavelength conversion gates. Our strategy is to first enhance the physical paths constructed by the algorithms for reliable networks to ensure success of fault-tolerant routing, and then to route among the enhanced paths to establish a set of fault-free physical routes to complete the corresponding routing request for each of the communication patterns.

In this paper, we present an $\Theta (n)$ time worst-case deterministic algorithm for finding the constrained Delaunay triangulation and constrained Voronoi diagram of a simple n-sided polygon in the plane. Up to now, only an O(n log n) worst-case deterministic and an O(n) expected time bound have been shown, leaving an O(n) deterministic solution open to conjecture.

Article Free Access Share on A polynomial time solution for labeling a rectilinear map Authors: Chung Keung Poon Dept. of Computer Science, City University of Hong Kong Dept. of Computer Science, City University of Hong KongView Profile , Binhai Zhu Dept. of Computer Science, City University of Hong Kong Dept. of Computer Science, City University of Hong KongView Profile , Franis Chin Dept. of Computer Science, University of Hong Kong Dept. of Computer Science, University of Hong KongView Profile Authors Info & Claims SCG '97: Proceedings of the thirteenth annual symposium on Computational geometryAugust 1997Pages 451–453https://doi.org/10.1145/262839.263079Published:01 August 1997Publication History 9citation277DownloadsMetricsTotal Citations9Total Downloads277Last 12 Months25Last 6 weeks6 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Publisher SiteeReaderPDF

Metamorphosis, or morphing, is the gradual transformation of one shape into another. It generally consists of two subproblems: the correspondence problem and the interpolation problem. This paper presents a solution to the interpolation problem of transforming one polyhedral model into another. It is an extension of the intrinsic shape interpolation scheme (T. W. Sederberg, P. Gao, G. Wang and H. Mu, ‘2-D shape blending: an intrinsic solution to the vertex path problem, SIGGRAPH '93, pp. 15–18.) for 2D polygons. Rather than considering a polyhedron as a set of independent points or faces, our solution treats a polyhedron as a graph representing the interrelations between faces. Intrinsic shape parameters, such as dihedral angles and edge lengths that interrelate the vertices and faces in the two graphs, are used for interpolation. This approach produces more satisfactory results than the linear or cubic curve paths would, and is translation and rotation invariant. © 1997 by John Wiley & Sons, Ltd.

Block matching algorithms (BMAs) are often employed for motion estimation (ME) in video coding. Most conventional fast BMAs treat the ME problem as an optimization problem and suffer heavily from the problem of being trapped at local minima. The full search algorithm (FS), on the other hand, is very time-consuming. Few of them makes use of the information inherent in the images explicitly. We propose a new ME algorithm which can reduce the search range while guaranteeing global optimality in most cases, making use of the edge features. Microblock visual patterns are designed to extract edge information to guide block matching: searching is only carried out at places where the real match most likely happens. The motion field subsampling technique is further employed to get a hierarchical algorithm, which can further double the speed. The proposed algorithms obtain speeds about ten times faster than that of FS with comparable prediction quality.

Magnetic Ink Character Recognition (MICR) technology has widely been used for processing bank checks. Since the MICR character set is a special type font, and the ink is also readable by human being, optical approach can also be used. This report will describe the design of a low-cost, but highly accurate, microprocessor-based optical character recognition (OCR) check reader. The performance of our OCR reader is affected by a number of factors, mainly the noise generated by the lens system and the colour image at the check background. In this paper we describe how our software solution can alleviate these problems. As speed is another concern, special attention is paid to the design of recognition algorithm, such as the avoidance of floating point arithmetics, hardware limitations, etc.

We study the problem of running full binary tree based algorithms on a hypercube with faulty nodes. The key to this problem is to devise a method for embedding a full binary tree into the faulty hypercube. Based on a novel embedding strategy, we present two results for embedding an (n-1) tree fa full binary tree with 2/sup n-1/ nodes) into an n-cube (a hypercube with 2/sup n/ nodes) with unit dilation and load. For the problem where the root of the tree must be mapped to a specified hypercube node (specified root embedding problem), we show that up to n-2 (node or edge) faults can be tolerated. This result is optimal in the following sense: 1) it is time-optimal, 2) (n-1)-tree is the largest fall binary tree that can be embedded in an n-cube, and 3) n-2 faults Is the maximum number of worst-case faults that can be tolerated in the specified root problem. Furthermore, we also show that any algorithm for this problem cannot be totally recursive in nature. For the problem where the root can be mapped to any nonfaulty hypercube node (variable root embedding problem), we show that up to 2n-3-[log n] faults can be tolerated. Thus we have improved upon the previous result of n-1-[log n]. In addition, we show that the algorithm for the variable root embedding problem is optimal within a class of algorithms called recursive embedding algorithms as far as the number of tolerable faults is concerned. Finally, we show that when an O(1spl radic/n) fraction of nodes in the hypercube are faulty, it is not always possible to have an O(1)-load variable root embedding no matter how large the dilation is.>

The problem of electing a leader in a dynamic ring in which processors are permitted to fail and recover during election is discussed. It is shown that theta (n log n+k/sub r/) messages, counting only messages sent by functional processors, are necessary and sufficient for dynamic ring election, where k/sub r/ is the number of processor recoveries experienced.>

The authors parallelize the embedding strategy for mapping any two-dimensional grid into its optimal hypercube with minimal dilation. The parallelization allows each hypercube node to independently determine, in constant time, which grid node it will simulate and the communication paths it will take to reach the hypercube nodes that simulate its grid-neighbors. The paths between grid-neighbors are chosen in such a way as to curb the congestion at each hypercube node and across each hypercube edge. Explicity, the node congestion for the embedding is at most 6, one above optimal, while the edge congestion is at most 5.>

A novel class of generating kernels for image pyramids is introduced. When these kernels are convolved with intensity functions of images, continuous piecewise surfaces composed of polynomial tensor products are fitted to the intensity functions. The fittings are optimal in the sense that the mean square error between them and the original intensity functions is minimized. Two members of the class are introduced, and symmetry, normalization, unimodality, and equal contribution properties are proved. These kernels possess attractive properties such as small window size, fast inverse transformation, and minimum error. Experiments show that they compare favorably with existing ones in terms of mean square error.>

The pinwheel is a hard-real-time scheduling problem for scheduling satellite ground stations to service a number of satellites without data loss. Given a multiset of positive integers (instance) A=(a/sub 1/, . . . a/sub n/), the problem is to find an infinite sequence (schedule) of symbols from (1,2, . . . n) such that there is at least one symbol i within any interval of a/sub i/ symbols (slots). Not all instances A can be scheduled; for example, no 'successful' schedule exists for instances whose density is larger than 1. It has been shown that any instance whose density is less than 2/3 can always be scheduled. Two new schedulers are proposed which improve this 2/3 result to a new 0.7 density threshold. These two schedulers can be viewed as a generalization of the previously known schedulers, i.e. they can handle a larger class of pinwheel instances including all instances schedulable by the previously known techniques.>

A distributed algorithm is presented that constructs the minimum-weight spanning tree of an undirected connected graph with distinct node identities. Initially, each node knows only the weight of each of its adjacent edges. When the algorithm terminates, each node knows which of its adjacent edges are edges of the tree. For a graph with n nodes and e edges, the total number of messages required by this algorithm is at most $5n \log n+2e$, where each message contains at most one edge weight plus $3+\log n$ bits. Although the algorithm presented here has the same message complexity as the previously known algorithm due to Gallager, Humblet, and Spira [ACM Trans. Programming Language and Systems, 5 (1983), pp. 66–77], the time complexity of the algorithm presented improves from Gallager’s $O(n \log n)$ to $O(n \log ^* n)$ time units, where $\log ^* k$ is the number of times the log function must be applied to k to obtain a result less than or equal to one. A worst case of $\Omega (n \log ^* n)$ is also possible. In addition, when the network is synchronous, the algorithm presented is modified further to solve the same problem with the same message complexity but in $O(n)$ time.

The following graph-embedding question is addressed: given a two-dimensional grid and the smallest hypercube with at least as many nodes as grid points, how can one assign grid points to hypercube nodes (with at most one grid point per node) so as to keep grid neighbors near each other in the cube? An embedding scheme for an infinite class of two-dimensional grids is given that keeps grid neighbors within a distance of two apart.>

We consider the failure atomicity problem of distributed transactions in conjunction with the maximization of database availability. We propose a new information-based model for the distributed transaction-execution, which explicitly expresses the information at each stage during a protocol. In addition to rederiving certain existing results, we prove a fundamental relation among the site failures and the network partitioning. We propose a realistic model for site failures under which we show that the costs of commit and termination protocols can be greatly reduced. Finally, we explore the possible recovery strategies for a failed site and show how they are improved under our site failure model.

The basic inference problem is defined as follows: For a finite set X = { x i , … , x n }, we wish to infer properties of elements of X on the basis of sets of "queries" regarding subsets of X . By restricting these queries to statistical queries, the statistical database (SDB) security problem is obtained. The security problem for the SDB is to limit the use of the SDB so that only statistical information is available and no sequence of queries is sufficient to infer protected information about any individual. When such information is obtained the SDB is said to be compromised. In this paper, two applications concerning the security of the SDB are considered: On-line application . The queries are answered one by one in sequence and it is necessary to determine whether the SDB is compromised if a new query is answered. Off-line application . All queries are available at the same time and it is necessary to determine the maximum subset of queries to be answered without compromising the SDB. The complexity of these two applications, when the set of queries consists of (a) a single type of SUM query, (b) a single type of MAX/MIN query, (c) mixed types of MAX and MIN queries, (d) mixed types of SUM and MAX/MIN queries, and (e) mixed types of SUM, MAX, and MIN queries, is studied. Efficient algorithms are designed for some of these situations while others are shown to be NP-hard.

We address the problem of maintaining the distributed database consistency in presence of failures while maximizing the database availability. Network Partitioning is a failure which partitions the distributed system into a number of parts, no part being able to communicate with any other. Formalizations of various notions in this context are developed and two measures for the performances of protocols in presence of a network partitioning are introduced. A general optimality theory is developed for two classes of protocols—centralized and decentralized. Optimal protocols are produced in all cases.

A distributed algorithm is presented that constructs the minimum-weight spanning tree of an undirected connected graph with distinct edge weights and distinct node identities. Initially each node knows only the weight of each of its adjacent edges. When the algorithm terminates, each node knows which of its adjacent edges are edges of the tree. For a graph with n nodes and e edges, the total number of messages required by our algorithm is at most 5nlogn+2e, and each message contains at most one edge weight or one node identity plus 3+logn bits. Although our algorithm has the same message complexity as the previously known algorithm by Gallager et al., the time complexity of our algorithm takes at most O(nG(n))+ time units, an improvement from Gallager's O(nlogn)+. A worst case O(nG(n)) is also possible.

In this paper, we present efficient parallel algorithms for the following graph problems: finding the lowest common ancestors for vertex pairs of a directed tree; finding all fundamental cycles, a directed spanning forest, all bridges, all bridge-connected components, all separation vertices, all biconnected components, and testing the biconnectivity of an undirected graph. All these algorithms achieve the $O(\lg ^2 n)$ time bound, with the first two algorithms using $n\lceil n /\lg n\rceil $ processors and the remaining algorithms using $n\lceil n/\lg ^2 n \rceil $ processors. In all cases, our algorithms are better than the previously known algorithms and in most cases reduce the number of processors used by a factor of $n\lg n$. Moreover, our algorithms are optimal with respect to the time-processor product for dense graphs, with the exception of the first two algorithms. The machine model we use is the PRAM which is a SIMD model allowing simultaneous reads but not simultaneous writes to the same memory location.

Commit protocols guarantee the consistency of distributed databases in absence of any failures. A commit protocol is resilient to a class of failures if it is possible to guarantee that a) databases at all operational sites in presence of these failures are consistent and b) other sites can be recovered consistently with these sites when the failure is repaired. Such a commit protocol is called nonblocking if no operational site needs to wait on a transaction which is incomplete at the time of the failure. It is known that no nonblocking commit protocol resilient to network partitioning exists. In this paper, the possible termination protocols of commit protocols are studied in the context of network partitioning. A formal model for termination protocols is introduced and a general logical interpretation of termination protocols is presented. The model makes use of all the information that is available in a component of the partition --- namely, the constituent sites and their respective states at the time of partition. Optimality measures for the termination protocols in terms of the number of waiting components and average number of waiting sites are introduced and protocols optimal under these measures are produced for all the possible centralized and decentralized commit protocols. It is proved that quorum-based termination protocols indeed perform very well in the presence of network partitioning. If the central site(s) is reliable, we can prove that centralized commit protocols indeed perform better than all decentralized ones. Thus, the general preference for centralized commit protocols is justified.

Two planar geometric problems relating to a convex n-gon P and a simple nonconvex m-gon Q are considered.

It is shown that the problem of scheduling a two-processor n-job open shop nonpreemptively in order to minimize mean flow time is NP-complete even if input length is measured by the sum of the task lengths. The proof is similar in approach to that used by Garey, Johnson and Sethi to show NP-completeness of the two-processor flow shop mean flow problem. We assume previous results from their paper where possible and concentrate on those elements of the proof that are distinct from theirs. In addition, bounds are derived for the mean flow times of arbitrary and shortest processing time (SPT) first schedules for m-processor n-job systems in terms of the mean flow time of an optimal schedule.

A statistical database (SDB) may be defined as an ordinary database with the capability of providing statistical information to user queries. The security problem for the SDB is to limit the use of the SDB so(that only statistical information is available and no sequence of queries is sufficient to infer protected information about any individual. When such information is obtained, the SDB is said to be compromised.

The security problem of a statistical database is to limit database use so that no private information is deducible. This paper discusses the advantages of using a Question-Answering System and a security kernel to enhance the security constraints at the conceptual model level. An SDB design with the goal of helping the DBA in specifying certain security contraints is proposed.

An open problem by Graham is solved.The problem considered is that of scheduling a set of n independent tasks nonpreemptively on m identical processors to minimize finish time.Let a.,o and ~o be the finish times of an optimal schedule and an arbitrary list schedule, respectively.The worst possible behavior of o~/w0 for tasks with similar execution times is investigated. KEY WORDS AND PHRASES: minimal length

Scheduling problems are considered for a common kind of flow shop where the execuuon Ume for certain tasks in each job is always longer or shorter than that for the other tasks NP-completeness ts shown for some cases, stmple opttmal algorithms are found for the others, and bounds are gtven for the worst cases. KEY WORDS AND PHRASES Job schedulmg, flow-

The security problem of a statistical database is to limit the use of the database so that no sequence of statistical queries is sufficient to deduce confidential or private information. In this paper it is suggested that the problem be investigated at the conceptual data model level. The design of a statistical database should utilize a statistical security management facility to enforce the security constraints at the conceptual model level. Information revealed to users is well defined in the sense that it can at most be reduced to nondecomposable information involving a group of individuals. In addition, the design also takes into consideration means of storing the query information for auditing purposes, changes in the database, users' knowledge, and some security measures.

This paper presents two sorting algorithms on the uniform ladder (a new storage device based on charged coupled devices, or magnetic bubbles implementation, proposed by Chen et al.). It is assumed that control and comparison timings are negligible when compared to the relatively slow bubble movements. The first algorithm (Algorithm 1) enables the sorting process on a single ladder to be completely embedded in the input/output time (whereas Chen's algorithm (SLISO) has a 20 percent unoverlapped sorting time in the load-sort-unload process). When one ladder cannot accommodate all the input records and two or more ladders are needed, Algorithm 2 attains a negligible unoverlapped sorting time (which can be removed with a minor modification in the system hardware and hence in Algorithm 2). In comparison, Algorithm 2 obviates the need for explicit merging of the ladders, which is required in Chen's algorithm (MLISO). This implies that unlike the MLISO scheme, ladders are not tied up for merging, and can be recycled once their contents are outputted. Therefore, in a real processing environment, the number of ladders required by Algorithm 2 may even be less than the theoretical minimum which can be attained by the MLISO scheme.

The security problem of statistical databases containing anonymous but individual records which may be evaluated by queries about sums and averages is considered. A model, more realistic than the previous ones, is proposed, in which nonexisting records for some keys can be allowed. Under the assumption that the system protects the individual's information by the well-known technique which avoids publishing summaries with small counts, several properties about the system and a necessary and sufficient condition for compromising the database have been derived. The minimum number of queries needed to compromise the database is also discussed.

We study a number of protection schemes with respect to their effectiveness in providing security for statistical data bases, their feasibility and their ease of implementation. A new method is proposed, and two implementations presented. One implementation guarantees perfect protection against leakage of information about individuals; the other requires very little implementation effort, but has a small probability of leakage.

The partial fraction expansion problem and its inverse are studied and it is shown that these two problems can be solved in $O(N\log^2N)$ steps for those rational functions with N simple poles, $O(N\log N)$ steps for those with a single multiple pole of order N and $O(N\log N(\log n+1))$ steps for the general multiple pole case, where N is the degree of the denominator polynomial and n is the number of distinct poles. We further show that the evaluation of a rational function and its derivatives at a given point can be done more efficiently than previously known. Previous known algorithms for the partial fraction problem and its inverse require $O(n^{2})$ steps.

It is shown in this paper that the evaluation and interpolation problems corresponding to a set of points, $\{ x_i \} _{i = 0}^{n - 1} $, with $(c_i - 1)$ higher derivatives at each $x_i $ such that $\sum _{i = 1}^{n - 1} c_i = N$, can be solved in $O([N\log N][(\log n) + 1])$ steps.l This upper bound matches perfectly with the known upper bounds of the two extreme cases, which are $O(N\log ^2 N)$ and $O(N\log N)$ steps when $n = N$ and $n = 1$, respectively.