930169
Sequencing-by-hybridization at the information-theory bound: an optimal algorithm
In a recent paper [PFU99) we have introduced a novel probing scheme for DNA sequencing by hybridization (SBH). The new gapped-probe scheme combines natural and universal bases in a well defined periodic pattern. It was shown in [PFU99] that the performance of the gapped-probe scheme (in terms of the length of a sequence that can be uniquely reconstructed using a given library size of probes) is significantly better than the standard scheme based on oligomer probes.
In this paper we present and analyze a new, more powerful, sequencing algorithm for the gapped-probe scheme. We prove that the new algorithm exploits the full potential of the SBH technology with high-confidence performance, that comes within a small constant factor (about 2) of the information-theory bound. Moreover, this performance is achieved while maintaining running time linear in the target sequence length.
41033149
Parallel Restructuring and Evaluation of Expressions
Abstract In this paper we describe a boolean network of size O ( N 2 log N ) which accepts a fully parenthesized N -variable expression over a given semiring and produces its value in O (log N ) time. The network consists of two components: a preprocessor and a universal evaluator. The preprocessor computes the destinations of the expression terms and routes them to the correct input terminals of the universal evaluator.
1765683
The Role of Arithmetic in Fast Parallel Matrix Inversion
Abstract. In the last two decades several NC algorithms for solving basic linear algebraic problems have appeared in the literature. This interest was clearly motivated by the emergence of a parallel computing technology and by the wide applicability of matrix computations. The traditionally adopted computation model, however, ignores the arithmetic aspects of the applications, and no analysis is currently available demonstrating the concrete feasibility of many of the known fast methods. In this paper we give strong evidence to the contrary, on the sole basis of the issue of robustness, indicating that some theoretically brilliant solutions fail the severe test of the ``Engineering of Algorithms.'' We perform a comparative analysis of several well-known numerical matrix inversion algorithms under both fixed- and variable-precision models of arithmetic. We show that, for most methods investigated, a typical input leads to poor numerical performance, and that in the exact-arithmetic setting no benefit derives from conditions usually deemed favorable in standard scientific computing. Under these circumstances, the only algorithm admitting sufficiently accurate NC implementations is Newton's iterative method, and the word size required to guarantee worst-case correctness appears to be the critical complexity measure. Our analysis also accounts for the observed instability of the considered superfast methods when implemented with the same floating-point arithmetic that is perfectly adequate for the fixed-precision approach.
1952504
Data structures and algorithms for the string statistics problem
Given a textstringx of lengthn, theMinimal Augmented Suffix Tree T (x) ofx is a digital-search index that returns, for anyquery stringw and in a number of comparisons bounded by the length ofw, the maximum number of nonoverlapping occurrences ofw inx. It is shown that, denoting the length ofx byn, T(x) can be built in timeO(n log2n) and spaceO(n logn), off-line on a RAM.
18686062
Sequencing-by-hybridization revisited: the analog-spectrum proposal
All published approaches to DNA sequencing by hybridization (SBH) consist of the biochemical acquisition of the spectrum of a target sequence (the set of its subsequences conforming to a given probing pattern) followed by the algorithmic reconstruction of the sequence from its spectrum. In the "standard" or "uniform" approach, the probing pattern is a string of length L and the length of reliably reconstructible sequences is known to be m/sub len/ = O(2/sup L/). For a fixed microarray area, higher sequencing performance can be achieved by inserting nonprobing gaps ("wild-cards") in the probing pattern. The reconstruction, however, must cope with the emergence of fooling probes due to the gaps and algorithmic failure occurs when the spectrum becomes too densely populated, although we can achieve m/sub comp/ = O(4/sup L/). Despite the combinatorial success of gapped probing, all current approaches are based on a biochemically unrealistic spectrum-acquisition model (digital-spectrum). The reality of hybridization is much more complex. Departing from the conventional model, in this paper, we propose an alternative, called the analog-spectrum model, which more closely reflects the biochemical process. This novel modeling reestablishes probe length as the performance-governing factor, adopting "semidegenerate bases" as suitable emulators of currently inadequate universal bases. One important conclusion is that accurate biochemical measurements are pivotal to the success of SBH. The theoretical proposal presented in this paper should be a convincing stimulus for the needed biotechnological work.
5066584
Widest-Corridor Problems
A k-dense corridor through a finite set, S, of n points in the plane is the open region of the plane that is bounded by two parallel lines that intersect the convex hull of S and such that the region contains k points of S. The problem of finding a widest k-dense corridor arises in robot motion-planning. In this paper, efficient solutions are presented for several versions of this problem. Results include: two algorithms for finding widest k-dense corridors for any k, an algorithm to dynamically maintain a widest empty corridor under online insertions and deletions in S, an algorithm to find a widest (n - 1)-dense closed corridor, and a widest empty corridor algorithm for polygonal obstacles. The techniques used are based on geometric duality and on efficient searching in the convex layers of a point-set.
62769560
Three layers are enough
In this paper we show that any channel routing problem of density d involving two-terminal nets can always be solved in the knock-knee mode in a channel of width equal the density d with three conducting layers. An algorithm is described which produces a layout of n nets with the following properties: (i) it has minimal width d; (ii) it can be realized with three layers; (iii) it has at most 3n vias; (iv) any two wires share at most four grid points.
7564242
Area-time lower-bound techniques with applications to sorting
Thearea-time complexity of VLSI computations is constrained by the flow and the storage of information in the two-dimensional chip. We study here the information exchanged across the boundary of the cells of asquare-tessellation of the layout. When the information exchange is due to thefunctional dependence between variables respectively input and output on opposite sides of a cell boundary, lower bounds are obtained on theAT2 measure (which subsume bisection bounds as a special case). When information exchange is due to thestorage saturation of the tessellation cells, a new type of lower bound is obtained on theAT measure.In the above arguments, information is essentially viewed as a fluid whose flow is uniquely constrained by the available bandwidth. However, in some computations, the flow is kept below capacity by the necessity to transform information before an output is produced. We call this mechanismcomputational friction and show that it implies lower bounds on theAT/logA measure.Regimes corresponding to each of the three mechanisms described above can appear by varying the problem parameters, as we shall illustrate by analyzing the problem of sortingn keys each ofk bits, for whichAT2,AT, andAT/logA bounds are derived. Each bound is interesting, since it dominates the other two in a suitable range of key lengths and computations times.
12582971
Stabbing line segments
An algorithm for the geometric problem of determining a line (called a stabbing line) which intersects each ofn given line segments in the plane is presented. As a matter of fact, the algorithm computes a description of all stabbing lines. A purely geometric fact is proved which infers that this description requiresO(n) space to be specified. Our algorithm computes it inO(n logn) time which is optimal in the worst case.Using the description of the stabbing lines, we are able to decide inO(logn) time whether or not a specified line is a stabbing line. Finally, the problem of maintaining the description of all stabbing lines while inserting and deleting line segments is addressed.
2327802
Robust proximity queries: an illustration of degree-driven algorithm design
In the context of methodologies intended to confer robustness to geometric algo- rithms, we elaborate on the exact-computation paradigm and formalize the notion of degree of a geometric algorithm as a worst-case quantication of the precision (number of bits) to which arith- metic calculation have to be executed in order to guarantee topological correctness. We also propose a formalism for the expeditious evaluation of algorithmic degree. As an application of this paradigm and an illustration of our general approach where algorithm design is driven also by the degree, we consider the important classical problem of proximity queries in two and three dimensions and develop a new technique for the ecient and robust execution of such queries based on an implicit representation of Voronoi diagrams. Our new technique oers both low degree and fast query time and for 2D queries is optimal with respect to both cost measures of the paradigm, asymptotic number of operations, and arithmetic degree.