𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the complexity of finding common approximate substrings

✍ Scribed by Patricia A. Evans; Andrew D. Smith; H.Todd Wareham

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
323 KB
Volume
306
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

Problems associated with ΓΏnding strings that are within a speciΓΏed Hamming distance of a given set of strings occur in several disciplines. In this paper, we use techniques from parameterized complexity to assess non-polynomial time algorithmic options and complexity for the COMMON APPROXIMATE SUBSTRING (CAS) problem. Our analyses indicate under which parameter restrictions useful algorithms are possible, and include both class membership and parameterized reductions to prove class hardness. In order to achieve ΓΏxed-parameter tractability, either a ΓΏxed string length or both a ΓΏxed size alphabet and ΓΏxed substring length are su cient. Fixing either the string length or the alphabet size and Hamming distance is shown to be necessary, unless W [1] = FPT . An assortment of parameterized class membership and hardness results cover all other parameterized variants, showing in particular the e ect of ΓΏxing the number of strings.

πŸ“œ SIMILAR VOLUMES

On the Common Substring Alignment Proble
On the Common Substring Alignment Problem
✍ Gad M Landau; Michal Ziv-Ukelson πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 164 KB

The Common Substring Alignment Problem is defined as follows: Given a set of one or more strings S 1 S 2 S c and a target string T , Y is a common substring of all strings S i , that is, S i = B i YF i . The goal is to compute the similarity of all strings S i with T , without computing the part of

On the complexity of finding balanced on
On the complexity of finding balanced oneway cuts
✍ Uriel Feige; Orly Yahalom πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 88 KB

A bisection of an n-vertex graph is a partition of its vertices into two sets S and T , each of size n/2. The bisection cost is the number of edges connecting the two sets. In directed graphs, the cost is the number of arcs going from S to T . Finding a minimum cost bisection is NP-hard for both und

On the query complexity of finding a loc
On the query complexity of finding a local maximum point
✍ A.L. Rastsvetaev; L.D. Beklemishev πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 94 KB

We calculate the minimal number of queries sufficient to find a local maximum point of a function on a discrete interval, for a model with M parallel queries, M 1. Matching upper and lower bounds are obtained. The bounds are formulated in terms of certain Fibonacci type sequences of numbers.