Missing pattern discovery

Stanislav Angelov, Shunsuke Inenaga, Teemu Kivioja, Veli Mäkinen

Research output: Contribution to journalArticlepeer-review


In this paper, we study the missing patterns problem: Find the shortest pair of patterns that do not occur close to each other in a given text, i.e., the distance between their occurrences is always greater than a given threshold α. We present various solutions to this problem, as well as to the case where the patterns in the pair are required to be of the same length. This work is motivated by optimizing the sensitivity of PCR. Experiments show that our algorithm is practical enough to handle human genome data.

Original languageEnglish
Pages (from-to)153-165
Number of pages13
JournalJournal of Discrete Algorithms
Issue number2
Publication statusPublished - Jun 2011

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Missing pattern discovery'. Together they form a unique fingerprint.

Cite this