This paper describes a fast and fully automated dictionary based approach to gene annotation and exon prediction. Two dictionaries are constructed, one from the nonredundant protein OWL database and the other from the dbEST database. These dictionaries are used to obtain O(1) time lookups of tuples in the dictionaries (4 tuples for the OWL database and 11 tuples for the \ndbEST database). These tuples can be used to rapidly find the longest matches at every position in an input sequence to the database sequences. Such matches provide very useful information pertaining to locating common segments between exons, alternative splice sites, and frequency data of long tuples for statistical purposes. These dictionaries also provide the basis for both homology determination, and statistical approaches to exon prediction. For instance, using the OWL protein database on a benchmark test set of 130 genes, and after removing sequences from the database with exact amino acid homology to genes in our test set, we find 88% of coding nucleotides, and 99% of our predictions of coding nucleotides are correct. Also, 81% of coding exons are predicted exactly, while 82% of our predictions of exons agree exactly with the published annotation of their genes.

We investigate a model of gate failure for Boolean circuits in which a faulty gate is restricted to output one of its input values. For some types of gates, the model (which we call the short-circuit model of gate failure) is weaker than the traditional von Neumann model where faulty gates always output precisely the wrong value. Our model has the advantage that it allows us to design Boolean circuits that can tolerate worst-case faults, as well as circuits that have arbitrarily high success probability in the case of random faults. Moreover, the short-circuit model captures a particular type of fault that commonly appears in practice, and it suggests a simple method for performing post-test alterations to circuits that have more severe types of faults. A variety of bounds on the size of fault-tolerant circuits are proved in the paper. Perhaps, the most important is a proof that any k-fault-tolerant circuit for any input-sensitive function using any type of gates (even arbitrarily powerful, multiple-input gates) must have size at least /spl Omega/(k log k/log log k). Obtaining a tight bound on the size of a circuit for computing the AND of two values if up to k of the gates are faulty is one of the central questions left open in the paper.>

It is proved that every strongly connected directed graph with n nodes and at least $\lfloor ( n + 1 )^2 /4 \rfloor $ edges must contain an even cycle. This is best possible, and the structure of extremal graphs is discussed.

A family of sets has the (p, q) property if among arty p members of the family some This extends Helly's Theorem and settles an old problem of Hadwiger and Debrunner.

Given n points in the plane, a crossing family is a collection of line segments, each joining two of the points, such that any two line segments intersect internally.We show that any n points in general position possess a crossing family of size at least ~, and describe an O(n log n)-time algorithm for finding one.

A connected graph having large minimum vertex degree must have a spanning tree with many leaves. In particular, let $l( n,k )$ be the maximum integer m such that every connected n-vertex graph with minimum degree at least k has a spanning tree with at least m leaves. Then $l( n,3 )\geqq n/4 + 2, l( n,4 )\geqq ( 2n + 8 )/5,$ and $l( n,k )\leqq n - 3\lfloor n/( k + 1 ) \rfloor + 2$ for all k. The lower bounds are proved by an algorithm that constructs a spanning tree with at least the desired number of leaves. Finally, $l( n,k )\geqq ( 1 - b \ln k/k )n$ for large k, again proved algorithmically, where b is any constant exceeding 2.5.

An $O( m\alpha ( n ) + n )$ time algorithm is given for finding row-maxima and minima in totally monotone partial $n \times n$ matrices. As a result, faster algorithms are obtained for some optimization problems concerning distance and visibility between vertices of two convex polygons. Also shown is how the algorithm can be modified to give an $O( n \alpha ( n ) )$ algorithm for a class of dynamic programming problems satisfying convex quadrangle inequalities. This results in faster algorithms for a number of problems arising in molecular biology, speech recognition, and geology.

In this note, an $O ( | V |k )$ algorithm is described for determining whether an interval graph on $| V |$ vertices has a bandwidth less than or equal to a given integer k. While the algorithm is not the first to resolve this problem, it does admit a shorter proof of its correctness than a previous algorithm of the same complexity due to Kratsch (Information and Computation, 74 (1987), pp. 140–158).

Given a graph G and $d \in \mathbb{Z}^+$, the pair labelling number, $r(G,d)$, is defined to be the minimum n such that each vertex in G can be assigned a pair of numbers from $\{ 1, \cdots ,n\} $ in such a way that any two numbers used at adjacent vertices differ by at least d. A question of Roberts’ is answered by determining all possible values of $r(G,d)$ given the chromatic number of G. The answer follows by determining the chromatic number of the graph that has pairs of integers as vertices and edges joining pairs that are distance at least d apart. For general $t \in \mathbb{Z}^+$, the analogous questions for t-sets instead of pairs are considered. A solution for general t is conjectured which, for $d = 1$, reduces to Lovász's theorem on Kneser graphs.

