The all scores matrix of a grid graph is a matrix containing the optimal scores of paths from every vertex on the first row of the graph to every vertex on the last row. This matrix is commonly used to solve diverse string comparison problems. All scores matrices have the Monge property, and this was exploited by previous works that used all scores matrices for solving various problems. In this paper, we study an extension of grid graphs that contain an additional set of edges, called bridges. Our main result is to show several properties of the all scores matrices of such graphs. We also give an O(r(nm + n2)) time algorithm for constructing the all scores matrix of an m × n grid graph with r bridges.

Two equal-length strings, or two equal-sized two-dimensional texts, parameterize match ( p-match ) if there is a one-one mapping (relative to the alphabet) of their characters. Two-dimensional parameterized matching is the task of finding all m × m substrings of an n × n text that p-match an m × m pattern. This models searching for color images with changing of color maps, for example. We present two algorithms that solve the two-dimensional parameterized matching problem. The time complexities of our algorithms are O ( n 2 log 2 m ) and O ( n 2 + m 2.5 polylog( m )). Our algorithms are faster than the O ( n 2 m log 2 m log log m ) time algorithm for this problem of Amir et al. [2006]. A key step in both of our algorithms is to count the number of distinct characters in every m × m substring of an n × n string. We show how to solve this problem in O ( n 2 ) time. This result may be of independent interest.

In the k -matches problem, we are given a pattern and a text, and for each text location, the desired output consists of all aligned matching characters if there are k or fewer of them, and any k aligned matching characters if there are more than k of them. This problem is one of several string matching problems that seek not only to find where the pattern matches the text under different “match” definitions, but also to provide witnesses to the match. Other such problems include k -aligned ones, k -witnesses, and k -mismatches. In addition, the solutions to several other string matching problems rely on the efficient solutions of the witness finding problems. In this article we provide a general method for solving such witness finding problems efficiently. We do so by casting the problem as a generalization of group testing, which we then solve by a process we call peeling . Using this general framework we obtain improved results for all of the problems mentioned. We also show that our method also solves a couple of problems outside the pattern matching domain.

We study a model of graph related formulae that we call the constraint-graph model. A constraint-graph is a labeled multi-graph (a graph where loops and parallel edges are allowed), where each edge e is labeled by a distinct Boolean variable and every vertex is associated with a Boolean function over the variables that label its adjacent edges. A Boolean assignment to the variables satisfies the constraint graph if it satisfies every vertex function. We associate with a constraint-graph G the property that consists of all assignments satisfying G, denoted SAT(G). We show that the above model is quite general. That is, for every property of strings P there exists a property of constraint-graphs PGsuch that P is testable using q queries if and only if PGis thus testable. In addition, we present a large family of constraint-graphs for which SAT(G) is testable with constant number of queries. As an implication of this, we infer the testability of some edge coloring problems (e.g. the property of two coloring of the edges in which every node is adjacent to at least one vertex of each color). Another implication is that every property of Boolean strings that can be represented by a read-twice CNF formula is testable. We note that this is the best possible in terms of the number of occurrences of every variable in a formula.

Sequencing by Hybridization is a method for reconstructing a DNA sequence based on its k-mer content. This content, called the spectrum of the sequence, can be obtained from hybridization with a universal DNA chip. However, even with a sequencing chip containing all 4 9 9-mers and assuming no hybridization errors, only about 400 bases-long sequences can be reconstructed unambiguously. Drmanac et al. suggested sequencing long DNA targets by obtaining spectra of many short overlapping fragments of the target, inferring their relative positions along the target and then computing spectra of subfragments that are short enough to be uniquely recoverable. Drmanac et al. do not treat the realistic case of errors in the hybridization process. In this paper we study the effect of such errors. We show that the probability of ambiguous reconstruction in the presence of (false negative) errors is close to the probability in the errorless case. More precisely, the ratio between these probabilities is 1 + O(p/(1 − p) 4 · 1/d) where d is the average length of subfragments, and p is the probability of a false negative. We also obtain lower and upper bounds for the probability of unambiguous reconstruction based on errorless spectrum. For realistic chip sizes, these bounds are tighter than those given by Arratia et al. Finally, we report results on simulations with real DNA sequences, showing that even in the presence of 50 % false negative errors, a target of cosmid length can be recovered with less than 0.1 % miscalled bases. 1