Department of Computer Science

This seminar overviews this recent research trend and studies the characteristics of successful research in this space, to understand whether this trend will have a long-term impact on the design and implementation of large-scale computing systems.

Abstract

A gapped pattern is a sequence consisting of regular alphabet symbols and of joker symbols that match any alphabet symbol. The content of a gapped pattern is defined as the number of its non-joker symbols. A gapped motif is a gapped pattern that occurs repeatedly in a string or in a set of strings. The aim of this paper is to study the complexity of several gapped motif finding problems. The following three decision problems are shown NP-complete, even if the input alphabet is binary. (i) Given a string T and two integers c and q, decide whether or not there exists a gapped pattern with content c (or more) that occurs in T at q distinct positions (or more). (ii) Given a set of strings S and an integer c, decide whether or not there exists a gapped pattern with content c that occurs at least once in each string of S. (iii) Given m strings with the same length, and two integers c and q, decide whether or not there exists a gapped pattern with content c, matching at least q input strings. We also present a non-naive quadratic-time algorithm that solves the following optimization problem: given a string T and an integer q ≥ 0, compute a maximum-content gapped pattern Q such that q consecutive copies of Q occur in T. Key words: gapped pattern, motif discovery, string matching with don’t care symbols, NP-complete, tandem motifs. ∗ Corresponding author.