This paper addresses the question: how large can a collection of divisors of a square free integer be, if any pair x and y in the collection so that x divides y, has $y/x$ congruent to $1\bmod p$? It is shown that if n has as many prime factors congruent to k and $1/k\bmod p$, and an even number congruent to $p - 1$, then the sum of the largest two binomial coefficients on n is an upper bound to the size of the collection. Asymptotic bounds are also obtained.

We provide an algorithm which solves the following problem: given a polygon with edges parallel to the x and y axes, which is convex in the y direction, find a minimum size collection of rectangles, which cover the polygon and are contained within it. The algorithm is quadratic in the number of vertices of the polygon. Our method also yields a new proof of a recent duality theorem equating minimum size rectangle covers to maximum size sets of independent points in the polygon.

In this extended abstract, we present several new layouts for the shuffle-exchange graph, including one which requires only 0(n2/log2n) area. The optimal layout is described and analyzed in section 3. The analysis is heavily dependent on several combinatorial results which we state in section 2 and prove in the appendix. The other layouts are described in section 4. Although these layouts are not asymptotically optimal (most require 0(n2/log3/2n) area), the theory behind their development is interesting and may eventually lead to good practical layouts as well as other asymptotically optimal layouts.

We consider the problem of identifying an unknown value xε{1,2,...,n} using only comparisons of x to constants when as many as E of 'the comparisons may receive erroneous answers. For a continuous analogue of this problem we show that there is a unique strategy that is optimal in the worst case. This strategy for the continuous problem is then shown to yield a strategy for the original discrete problem that uses log2n+E.log2log2n+O(E.log2E) comparisons in the worst case. This number is shown to be optimal even if arbitrary “Yes-No” questions are allowed.

Bin packing and dynamic allocation problems hold an important place both in theoretical computer science and in practical issues arising in computer applications and operations research. While major analytic advances have been made for the 1-dimension case, optimal results for 2-dimensional problems have been elusive. As a model for analysis of various multidimensional bin packing and cutting stock problems, we consider the following question. Let be an arbitrary finite family of squares of total area at most unity; what is the smallest rectangle into which any such family can be packed without overlap? We answer this with the following optimal result: 1) any unit family can be packed into a rectangle with sides 2/√3 and √2; 2) any other rectangle with this packing property has larger area. The proof of this is rather lengthy and technical. We therefore restrict this presentation to a general discussion of the methods used and an outline of the major cases together with some specific examples.

Abstract We consider the cost allocation problem faced by a large scale supplier (the telephone company) who rents telephone circuits to its customers. A number of possible allocation rate structures are analyzed, as are some of the criteria that they may be measured by. Finally, we draw conclusions and make recommendations for cost allocation in these circumstances.

The purpose of this note is to settle a conjecture on perfect elimination digraphs raised by Haskins and Rose in this journal, and to make some remarks that illuminate the nature of digraphs satisfying the conditions defined by them.

Abstract The problem of allocating cost in a spanning tree network is considered. A number of possible schemes are surveyed, and critically analyzed. Methods are suggested that are preferred given different emphases among the criteria for such a function.

Abstract In this paper we provide a simple algorithm for constructing an n‐ (vertex) connected graph with no multiple edges or loops having degree sequence satisfying the conditions indicated below. We prove these to be necessary and sufficient for the existence of such a graph. Our algorithm consists of constructing the graph in stages. An explicit construction is given if all degrees are n or n+1. Otherwise we choose a vertex with either the largest or smallest degree and connect it with a set of the remaining vertices having largest degrees, leaving a residual degree sequence for the rest of the graph which later can then be constructed by iteration. We connect the vertex of smallest degree above if the residual degrees after its connection are all at least n. Otherwise we connect the vertex of largest degree. The conditions on the degree sequence are that it must be realizable by a graph, all degrees must be at least n, and the number of edges which can avoid touching the n‐1 largest degree vertices are sufficient to form a tree among the other vertices.

Abstract In this paper an algorithm is presented for solving a certain class of multi‐commodity flow problems. The class of problems considered consist of integer capacity multi‐source and multi‐sink problems for which each node is a source of sink for all but at most one commodity. The algorithm is described in the case that any edge connecting a source and sink of a commodity can be used for flow of that commodity.